Full Disclosure mailing list archives
Re: how would browser vendors deal with $O(10^k)$ fake certs?
From: Pavel Kankovsky <peak () argo troja mff cuni cz>
Date: Sun, 10 Apr 2011 22:48:34 +0200 (CEST)
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/
Current thread:
- how would browser vendors deal with $O(10^k)$ fake certs? Georgi Guninski (Apr 10)
- Re: how would browser vendors deal with $O(10^k)$ fake certs? Pavel Kankovsky (Apr 10)
- Re: how would browser vendors deal with $O(10^k)$ fake certs? Marsh Ray (Apr 13)
- Re: how would browser vendors deal with $O(10^k)$ fake certs? Pavel Kankovsky (Apr 17)
- Re: how would browser vendors deal with $O(10^k)$ fake certs? Marsh Ray (Apr 13)
- Re: how would browser vendors deal with $O(10^k)$ fake certs? Pavel Kankovsky (Apr 10)