[SSL Observatory] Batch gcd

[Andy Isaacson]

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.)

> 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