Re: OpenID/Debian PRNG/DNS Cache poisoning advisory

[Eric Rescorla <ekr () networkresonance com>]

At Fri, 08 Aug 2008 10:43:53 -0700,
Dan Kaminsky wrote:
> Eric Rescorla wrote:
> > It's easy to compute all the public keys that will be generated
> > by the broken PRNG. The clients could embed that list and refuse
> > to accept any certificate containing one of them. So, this
> > is distinct from CRLs in that it doesn't require knowing 
> > which servers have which cert...
> 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
1024-bit RSA keys. There are ~32,000 such keys. If you devote an
80-bit 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
build (Windows) is 7.1 MB, this doesn't sound like a nonstarter to me
at all, especially since the browser could download it in the
background.


> Updating the filter could then be something we do on a 24 hour 
> autoupdate basis.  Doing either this, or doing revocation checking over 
> DNS (seriously), is not necessarily a bad idea.  We need to do better 
> than we've been.

Yes, there are a number of approaches to more efficient CRL
checking, I think that's a separate issue.

-Ekr