Forgot your password?
typodupeerror
Security

Factorable Keys: Twice As Many, But Half As Bad 40

Posted by Unknown Lamer
from the keep-on-factoring dept.
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."
This discussion has been archived. No new comments can be posted.

Factorable Keys: Twice As Many, But Half As Bad

Comments Filter:
  • 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.
  • by Kenja (541830) on Wednesday February 15, 2012 @12:48PM (#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: (Score:2, Informative)

      by Anonymous Coward

      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 ep

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

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

    • by Magada (741361) on Wednesday February 15, 2012 @01:03PM (#39046043) Journal

      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.

      • by Anonymous Coward on Wednesday February 15, 2012 @02:38PM (#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.

        • by Magada (741361)

          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.

      • by Rich0 (548339)

        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?

        • by znrt (2424692)

          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.

    • by Anonymous Coward

      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

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

  • by Anonymous Coward

    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.

  • by hawguy (1600213) on Wednesday February 15, 2012 @01:52PM (#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).

    • The biggest question I have is whether or not I need to keep my public ssh keys more private from now on.
      • by daid303 (843777)

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

    • Re:Seems overblown (Score:4, Informative)

      by timeOday (582209) on Wednesday February 15, 2012 @05:54PM (#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.
  • by Anonymous Coward

    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

  • by hobit (253905)

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

It is much easier to suggest solutions when you know nothing about the problem.

Working...