Full Disclosure mailing list archives
Re: OpenID/Debian PRNG/DNS Cache poisoning advisory
From: "Leichter, Jerry" <leichter_jerrold () emc com>
Date: Fri, 8 Aug 2008 16:51:10 -0400 (EDT)
| > You can get by with a lot less than 64 bits. People see problems | > like this and immediately think "birthday paradox", but there is no | > "birthday paradox" here: You aren't look for pairs in an | > ever-growing set, you're looking for matches against a fixed set. | > If you use 30-bit hashes - giving you about a 120KB table - the | > chance that any given key happens to hash to something in the table | > is one in a billion, now and forever. (Of course, if you use a | > given key repeatedly, and it happens to be that 1 in a billion, it | > will hit every time. So an additional table of "known good keys | > that happen to collide" is worth maintaining. Even if you somehow | > built and maintained that table for all the keys across all the | > systems in the world - how big would it get, if only 1 in a billion | > keys world-wide got entered?) | I don't believe your math is correct here. Or rather, it would | be correct if there was only one bad key. | | Remember, there are N bad keys and you're using a b-bit hash, which | has 2^b distinct values. If you put N' entries in the hash table, the | probability that a new key will have the same digest as one of them is | N'/(2^b). If b is sufficiently large to make collisions rare, then | N'=~N and we get N/(2^b). | | To be concrete, we have 2^15 distinct keys, so, the probability of a | false positive becomes (2^15)/(2^b)=2^(b-15). To get that probability | below 1 billion, b+15 >= 30, so you need about 45 bits. I chose 64 | because it seemed to me that a false positive probability of 2^{-48} | or so was better. You're right, of course - I considered 32,000 to be "vanishingly small" compared to the number of hash values, but of course it isn't. The perils of looking at one number just as decimal and the other just in exponential form.... In any case, I think it's clear that even for extremely conservative "false hit" ratios, the table size is quite reasonable. You wouldn't want the table on your smart card or RFID chip, perhaps, but there even a low-end "smartphone" would have no problems. -- Jerry _______________________________________________ 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:
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory, (continued)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Dave Korn (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Dan Guido (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Jin Sei (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Peter Gutmann (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Dan Kaminsky (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Eric Rescorla (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Florian Weimer (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Nicolas Williams (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Leichter, Jerry (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Eric Rescorla (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Leichter, Jerry (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Forrest J. Cavalier III (Aug 09)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Seth Breidbart (Aug 13)
- key blacklisting & file size (was: OpenID/Debian PRNG/DNS Cache poisoning advisory) Solar Designer (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Tim Dierks (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Ben Laurie (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Tim Dierks (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Stefan Kanthak (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Leichter, Jerry (Aug 08)
- Re: OpenID/Debian PRNG/DNS Cache poisoning advisory Ben Laurie (Aug 12)