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:
  • by blueg3 (192743) on Wednesday February 15, 2012 @12:54PM (#39045939)

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

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

  • Re:MEGA DUPE (Score:4, Informative)

    by phantomfive (622387) on Wednesday February 15, 2012 @01:31PM (#39046463) Journal
    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?
  • by Anonymous Coward on Wednesday February 15, 2012 @01:43PM (#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.

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

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

Real Users find the one combination of bizarre input values that shuts down the system for days.

Working...