5 ms·

The keys to the keydom

152 points by breadbox 13y ago

queeerkopf 13y ago
Thanks for posting. Well worth the time spent reading it :)
randywaterhouse 13y ago
A very interesting read. The final point is probably the most notable one, that key-generation immediately following a boot up can compromise the PRNG (as we know). Also a cool thought, comparing all those keys. I just compared the few keys I have hanging around (only of order 10, not 4 billion), and none of mine have common factors other than 1. Yay! Spoofing host keys also sounds like a potential target, so you could spoof the server identity and then decrypt communications without having to deal with the actual key-cracking.
gpcz 13y ago
64,081 is really close to 65536 (2^16) -- I wonder if the 64,000 vulnerable TLS keys have anything to do with a bug similar to the 2008 Debian SSL key fiasco, where the only contributor to the key's entropy was the PID (2^15 combinations). It would be interesting to see data about the types of devices that have these weak keys, but then again if there is a correlation its release could be used maliciously in the wild.
- ye 13y ago
  It's definitely a bug, most likely in the pre-prime generation (not enough entropy). If we're talking 1024-bit integers created by multiplying two 512-bit primes, the facts are: 1) The number of 512-bit primes is estimated around 11.36×10^150 2) The chance that two truly random primes are the same is one in 3.37*10^75. It is safe to assume it has never happened and never will (at least on our current hardware).
  - jsmeaton 13y ago
    > We’re only at 10^7 so far. As Heninger said in her talk, we have enough 512-bit primes to assign a public encryption key to every atom in the universe, with little worry over possible duplicates. I find the scale of these numbers absolutely incredible.
