Links

Ben Laurie blathering


Searching for Weak PRNGs

A paper I was shown this morning at NSPW reminded me of what seems ancient history, but in fact was only two years ago: PET 2004, in Toronto. In the coffee breaks, Matthias Bauer and I cooked up a plan to find weak PRNGs by searching for PGP keys that had common factors – apparently an early version of PGP had a PRNG that wasn’t much good, so there was some chance it might have generated the same prime for two different key.

So, the way you do this is to take every pair of PGP keys and take the GCD. If they have a common factor, this will be something other than 1 (in fact, it’ll be the common factor, of course). If I remember correctly there were around a million keys at the time, and my laptop (an IBM A31p, at the time) completed the task in about 24 hours.

Sadly, all we found was a pair of keys with common factor 9 – which means both keys were totally broken. Matthias may remember the key IDs if anyone wants to play, but I don’t.

As far as I remember, we never really wrote this up, so I thought I’d mention it here.

4 Comments »

  1. We looked at v3 keys exclusively, and there are about
    48000 on the keyservers (that’s still a lot of pairs).
    My writeup “Factoring silly keys from the keyservers”
    is at
    http://shoestringfoundation.org/cgi-bin/blosxom.cgi/2004/07/01#non-pgp-key
    Cheers
    Matthias

    Comment by Matthias — 23 Sep 2006 @ 11:43

  2. [...] One thing that will go wrong and unsettle everybone is broken crypto: the cracking of more and more complex keys. There are two strange aspects for me. One is that I just dont begin for the life of me to understand the cryptography on which the safety of my on-line business life depends. The second is that only a small proportion of the people who crack these security systems are good enough to say so (Ben Laurie on PGP or <a href=”http://www.pgp.net/pgpnet/pgp-faq/pgp-faq-security-questions.html#security-rsa> this on PGP), and we have have to assume that those who are secretive about it (of whatever variety) are more numerous, more highly motivated and generally ahead of the honest hobbyists to whom I can more easily relate. [...]

    Pingback by Blindside » Blog Archive » Cracking crypto — 17 Feb 2007 @ 16:24

  3. [...] not the only work in this area that has been done. At the PETS conference in 2004, Ben Laurie and Matthias Bauer did the same analysis of PGP keys and found no duplicate factors in [...]

    Pingback by RSA Key Generation Flaw Does Not Affect Entrust Certificates « SSL Blog - Entrust Insights — 16 Feb 2012 @ 22:14

  4. [...] is not the only work in this area that has been done. At the PETS conference in 2004, Ben Laurie and Matthias Bauer did the same analysis of PGP keys and found no duplicate factors in [...]

    Pingback by RSA Key Generation Flaw Does Not Affect Entrust Certificates - Identity On — 12 Apr 2012 @ 16:49

RSS feed for comments on this post. TrackBack URI

Leave a comment

Powered by WordPress

Close
E-mail It