OpenID/Debian PRNG/DNS Cache poisoning advisory
Leichter, Jerry
leichter_jerrold at emc.com
Fri Aug 8 15:52:07 EDT 2008
 > > Funnily enough I was just working on this  and found that we'd
 > > end up adding a couple megabytes to every browser. #DEFINE
 > > NONSTARTER. I am curious about the feasibility of a large bloom
 > > filter that fails back to online checking though. This has side
 > > effects but perhaps they can be made statistically very unlikely,
 > > without blowing out the size of a browser.
 > Why do you say a couple of megabytes? 99% of the value would be
 > 1024bit RSA keys. There are ~32,000 such keys. If you devote an
 > 80bit hash to each one (which is easily large enough to give you a
 > vanishingly small false positive probability; you could probably get
 > away with 64 bits), that's 320KB. Given that the smallest Firefox
 > [...]
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?)
 You could store {<hash>, <seed>} and check matches for false positives
 by generating a key with the corresponding seed and then checking for an
 exact match  slow, but rare. This way you could choose your false
 positive rate / table size comfort zone and vary the size of the hash
 accordingly.
Or just go off to one of a number of web sites that have a full table.
Many solutions are possible, when they only need to be invoked very,
very rarely.
 Jerry
 Nico
 

 
 The Cryptography Mailing List
 Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list