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:slashdotted

[show me altoids]

Here's the whole article, for those who still can't get to it: New research: There's no need to panic over factorable keys--just mind your Ps and Qs By Nadia Heninger - Posted on February 15th, 2012 at 2:16 am You may have seen the preprint posted today by Lenstra et al. about entropy problems in public keys. Zakir Durumeric, Eric Wustrow, Alex Halderman, and I have been waiting to talk about some similar results. We will be publishing a full paper after the relevant manufacturers have been notified. Meanwhile, we'd like to give a more complete explanation of what's really going on. We have been able to remotely compromise about 0.4% of all the public keys used for SSL web site security. The keys we were able to compromise were generated incorrectly--using predictable "random" numbers that were sometimes repeated. There were two kinds of problems: keys that were generated with predictable randomness, and a subset of these, where the lack of randomness allows a remote attacker to efficiently factor the public key and obtain the private key. With the private key, an attacker can impersonate a web site or possibly decrypt encrypted traffic to that web site. We've developed a tool that can factor these keys and give us the private keys to all the hosts vulnerable to this attack on the Internet in only a few hours. However, there's no need to panic as this problem mainly affects various kinds of embedded devices such as routers and VPN devices, not full-blown web servers. (It's certainly not, as suggested in the New York Times, any reason to have diminished confidence in the security of web-based commerce.) Unfortunately, we've found vulnerable devices from nearly every major manufacturer and we suspect that more than 200,000 devices, representing 4.1% of the SSL keys in our dataset, were generated with poor entropy. Any weak keys found to be generated by a device suggests that the entire class of devices may be vulnerable upon further analysis. We're not going to announce every device we think is vulnerable until we've contacted their manufacturers, but the attack is fairly easy to reproduce from material already known. That's why we are working on putting up a web site that you can use to determine whether your device is immediately vulnerable. Read on for more details, and watch for our full paper soon. Don't worry, the key for your bank's web site is probably safe SSL is used to authenticate every major web site on the Internet, but in our analysis, these were not the keys that were vulnerable to the problems outlined in this blog post. So which systems are vulnerable? Almost all of the vulnerable keys were generated by and are used to secure embedded hardware devices such as routers and firewalls, not to secure popular web sites such as your bank or email provider. Only one of the factorable SSL keys was signed by a trusted certificate authority and it has already expired. There are signed certificates using repeated keys; some of them are generated by vulnerable devices, some of them are due to website owners submitting known weak keys to be signed, and for some of them we have no good explanation. Embedded devices are well known to have entropy problems. However, until now it wasn't apparent how widespread these problems were in real, Internet-connected devices. Background: key generation Websites and networked computers use public-key cryptography for authentication. The kind of authentication that we will be talking about here is a server certifying to a client that it really is the server that the client intended to connect to. An attacker who knows the private key to one of these systems would be able to impersonate the real system to a client or in many cases decrypt encrypted traffic between the client and server. The most widely used cryptosystem for this purpose is RSA. The RSA cryptosystem is intended to be based on the difficulty of factoring large numbers. An RSA public key consists of a pair of integers: an encryption exponent e and a modulus N, which is a large integer that itself is the produ