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]

Message-ID: <4DA63CAA.2010905@extendedsubset.com>
Date: Wed, 13 Apr 2011 19:15:38 -0500
From: Marsh Ray <marsh@...endedsubset.com>
To: Pavel Kankovsky <peak@...o.troja.mff.cuni.cz>
Cc: full-disclosure@...ts.grok.org.uk
Subject: Re: how would browser vendors deal with $O(10^k)$
 fake certs?

On 04/10/2011 03:48 PM, Pavel Kankovsky wrote:
> On Sun, 10 Apr 2011, Georgi Guninski wrote:
>>
>> 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).

Only in cases where the element is found though, the last bit only needs 
to be checked if all the preceding bits matched. In the normal 
(non-attack) case the "s3r34l number" isn't found.

A precomputed hash table or Bloom filter could be very small and 
effectively O(1) even for 10K entries. Except for those dumb CAs that 
issued sequential numbers, just the first few bytes of the cert would be 
enough to rule it out of the blacklist.

Hard-coding serial numbers in the source code still looks like a sad act 
of desperation though.

- Marsh

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