[SSL Observatory] Batch gcd

[Peter Eckersley]

On Sat, Dec 29, 2012 at 02:46:44AM -0800, Andy Isaacson wrote:
> On Sat, Dec 29, 2012 at 11:22:35AM +0100, Hanno Böck wrote:
> > In a talk on #29c3 Dan Bernstein describes an algorithm to break weak
> 
> Actually the bad-rng work came from Nadia Heninger.  Dan co-presented
> some related work in the "real world factorization" session at 29c3.
> (The three presenters, also including Tanja Lange, traded off the mic a
> lot so it was sometimes hard to tell whose work was being presented.)

Simultaneous, independent versions of this attack were found by Nadia and her
coauthors, and by Arjen Lenstra and a team at EFPL, who used a (still
unpublished, unfortunately) centralised SSL Observatory scan.

Based on data from both teams, the Decentralized SSL Observatory should issue
warnings if your browser accepts one of these known-factorisable keys,
although we don't have a realtime gcd pipeline at this point.

> 
> > RSA keys using a broken random number generator. The basic idea is that
> > if two keys share a common prime, you can find that out with the
> > greatest common divisor algorithm and you can use batch gcd to do it on
> > a bunch of keys.
> > 
> > There are preliminary video recordings of the talk
> > https://www.youtube.com/watch?v=N5Wn6ZBLjgU
> > and here's the basic algorithm described
> > http://facthacks.cr.yp.to/batchgcd.html
> > 
> > Now the obvious question: Has anyone already tried to do this on the
> > ssl observatory data? Is it feasible on home-hardware? (In the talk
> 
> Nadia's original paper supercedes the Observatory data AFAIK.
> https://factorable.net/weakkeys12.extended.pdf
> 
>   By scanning the public IPv4 address space, we collected 5.8 million
>   unique TLS certificates from 12.8 million hosts and 6.2 million
>   unique SSH host keys from 10.2 million hosts. This is 67% more TLS
>   hosts than the latest released EFF SSL Observatory dataset [20].
> 
> > sounds like it would be feasible, but I'm unsure if this is only true
> > for 1024 bit keys or if it'd be also feasible on longer keys)
> 
> It's quite feasible to do batch GCD on a PC on a few million
> 4096-or-fewer-bit keys, although I'm not sure if Sage is up to the task.
> 
> -andy
> 

-- 
Peter Eckersley                            pde at eff.org
Technology Projects Director      Tel  +1 415 436 9333 x131
Electronic Frontier Foundation    Fax  +1 415 436 9993