Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Factorable Keys: Twice As Many, But Half As Bad

Unknown Lamer posted more than 2 years ago | from the keep-on-factoring dept.

Security 40

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

cancel ×

40 comments

Sorry! There are no comments related to the filter you selected.

So, Twice As Many? (0)

WrongSizeGlass (838941) | more than 2 years ago | (#39045831)

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.

slashdotted (-1)

Anonymous Coward | more than 2 years ago | (#39045833)

Wow! Didn't know this still happened!

Re:slashdotted (1, Redundant)

show me altoids (1183399) | more than 2 years ago | (#39046129)

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 product of two large primes, p and q. If an adversary can factor this integer N back into its prime factors p and q, then the adversary can decrypt any messages encrypted using this public key. However, even using the fastest known factoring algorithm, to public knowledge nobody has yet been able to factor a 1024-bit RSA modulus. It is vitally important to the security of the keys that they are generated using random inputs. If the inputs used to generate the keys were not random, then an adversary may be able to guess those inputs and thus recover the keys without having to laboriously factor N. On modern computers and servers, key generation software attempts to collect random information from physical sources (often through the underlying operating system): the movements of the mouse, keyboard, hard drive, network events, and other external sources of unpredictable information. However, if the keys are generated from a small set of possibilities, that is, using too little entropy, then the keys may be vulnerable to an attacker. Gathering strong entropy and verifying its strength is a very difficult problem that has given rise to multiple vulnerabilities over the years. Two versions of the problem We decided to investigate the prevalence of this issue by scanning the Internet for all SSL and SSH public keys. We scanned every IPv4 address on the Internet, collecting a copy of each SSL certificate and SSH host key. We were able to complete both scans in less than a day: we first used a standard tool called nmap to find hosts with the relevant ports open, and then used our own optimized software to query those hosts. In our SSL scan, we collected 5.8 million certificates. In our SSH scan, we collected 10 million host keys. We found that entropy problems resulted in two different types of weaknesses: Repeated public keys. We found that 1% of the RSA keys in our SSL scan data were repeated, apparently due to entropy problems. When two different devices have the same public key, it means they also have the same private key. In effect, the devices that share keys are "in the same boat" as one another--an attacker would only need to compromise the weakest one of these devices, in order to obtain the repeated private key that protects all of the devices. This has long been a known problem, but until now, none of the publicly available security literature has documented how widespread the problem was. We manually verified that 59,000 duplicate keys were repeated due to entropy problems, representing 1% of all certificates, or 2.6% of self-signed certificates. We also found that 585,000 certificates, or 4.6% of all devices used the default certificates pre-installed on embedded devices. While these devices are not using keys generated with poor entropy, they are suspectible to the same attack as their private keys are found on every device of a given model. We manually verified these keys because a large number of websites may utilize repeated keys for legitimate reason; these provide no risk to users. Factorable public keys. More surprisingly, we discovered that entropy problems can allow a remote attacker with no special access to factor a significant fraction of the RSA keys in use on the Internet. We were able to factor 0.4% of the RSA keys in our SSL scan. We did this by computing the greatest common divisor (GCD) of all pairs of moduli from RSA public keys on the Internet. We identified 1724 common factors which allowed us to factor 24,816 SSL keys, and 301 common factors which allowed us to factor 2422 SSH host keys. This means we were able to calculate the private keys for almost half of 1% of the RSA keys in use for SSL. We will explain how we did this calculation below. Specific vulnerable devices Embedded devices often generate cryptographic keys on first boot, when their entire state may have been pre-determined in the factory. This can result in the kinds of entropy problems we observe in this study. We were able to use information from the SSL certificates to identify classes of devices that are prone to generating weak keys. Many more devices than the ones whose keys we factored are probably also producing weak keys that could be compromised by a determined attacker. The list of vulnerable devices that we have already identified includes more than thirty different manufacturers, including almost all of the biggest names in the computer hardware industry. The kinds of products that we identified include firewalls, routers, VPN devices, remote server administration devices, printers, projectors, and VOIP phones. We're not going to list specific devices or brands until we've told the manufacturers, but here are some examples: Firewall product X: 52,055 hosts in our SSL dataset 6,730 share public keys 12,880 have factorable keys Consumer-grade router Y: 26,952 hosts in our SSL dataset 9,345 share public keys 4,792 have factorable keys Enterprise remote access solution Z: 1,648 hosts in our SSL dataset 24 share public keys 0 factorable How could this happen? It wasn't obvious at first how these types of entropy problems might result in keys that could be factored. We'll explain now for the geekier readers. Here's one way a programmer might generate an RSA modulus: prng.seed(seed) p = prng.generate_random_prime() q = prng.generate_random_prime() N = p*q If the pseudorandom number generator is seeded with a predictable value, then that would likely result in different devices generating the same modulus N, but we would not expect a good pseudorandom number generator to produce different moduli that share a single factor. However, some implementations add additional randomness between generating the primes p and q, with the intention of increasing security: prng.seed(seed) p = prng.generate_random_prime() prng.add_randomness(bits) q = prng.generate_random_prime() N = p*q If the initial seed to the pseudorandom number generator is generated with low entropy, this could result in multiple devices generating different moduli which share the prime factor p and have different second factors q. Then both moduli can be easily factored by computing their GCD: p = gcd(N1, N2). OpenSSL's RSA key generation functions this way: each time random bits are produced from the entropy pool to generate the primes p and q, the current time in seconds is added to the entropy pool. Many, but not all, of the vulnerable keys were generated by OpenSSL and OpenSSH, which calls OpenSSL's RSA key generation code. Computing the GCDs of all pairs of keys If any pair of RSA moduli N1 and N2 share, say, the same prime factor p in common, but have different second factors q1 and q2, then we can easily factor the moduli by computing their greatest common divisor. On my desktop computer, computing the GCD of two 1024-bit RSA moduli took about 17s. For the mathematically inclined, I'll explain how we were able to use this idea to factor a large collection of keys. The simplest way that one might try to factor keys is by computing the GCD of each pair of RSA moduli. A back of the envelope calculation shows that doing a GCD computation for all pairs of moduli in our data sets would take 24 years of computation time on my computer. Instead, we used an idea Dan Bernstein published in the Journal of Algorithms in 2005 for factoring a group of integers into coprimes which allowed us to do the computation in a few hours on a desktop computer, in a few lines of Python. The algorithm is no great secret: a long stream of published papers has worked on improving these ideas. The main mathematical insight is that one can compute the GCD of a single modulus N1 with every other modulus N2,,Nm using the following equation: gcd(N1,N2Nm) = gcd(N1, (N1*N2**Nm mod N12)/N1) The secret sauce is in making this run fast--note that the first step is to compute the product of all the keys, a 729 million digit number. We were able to factor the SSL data in eighteen hours on a desktop computer using a single core, and the SSH data in about four hours using four cores. The bottom line This is a problem, but it's not something that average users need to worry about just yet. However, embedded device manufacturers have a lot of work to do, and some system administrators should be concerned. This is a wake-up call to the security community, and a reminder to all of how security vulnerabilities can sometimes be hiding in plain sight.

Re:slashdotted (1, Funny)

Yvan256 (722131) | more than 2 years ago | (#39046175)

All I see is a wall of text.

Re:slashdotted (1, Insightful)

WrongSizeGlass (838941) | more than 2 years ago | (#39046251)

All I see is a wall of text.

Apparently what you pay for to get past the 'pay wall' is the line feeds.

Re:slashdotted (2)

nschubach (922175) | more than 2 years ago | (#39047145)

I see a few spaces in there.

Re:slashdotted (0)

Anonymous Coward | more than 2 years ago | (#39057985)

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 exponent e and a modulus N, which is a large integer that itself is the product of two large primes, p and q. If an adversary can factor this integer N back into its prime factors p and q, then the adversary can decrypt any messages encrypted using this public key.

However, even using the fastest known factoring algorithm, to public knowledge nobody has yet been able to factor a 1024-bit RSA modulus.

It is vitally important to the security of the keys that they are generated using random inputs. If the inputs used to generate the keys were not random, then an adversary may be able to guess those inputs and thus recover the keys without having to laboriously factor N.

On modern computers and servers, key generation software attempts to collect random information from physical sources (often through the underlying operating system): the movements of the mouse, keyboard, hard drive, network events, and other external sources of unpredictable information. However, if the keys are generated from a small set of possibilities, that is, using too little entropy, then the keys may be vulnerable to an attacker. Gathering strong entropy and verifying its strength is a very difficult problem that has given rise to multiple vulnerabilities over the years.

Two versions of the problem
We decided to investigate the prevalence of this issue by scanning the Internet for all SSL and SSH public keys. We scanned every IPv4 address on the Internet, collecting a copy of each SSL certificate and SSH host key. We were able to complete both scans in less than a day: we first used a standard tool called nmap to find hosts with the relevant ports open, and then used our own optimized software to query those hosts. In our SSL scan, we collected 5.8 million certificates. In our SSH scan, we collected 10 million host keys.

We found that entropy problems resulted in two different types of weaknesses: Repeated public keys. We found that 1% of the RSA keys in our SSL scan data were repeated, apparently due to entropy problems. When two different devices have the same public key, it means they also have the same private key. In effect, the devices that share keys are "in the same boat" as one another--an attacker would only need to compromise the weakest one of these devices, in order to obtain the repeated private key that protects all of the devices. This has long been a known problem, but until now, none of the publicly available security literature has documented how widespread the problem was. We manually verified that 59,000 duplicate keys were repeated due to entropy problems, representing 1% of all certificates, or 2.6% of self-signed certificates.

We also found that 585,000 certificates, or 4.6% of all devices used the default certificates pre-installed on embedded devices. While these devices are not using keys generated with poor entropy, they are suspectible to the same attack as their private keys are found on every device of a given model. We manually verified these keys because a large number of websites may utilize repeated keys for legitimate reason; these provide no risk to users.

Factorable public keys.
More surprisingly, we discovered that entropy problems can allow a remote attacker with no special access to factor a significant fraction of the RSA keys in use on the Internet. We were able to factor 0.4% of the RSA keys in our SSL scan. We did this by computing the greatest common divisor (GCD) of all pairs of moduli from RSA public keys on the Internet. We identified 1724 common factors which allowed us to factor 24,816 SSL keys, and 301 common factors which allowed us to factor 2422 SSH host keys. This means we were able to calculate the private keys for almost half of 1% of the RSA keys in use for SSL. We will explain how we did this calculation below.

Specific vulnerable devices
Embedded devices often generate cryptographic keys on first boot, when their entire state may have been pre-determined in the factory. This can result in the kinds of entropy problems we observe in this study. We were able to use information from the SSL certificates to identify classes of devices that are prone to generating weak keys. Many more devices than the ones whose keys we factored are probably also producing weak keys that could be compromised by a determined attacker. The list of vulnerable devices that we have already identified includes more than thirty different manufacturers, including almost all of the biggest names in the computer hardware industry. The kinds of products that we identified include firewalls, routers, VPN devices, remote server administration devices, printers, projectors, and VOIP phones.

We're not going to list specific devices or brands until we've told the manufacturers, but here are some examples:
Firewall product X: 52,055 hosts in our SSL dataset 6,730 share public keys 12,880 have factorable keys
Consumer-grade router Y: 26,952 hosts in our SSL dataset 9,345 share public keys 4,792 have factorable keys
Enterprise remote access solution Z: 1,648 hosts in our SSL dataset 24 share public keys 0 factorable How could this happen? It wasn't obvious at first how these types of entropy problems might result in keys that could be factored.

We'll explain now for the geekier readers.
Here's one way a programmer might generate an RSA modulus: prng.seed(seed) p = prng.generate_random_prime() q = prng.generate_random_prime() N = p*q If the pseudorandom number generator is seeded with a predictable value, then that would likely result in different devices generating the same modulus N, but we would not expect a good pseudorandom number generator to produce different moduli that share a single factor. However, some implementations add additional randomness between generating the primes p and q, with the intention of increasing security: prng.seed(seed) p = prng.generate_random_prime() prng.add_randomness(bits) q = prng.generate_random_prime() N = p*q
If the initial seed to the pseudorandom number generator is generated with low entropy, this could result in multiple devices generating different moduli which share the prime factor p and have different second factors q. Then both moduli can be easily factored by computing their GCD: p = gcd(N1, N2). OpenSSL's RSA key generation functions this way: each time random bits are produced from the entropy pool to generate the primes p and q, the current time in seconds is added to the entropy pool. Many, but not all, of the vulnerable keys were generated by OpenSSL and OpenSSH, which calls OpenSSL's RSA key generation code. Computing the GCDs of all pairs of keys If any pair of RSA moduli N1 and N2 share, say, the same prime factor p in common, but have different second factors q1 and q2, then we can easily factor the moduli by computing their greatest common divisor. On my desktop computer, computing the GCD of two 1024-bit RSA moduli took about 17s.

For the mathematically inclined, I'll explain how we were able to use this idea to factor a large collection of keys.

The simplest way that one might try to factor keys is by computing the GCD of each pair of RSA moduli. A back of the envelope calculation shows that doing a GCD computation for all pairs of moduli in our data sets would take 24 years of computation time on my computer. Instead, we used an idea Dan Bernstein published in the Journal of Algorithms in 2005 for factoring a group of integers into coprimes which allowed us to do the computation in a few hours on a desktop computer, in a few lines of Python. The algorithm is no great secret: a long stream of published papers has worked on improving these ideas. The main mathematical insight is that one can compute the GCD of a single modulus N1 with every other modulus N2,,Nm using the following equation: gcd(N1,N2Nm) = gcd(N1, (N1*N2**Nm mod N12)/N1) The secret sauce is in making this run fast--note that the first step is to compute the product of all the keys, a 729 million digit number. We were able to factor the SSL data in eighteen hours on a desktop computer using a single core, and the SSH data in about four hours using four cores.

The bottom line
This is a problem, but it's not something that average users need to worry about just yet. However, embedded device manufacturers have a lot of work to do, and some system administrators should be concerned. This is a wake-up call to the security community, and a reminder to all of how security vulnerabilities can sometimes be hiding in plain sight.

Dont these keys change often? How would you match? (5, Insightful)

Kenja (541830) | more than 2 years ago | (#39045837)

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.

Re:Dont these keys change often? How would you mat (0)

Anonymous Coward | more than 2 years ago | (#39045877)

Pretty sure these guys care more about scaring people and publicizing it than having a practical use to the attack.

Re:Dont these keys change often? How would you mat (0)

Anonymous Coward | more than 2 years ago | (#39046121)

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.

Re:Dont these keys change often? How would you mat (0)

Anonymous Coward | more than 2 years ago | (#39046239)

I can guess a password is "fishmonkeywrinkles"

Sonovabitch.
Now I have to change my password.

Re:Dont these keys change often? How would you mat (2, Funny)

Anonymous Coward | more than 2 years ago | (#39046299)

Quick! Everybody log in as "Anonymous Coward" before he changes it!

Re:Dont these keys change often? How would you mat (2, Informative)

Anonymous Coward | more than 2 years ago | (#39046647)

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.

100-million-digit numbers (1)

blueg3 (192743) | more than 2 years ago | (#39045891)

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.

Re:100-million-digit numbers (4, Informative)

blueg3 (192743) | more than 2 years ago | (#39045939)

Ah, I see. You regularly work with the product of all of the moduli gathered, which would be a fairly large number.

Slashdotted. Anything new from Ars article? (0)

Anonymous Coward | more than 2 years ago | (#39045911)

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

Why does this happen? (1)

inglorion_on_the_net (1965514) | more than 2 years ago | (#39045919)

What I would like to know is: Why does this happen? How do these bad keys get generated? Why so many of them?

Re:Why does this happen? (5, Informative)

Magada (741361) | more than 2 years ago | (#39046043)

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.

Re:Why does this happen? (4, Informative)

Anonymous Coward | more than 2 years ago | (#39047575)

As it turns out, OpenSSH/SSL has a shit PRNG

AFAIK, OpenSSL gets its entropy from the operating system. If the OS has no good source of entropy, like on the embedded devices mentioned in the article, it doesn't matter what library you use to generate your keys, they will alway be predictable and therefore weak.

The article makes no mention of keys generated on non-embedded devices being weak, so it's probably safe to assume that generating a key on a desktop or server with decent entropy sources using OpenSSL is secure.

Re:Why does this happen? (1)

Magada (741361) | more than 2 years ago | (#39058071)

It gets worse. OpenSSL also retrieves uptime and mixes it with what it gets from /dev/urandom, iirc. Of course, uptime is not as random as all that, especially on embedded devices. Let's say you write a script that generates a key on first boot. That boot is going to take the exact same amount of time on all identical devices and there is precious little entropy to work with. Oops.

Re:Why does this happen? (2)

Rich0 (548339) | more than 2 years ago | (#39049887)

What I'd like to know is how to tell if my key is a bad one or not. I don't mind throwing some CPU-time at the problem, but I don't see any info online for how to check your own key.

Since I know my own private keys, perhaps an algorithm would be able to analyze how "similar" my keys are? Or, do you need to have the original primes?

Re:Why does this happen? (1)

znrt (2424692) | more than 2 years ago | (#39052663)

What I'd like to know is how to tell if my key is a bad one or not. I don't mind throwing some CPU-time at the problem, but I don't see any info online for how to check your own key

all needed info is already in the article. you just have to do what they did, but include your key in the set and check if it shares "p" with any other. if it does, generate a new one but move your mouse like crazy this time (a good moment to enjoy some flash game, maybe).

the most stunnig part for me is still scanning the whole internets for keys. dude! maybe in near future there could be a trusted repository or service for this, dunno.

Re:Why does this happen? (1)

Anonymous Coward | more than 2 years ago | (#39046159)

The keys are just two large prime numbers multiplied together.
Rather than using a deterministic test to find a large prime, most times they use a probabilistic test to find a large pseudoprime number.
http://en.wikipedia.org/wiki/Prime_number#Primality_testing_versus_primality_proving

If you have 5 million devices generating pseudoprimes, odds are that at least two of the devices will generate a non prime number, and the two non prime numbers will share a common factor.
So take 5 million random keys, which are 5 million random numbers, and find the GCD comparing them two at a time.
http://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid.27s_algorithm

Odds are you will find two of the random keys that share a common factor, and those two devices are now not secure.

Based on the numbers in TFS, The odds of finding two psuedoprimes with a common factor is 0.4%, or 27,000 of the 5 million.

MEGA DUPE (0)

EmagGeek (574360) | more than 2 years ago | (#39046045)

This was posted just 19 hours ago... it's still visible on my version of Slashdot's front page.

Re:MEGA DUPE (1)

aardvarkjoe (156801) | more than 2 years ago | (#39046125)

This was posted just 19 hours ago... it's still visible on my version of Slashdot's front page.

Think of it as a blast from the past. There were days when every other story on /. was a dupe.

Re:MEGA DUPE (3, Informative)

phantomfive (622387) | more than 2 years ago | (#39046463)

You mean this story [slashdot.org] that was actually mentioned in the summary if you had managed to finish the first sentence of the summary?

Re:MEGA DUPE (0)

Anonymous Coward | more than 2 years ago | (#39047489)

Now come on. There's no need to be an asshole to the GP. After all, isn't it obvious he's kinda special?

Not a flaw in the crypto (2, Insightful)

Anonymous Coward | more than 2 years ago | (#39046297)

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.

Re:Not a flaw in the crypto (0)

Anonymous Coward | more than 2 years ago | (#39047051)

So then the statistic doesn't really mean anything. There is no whatever% chance your key is secure; rather, if your implemenation is good, it's secure, and otherwise it isn't.
Instead of the meaningless percentage a list of bad implementations should have been posted in the summary. (I'd check TFA, but it's slashdotted.)

Debian keys (0)

Anonymous Coward | more than 2 years ago | (#39046387)

Are the bad Debian ssh keys taken into account?
http://digitaloffense.net/tools/debian-openssl/

Re:Debian keys (0)

Anonymous Coward | more than 2 years ago | (#39048977)

I doubt it. The flaw with Debian was a poor seed to the PRNG, not a poor PRNG. I wouldn't expect it to be any different from any other OpenSSL.

Old Debian keys? (0)

Anonymous Coward | more than 2 years ago | (#39046677)

How many of the keys are still the old insecure Debian OpenSSL disaster keys?

Seems overblown (2)

hawguy (1600213) | more than 2 years ago | (#39046779)

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

Re:Seems overblown (1)

ModernGeek (601932) | more than 2 years ago | (#39047801)

The biggest question I have is whether or not I need to keep my public ssh keys more private from now on.

Re:Seems overblown (1)

daid303 (843777) | more than 2 years ago | (#39049997)

You don't. Your public ssh keys are generated with a good /dev/random, these refactorable keys are not.

Re:Seems overblown (3, Informative)

timeOday (582209) | more than 2 years ago | (#39051449)

There must be small businesses using VPN features [amazon.com] of these routers (I am not implying D-Link is the affected party by the way). Otherwise they wouldn't have found so many such keys on the open net (0.4% of all keys) - certainly there aren't that many people remotely configuring their firewalls etc. If I were using one for VPN I would watch closely for a firmware upgrade in the near future.

Twice as many ? (0)

Anonymous Coward | more than 2 years ago | (#39047543)

Both research teams claim 27000 factored keys. The difference seems to be in how they count the number of active certificates.

Debian screw up? (1)

Anonymous Coward | more than 2 years ago | (#39047655)

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

Woot! (0)

hobit (253905) | more than 2 years ago | (#39047943)

An official "Woot!" to Alex, Nadia and Michigan. Sorry you were scooped, but it sounds like you've actually identified the underlying problem.

499/500 keys secure (0)

Anonymous Coward | more than 2 years ago | (#39050245)

99.8%

Isn't this the same as saying 1 of every 500 keys is not secure? Doesn't sound secure to me.

Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?