Slashdot Mirror
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."
I guess we could say yesterday's report was off by 100%, but let's not go crazy. 0.4% is still too many, but it's still not as bad as it could be with all the cert vendor break-ins that have gone on recently.
So how do you go about matching one of the keys that you guessed and a specific users session? What's more, how do you do that before the key changes? I can guess a password is "fishmonkeywrinkles", but without a matching account that wont do much good.
"Have you ever thought about just turning off the TV, sitting down with your kids, and hitting them?"
Pretty sure these guys care more about scaring people and publicizing it than having a practical use to the attack.
100-million-digit numbers? That's about what, about a 330-million-bit number? I haven't seen too many 40 MiB public keys. Even the product of two 4096-bit numbers is only three thousand digits.
Site seems slashdotted, down or whatever.
Was there anything new over articele from arstechnica?
http://arstechnica.com/business/news/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security.ars
What I would like to know is: Why does this happen? How do these bad keys get generated? Why so many of them?
Please correct me if I got my facts wrong.
This was posted just 19 hours ago... it's still visible on my version of Slashdot's front page.
Or you could read the article, where they say that there's no need to panic, and criticize the New York Times for freaking out about it.
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
I feel sorry for people that don't drink, because when they get up in the morning, that's as good as they're gonna feel
All I see is a wall of text.
I can guess a password is "fishmonkeywrinkles"
Sonovabitch.
Now I have to change my password.
All I see is a wall of text.
Apparently what you pay for to get past the 'pay wall' is the line feeds.
FTA:
For the system to provide security, however, it is essential that the secret prime numbers be generated randomly. The researchers discovered that in a small but significant number of cases, the random number generation system failed to work correctly.
So it's the faulty implementations that we need to worry about. The foundation itself is still strong.
Quick! Everybody log in as "Anonymous Coward" before he changes it!
Are the bad Debian ssh keys taken into account?
http://digitaloffense.net/tools/debian-openssl/
So how do you go about matching one of the keys that you guessed and a specific users session? What's more, how do you do that before the key changes? I can guess a password is "fishmonkeywrinkles", but without a matching account that wont do much good.
The keys in question are the 'permanent' ones that are used to establish the (supposedly) secure user sessions. The authors are saying that it is possible to factor the RSA public key and arrive at the private key. Once you have the private key you can do do a man-in-the-middle attack and pretend to be the server.
Furthermore, all user sessions can be recorded and decrypted after-the-fact since each session is encrypted with the (now compromised) private/public key pair. (Except if you're using SSL/TLS in ephemeral mode to provide perfect forward security--which hardly anyone does.)
So two possible attacks are: (1) do a MITM for specific connections, and (2) record everything you can and decrypt later at your leisure.
How many of the keys are still the old insecure Debian OpenSSL disaster keys?
I think few people use the SSL keys on the home router/firewall for anything other than local administration of their firewall so it doesn't really matter if the SSL can be broken, no one is watching and no one cares.
Even if the few people that actually used their home router/firewall to encrypt data sent over the public internet have hackable encrypted sessions, it's pretty unlikely that an attacker is watching their packets on the off chance that they have a hackable key when there are far easier and more common vulnerabilities to exploit when the attacker has access to your network packets (like firesheep style session stealing).
I see a few spaces in there.
Every time I start to have faith in humanity, I ruin it by driving to work between 7 and 8 am.
Both research teams claim 27000 factored keys. The difference seems to be in how they count the number of active certificates.
I wonder if these keys came as the result of the massive debian packaging screwup of openssh?
http://lists.debian.org/debian-security-announce/2008/msg00152.html
An official "Woot!" to Alex, Nadia and Michigan. Sorry you were scooped, but it sounds like you've actually identified the underlying problem.
As Nietsche famously said, "If you stare too long into the Abyss, 1d4 Tanar'ri of random type will attack you."
99.8%
Isn't this the same as saying 1 of every 500 keys is not secure? Doesn't sound secure to me.
Here's the whole article, for those who still can't get to it:
( Now, with line feeds. )
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 expone