Factorable Keys: Twice As Many, But Half As Bad

J. Alex Halderman and Nadia Heninger write in with an update to yesterday's story on RSA key security: "Yesterday Slashdot posted that RSA keys are 99.8% secure in the real world. We've been working on this concurrently, and as it turns out, the story is a bit more complicated. Those factorable keys are generated by your router and VPN, not bankofamerica.com. The geeky details are pretty nifty: we downloaded every SSL and SSH keys on the internet in a few days, did some math on 100 million digit numbers, and ended up with 27,000 private keys. (That's 0.4% of SSL keys in current use.) We posted a long blog post summarizing our findings over at Freedom to Tinker."

Comments

Re:Why does this happen?

[Magada]

If you have a shit pseudo entropy generator, the keys you generate will be easy to factor because they will share one common prime factor (recall that key security depends on the computational intractability of factoring large numbers). This is called a related-key attack and has (so far) been responsible only for the demise of WEP.

As it turns out, OpenSSH/SSL has a shit PRNG which makes private keys generated with it recoverable using only the public keys, in some implementations and usage scenarios. Together, these amount to 0.4% of ALL public keys currently available on the open 'Net.