- kalleboo 13y ago
  The post mentions "Most of them are found in embedded networked devices, such as routers and firewalls". Embedded devices like that have very little entropy on first boot - that could might cause them to generate very poor keys. I wonder how many of the 60% non-unique keys are embedded devices with hardcoded keys...
  - voltagex_ 13y ago
    I can see the bumper stickers now - "Have you disassembled your firmware today?" Sigh. I'm not sure what we can do (as an industry). Bad devices (and bad firmware, and bad software) are so widely deployed it seems almost impossible to fix.
  - bigiain 13y ago
    "I wonder how many of the 60% non-unique keys are embedded devices with hardcoded keys..." That wouldn't surprise me much at all. I've been working on a secure workaround to let an embedded webserver on our consumer-oriented wifi-equipped hardware(1) do OAuth2 authentication (to connect to owner's Twitter/Faceboot/et al. accounts). OAuth relies on SSL/TLS to protect it's password-equivalent tokens on-the-wire. Getting an SSL cert onto the device (at a reasonable cost) so that a phone connecting to it via wifi doesn't throw up big scarey "somebody might be doing _bad_ things!" warnings is not easily solved. (1) Shameless self promotion: http://holiday.moorescloud.com http://holiday.moorescloud.com - The world's most intelligent christmas lights…
- reirob 13y ago
  This question has been asked in the comments to the article and there is answer: "Heninger et al. did check their data for “Debian weak keys.” They found 4,147 such TLS keys and 53,141 SSH keys."
themenace 13y ago
Check if your site uses a known weak key here: https://factorable.net/keycheck.html https://factorable.net/keycheck.html Enter a domain name or an IP address.
- blueblob 13y ago
  I pasted my key in to check. Came out as: "Factorable RSA Key Check Pass! This RSA key is not known to be factorable." I would have felt uncomfortable checking my publicly available TLS or SSH server because if it comes back a fail, how do I know the site is not logging the data and logging in?
  - themenace 13y ago
    I'm not seeing the risk if it's a publicly available address. Analogy: They tested every door lock in America. They found that 64,000 door locks are trivially opened. They put up a website where you can enter your home address to see if you're vulnerable. If you enter your home address ("123 Maple Street"), they could lie and tell you that you're secure, but then go and rob you. The thing is that they already knew whether 123 Maple Street was secure or not. They could have robbed you beforehand. (Also, let's say that they never tested 123 Maple Street, and they tell you arbitrarily that you're secure. In this case, they still haven't gained any new knowledge.)
    - acchow 13y ago
      This isn't it at all. They have been handed a giant pile of all keys to all homes in America. They went through the pile and found all but 64,000 keys to be too damaged to be usable. Those 64,000 keys are perfectly good, but they don't know which homes they belong to. They open up a shop allowing people to come in with their lock to check if their key is one of the 64,000. Do you go to check? Do you drive? Or do you go wearing a mask on your face and take public transit (VPN + tor)?
      - BoppreH 13y ago
        Unless I misunderstood, they know which keys belongs to which houses. They successfully factored those keys, and unless they threw the metadata away they still know the domain that is using that key. And if they did throw the metadata away, they still have this pile of 64,000 prime factors. They can ask the domains for their public keys again and test if any of those factors matches.
tptacek 13y ago
I don't have a source to back this up, but I thought this problem had been tracked down to a faulty Cisco CSPRNG. (Later: nope, I'm wrong; the P's and Q's paper has Juniper vulnerable as well. The more likely commonality might be solid state devices and cold-start entropy.)
tunesmith 13y ago
I had trouble following this point: "Even though Euclid’s GCD algorithm is highly efficient, running it on all possible pairings of keys would be a strain. There’s an ingenious shortcut, based on the observation that if Y is relatively prime to each of X1,X2,…,Xn, then it also has no factor in common with the product X1×X2×⋯×Xn. Thus it’s possible to detect the presence of shared factors with just n GCD operations, instead of n2." Can someone explain that shortcut in more detail?
- bumbledraven 13y ago
  Someone please correct me if I'm wrong, but I guess the shortcut is something like this: Z = X[1] * X[2] * X[3] * ... * X[n]; for i in (1..n-1) { Z = Z/X[i]; g = GCD(X[i], Z); if (g > 1) { // check each other key to see which have g as a factor for j in (j+1..n) { if (X[j] % g == 0) { log that keys i & j have g as a common factor; } } } Rather than having to run the inner loop for every iteration of the outer loop, it only has to run in the case where there is a common factor. For instance, to check for common factors in [4, 13, 10] we initially compute Z = 4 * 13 * 10 = 520. Then we start with the first key, 4. Divide Z by 4 yielding 130. Do 4 and 130 have a common factor? gcd(4,130) = 2, so yes they do. We now check each remaining key individually (13 & 10) for divisibility by 2 and report which one(s) match, (in this case, 10). Then we continue with the second key, 13. Divide Z by 13 yielding 10. Do 13 & 10 have a common factor? No, they don't, and there are no more keys left to check, so we're done.
  - cipherzero 13y ago
    Yes that's correct, however you need not actually "log that keys i & j have g as a common factor;" if g > 1 then just add x[i] to a list, after checking all in x, then just go through that much smaller list. ( even better would be to just group x[I] in a dictionary based on g)... good example though.
- pudquick 13y ago
  I think it's shorthand English for saying: Rather than doing n^2 comparisons (ie. every key individually GCD compared against every other key individually = (n keys)x(n-1 other keys) combinations), you can instead do n total GCD comparisons - every key GCD factored a single time against <large product of every other key> (which works out to (n keys)x(1 big product) GCD comparisons)
reirob 13y ago
"Some 60 percent of the keys retrieved were not unique. Presumably, most of the duplicates are accounted for by organizations that have multiple servers all operating with the same cryptographic credentials, but there were also instances of apparently unaffiliated individuals sharing a key." - how is it possible that 60 percent have the same keys? I also do not understand why a big company would share the same public key across servers? If it is compromised (somebody got the private key) then all its servers are compromised, right?
- alexkus 13y ago
  > I also do not understand why a big company would share the same public key across servers? They might not be different servers, just different IPs. Multiple external IPs may all terminate at the same piece of hardware (Firewall, VPN device, SSL terminator, etc).

152 points by breadbox 13y ago

Thanks for posting. Well worth the time spent reading it :)

