full-disclosure - Re: how would browser vendors deal with $O(10^k)$ fake certs?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Sun, 10 Apr 2011 22:48:34 +0200 (CEST)
From: Pavel Kankovsky <peak@...o.troja.mff.cuni.cz>
To: Georgi Guninski <guninski@...inski.com>
Cc: full-disclosure@...ts.grok.org.uk
Subject: Re: how would browser vendors deal with $O(10^k)$
 fake certs?

On Sun, 10 Apr 2011, Georgi Guninski wrote:

> what would do most browser vendors do if they find $O(10^k)$ fake server
> certs (possibly from different RA) {one assume $k$ is not **that** big}
> [god forbid CA certs]?
> 
> appears to me getting the certs is one time cost to the attacker, while
> checking 10^k c3rt s3r34l numbers (as in the panic patch) requires loop
> to 10^k?

You always need \Omega(l) operations to check a value where l is the
number of its significant bits (i.e. of the cert's serial number).
It cannot be less than \Omega(l) because you need to read and consider
every of those significant bits (they would not be really significant if
you did not have to do that).

Any set of values having (at most) l significant bits can be represented
by a bitwise trie whose depth is (at most) l. The presence of any value in
the set can be checked in \O(l) operations.

\Omega(l) + O(l) = \Omega(l).

-- 
Pavel Kankovsky aka Peak                          / Jeremiah 9:21        \
"For death is come up into our MS Windows(tm)..." \ 21st century edition /

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/