Re: OpenID/Debian PRNG/DNS Cache poisoning advisory
From: 
Leichter, Jerry <leichter_jerrold@emc.com> 
To: 
Eric Rescorla <ekr@networkresonance.com> 
Cc: 
Nicolas Williams <Nicolas.Williams@sun.com>,Dan Kaminsky <dan@doxpara.com>,Dave Korn <dave.korn@artimi.com>,'Ben Laurie' <benl@google.com>,bugtraq@securityfocus.com,security@openid.net,'OpenID List' <general@openid.net>,cryptography@metzdowd.com,fulldisclosure@lists.grok.org.uk 
Subject: 
Re: OpenID/Debian PRNG/DNS Cache poisoning advisory 
Date: 
Fri, 08 August 2008 20:51 GMT 
 > 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
 > evergrowing set, you're looking for matches against a fixed set.
 > If you use 30bit 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 worldwide 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 bbit 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^(b15). 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 lowend "smartphone" would have no problems.
 Jerry