A very interesting read. The final point is probably the most notable one, that key-generation immediately following a boot up can compromise the PRNG (as we know). Also a cool thought, comparing all those keys. I just compared the few keys I have hanging around (only of order 10, not 4 billion), and none of mine have common factors other than 1. Yay! Spoofing host keys also sounds like a potential target, so you could spoof the server identity and then decrypt communications without having to deal with the actual key-cracking.

gpcz 13y ago

64,081 is really close to 65536 (2^16) -- I wonder if the 64,000 vulnerable TLS keys have anything to do with a bug similar to the 2008 Debian SSL key fiasco, where the only contributor to the key's entropy was the PID (2^15 combinations). It would be interesting to see data about the types of devices that have these weak keys, but then again if there is a correlation its release could be used maliciously in the wild.

ye 13y ago
It's definitely a bug, most likely in the pre-prime generation (not enough entropy). If we're talking 1024-bit integers created by multiplying two 512-bit primes, the facts are: 1) The number of 512-bit primes is estimated around 11.36×10^150 2) The chance that two truly random primes are the same is one in 3.37*10^75. It is safe to assume it has never happened and never will (at least on our current hardware).
- jsmeaton 13y ago
  > We’re only at 10^7 so far. As Heninger said in her talk, we have enough 512-bit primes to assign a public encryption key to every atom in the universe, with little worry over possible duplicates. I find the scale of these numbers absolutely incredible.
kalleboo 13y ago
The post mentions "Most of them are found in embedded networked devices, such as routers and firewalls". Embedded devices like that have very little entropy on first boot - that could might cause them to generate very poor keys. I wonder how many of the 60% non-unique keys are embedded devices with hardcoded keys...
- voltagex_ 13y ago
  I can see the bumper stickers now - "Have you disassembled your firmware today?" Sigh. I'm not sure what we can do (as an industry). Bad devices (and bad firmware, and bad software) are so widely deployed it seems almost impossible to fix.
- bigiain 13y ago
  "I wonder how many of the 60% non-unique keys are embedded devices with hardcoded keys..." That wouldn't surprise me much at all. I've been working on a secure workaround to let an embedded webserver on our consumer-oriented wifi-equipped hardware(1) do OAuth2 authentication (to connect to owner's Twitter/Faceboot/et al. accounts). OAuth relies on SSL/TLS to protect it's password-equivalent tokens on-the-wire. Getting an SSL cert onto the device (at a reasonable cost) so that a phone connecting to it via wifi doesn't throw up big scarey "somebody might be doing _bad_ things!" warnings is not easily solved. (1) Shameless self promotion: http://holiday.moorescloud.com http://holiday.moorescloud.com - The world's most intelligent christmas lights…
reirob 13y ago
This question has been asked in the comments to the article and there is answer: "Heninger et al. did check their data for “Debian weak keys.” They found 4,147 such TLS keys and 53,141 SSH keys."

themenace 13y ago

Check if your site uses a known weak key here: https://factorable.net/keycheck.html https://factorable.net/keycheck.html Enter a domain name or an IP address.

blueblob 13y ago
I pasted my key in to check. Came out as: "Factorable RSA Key Check Pass! This RSA key is not known to be factorable." I would have felt uncomfortable checking my publicly available TLS or SSH server because if it comes back a fail, how do I know the site is not logging the data and logging in?
- themenace 13y ago
  I'm not seeing the risk if it's a publicly available address. Analogy: They tested every door lock in America. They found that 64,000 door locks are trivially opened. They put up a website where you can enter your home address to see if you're vulnerable. If you enter your home address ("123 Maple Street"), they could lie and tell you that you're secure, but then go and rob you. The thing is that they already knew whether 123 Maple Street was secure or not. They could have robbed you beforehand. (Also, let's say that they never tested 123 Maple Street, and they tell you arbitrarily that you're secure. In this case, they still haven't gained any new knowledge.)
  - acchow 13y ago
    This isn't it at all. They have been handed a giant pile of all keys to all homes in America. They went through the pile and found all but 64,000 keys to be too damaged to be usable. Those 64,000 keys are perfectly good, but they don't know which homes they belong to. They open up a shop allowing people to come in with their lock to check if their key is one of the 64,000. Do you go to check? Do you drive? Or do you go wearing a mask on your face and take public transit (VPN + tor)?
    - BoppreH 13y ago
      Unless I misunderstood, they know which keys belongs to which houses. They successfully factored those keys, and unless they threw the metadata away they still know the domain that is using that key. And if they did throw the metadata away, they still have this pile of 64,000 prime factors. They can ask the domains for their public keys again and test if any of those factors matches.

tptacek 13y ago

I don't have a source to back this up, but I thought this problem had been tracked down to a faulty Cisco CSPRNG. (Later: nope, I'm wrong; the P's and Q's paper has Juniper vulnerable as well. The more likely commonality might be solid state devices and cold-start entropy.)

tunesmith 13y ago

I had trouble following this point: "Even though Euclid’s GCD algorithm is highly efficient, running it on all possible pairings of keys would be a strain. There’s an ingenious shortcut, based on the observation that if Y is relatively prime to each of X1,X2,…,Xn, then it also has no factor in common with the product X1×X2×⋯×Xn. Thus it’s possible to detect the presence of shared factors with just n GCD operations, instead of n2." Can someone explain that shortcut in more detail?

bumbledraven 13y ago
Someone please correct me if I'm wrong, but I guess the shortcut is something like this: Z = X[1] * X[2] * X[3] * ... * X[n]; for i in (1..n-1) { Z = Z/X[i]; g = GCD(X[i], Z); if (g > 1) { // check each other key to see which have g as a factor for j in (j+1..n) { if (X[j] % g == 0) { log that keys i & j have g as a common factor; } } } Rather than having to run the inner loop for every iteration of the outer loop, it only has to run in the case where there is a common factor. For instance, to check for common factors in [4, 13, 10] we initially compute Z = 4 * 13 * 10 = 520. Then we start with the first key, 4. Divide Z by 4 yielding 130. Do 4 and 130 have a common factor? gcd(4,130) = 2, so yes they do. We now check each remaining key individually (13 & 10) for divisibility by 2 and report which one(s) match, (in this case, 10). Then we continue with the second key, 13. Divide Z by 13 yielding 10. Do 13 & 10 have a common factor? No, they don't, and there are no more keys left to check, so we're done.
- cipherzero 13y ago
  Yes that's correct, however you need not actually "log that keys i & j have g as a common factor;" if g > 1 then just add x[i] to a list, after checking all in x, then just go through that much smaller list. ( even better would be to just group x[I] in a dictionary based on g)... good example though.
pudquick 13y ago
I think it's shorthand English for saying: Rather than doing n^2 comparisons (ie. every key individually GCD compared against every other key individually = (n keys)x(n-1 other keys) combinations), you can instead do n total GCD comparisons - every key GCD factored a single time against <large product of every other key> (which works out to (n keys)x(1 big product) GCD comparisons)

reirob 13y ago

"Some 60 percent of the keys retrieved were not unique. Presumably, most of the duplicates are accounted for by organizations that have multiple servers all operating with the same cryptographic credentials, but there were also instances of apparently unaffiliated individuals sharing a key." - how is it possible that 60 percent have the same keys? I also do not understand why a big company would share the same public key across servers? If it is compromised (somebody got the private key) then all its servers are compromised, right?

alexkus 13y ago
> I also do not understand why a big company would share the same public key across servers? They might not be different servers, just different IPs. Multiple external IPs may all terminate at the same piece of hardware (Firewall, VPN device, SSL terminator, etc).