6 ms·

The Cryptopocalypse

80 points by Garbage 13y ago

tptacek 13y ago
I think the authors of the presentation† would agree with Schneier about the math, and I know Tom Ritter's working on a bit of a follow-up. But I don't think they'd agree on Schneier's message here, which is that people who use RSA have nothing to worry about. The Joux small-char DLP stuff isn't going to directly impact RSA, but RSA in its most commonly used key size (1024 bits) is not secure, and the next common size up (2048 bits) is ~5x slower. It's past time people started moving away from RSA. † My name is first listed among them but I did literally no work on it; I'm as confused as you are, but flattered.
- leokun 13y ago
  What do you use for your SSH key. RSA? Just curious. As far as I know RSA and DSA are the only options for SSH, or is that wrong?
  - contingencies 13y ago
    Looks like you are right. The ssh-keygen manpage reports: The possible values are 'rsa1' for protocol version 1 and 'rsa' or 'dsa' for protocol version 2.
    - leokun 13y ago
      I installed openssh from homebrew dupes and just upgraded my key to ecdsa. Now to update all the things. Github doesn't support this yet so I put a special line in my .ssh/config to use my old key with github.com
  - MichaelSalib 13y ago
    Recent versions of SSH (6.1p1 on Ubuntu 13.04) support ECDSA, http://en.wikipedia.org/wiki/Elliptic_Curve_DSA http://en.wikipedia.org/wiki/Elliptic_Curve_DSA Unfortunately, gnome-keyring-daemon can't deal with those keys...grrr.
    - zx2c4 13y ago
      As of GnuPG 2.0.21, gpg-agent can deal with ECDSA keys, which is quite nice.
    - deleted 13y ago
      [deleted]
- geal 13y ago
  Increasing key length has been the main way to protect crypto from Moore's law. That law is somewhat predictable: we can now how much time a key can hold depending on ressources needed to crack it. The real problem here: cryptanalysis advances like Joux's tend to create big leaps, much bigger than what we predict based on Moore's law. And there's the problem that RSA 2048 is slow, and RSA 4096 is so slow that it's impractical...
  - tptacek 13y ago
    These are analyses that were available a decade ago, unfortunately. We should already be in the middle of a transition away from RSA and to ECC constructions.
    - geal 13y ago
      What were the reasons for this lateness? IIRC there were patent issues for some curves, but is that the only reason?
- conroy 13y ago
  > It's past time people started moving away from RSA. What do you recommend instead?
  - tptacek 13y ago
    ECDH, ECDSA.
    - cperciva 13y ago
      Over prime fields, please.
      - pbsd 13y ago
        Do you really not trust binary curves that much? I'm certainly not going to defend them, but curves over prime exponent binary fields seem OK for now. For us this might not matter much, but hardware people like binary fields a lot.
        cperciva 13y ago
        They scare me a bit, simply because of the added structure. I don't have any concrete argument for why they're bad; it's just that there's more places to start from when analysing them. I don't buy the cost arguments... if you're limited by how many asymmetric crypto operations you can handle, you're either doing something very wrong or something very unusual.
trebor 13y ago
If I read this correctly, Schneier is saying that "increasing key size will be enough to stay ahead of the advances in factorization for the foreseeable future." I hope this is true. But I think I'll stick to my guns, saying that RSA will be broken (with)in 5 years.
aortega 13y ago
Even if RSA is broken tomorrow, we already have many other algorithms for asymmetric encryption that do not depend on factoring and can't be broken even with a quantum computer, like the McEliece cryptosystem. We only would need to change the standard quickly like when MD5 was broken.
- tptacek 13y ago
  However true that is, it doesn't really respond to anyone's point (Schneier's or Ritter/Samuel's); nobody involved in this was saying something like "crypto is dead".
  - aortega 13y ago
    Indeed, but then he could go with a less scary title than "The Cryptopocalypse". "RSApocalypse" maybe.
- eterm 13y ago
  But look at what happened when MD5 was broken. Did everyone move swiftly away from MD5? Well no, it still turns up daily even in new developments[1]. Library maintainers value compatibility over security, so would rather continue to include a broken hash function than remove it and break applications. [1] http://stackoverflow.com/search?tab=newest&q=md5 http://stackoverflow.com/search?tab=newest&q=md5
tptacek 13y ago
Matthew Green breaks this down in considerably more detail here; highly recommended: https://news.ycombinator.com/item?id=6238305 https://news.ycombinator.com/item?id=6238305
tlb 13y ago
Remember folks: people may be capturing and storing your SSL traffic now. If there is a huge advance in factoring 5 or 10 years from now, they'll be able to decrypt all your traffic from today.

80 points by Garbage 13y ago

I think the authors of the presentation† would agree with Schneier about the math, and I know Tom Ritter's working on a bit of a follow-up. But I don't think they'd agree on Schneier's message here, which is that people who use RSA have nothing to worry about. The Joux small-char DLP stuff isn't going to directly impact RSA, but RSA in its most commonly used key size (1024 bits) is not secure, and the next common size up (2048 bits) is ~5x slower. It's past time people started moving away from RSA. † My name is first listed among them but I did literally no work on it; I'm as confused as you are, but flattered.

leokun 13y ago
What do you use for your SSH key. RSA? Just curious. As far as I know RSA and DSA are the only options for SSH, or is that wrong?
- contingencies 13y ago
  Looks like you are right. The ssh-keygen manpage reports: The possible values are 'rsa1' for protocol version 1 and 'rsa' or 'dsa' for protocol version 2.
  - leokun 13y ago
    I installed openssh from homebrew dupes and just upgraded my key to ecdsa. Now to update all the things. Github doesn't support this yet so I put a special line in my .ssh/config to use my old key with github.com
- MichaelSalib 13y ago
  Recent versions of SSH (6.1p1 on Ubuntu 13.04) support ECDSA, http://en.wikipedia.org/wiki/Elliptic_Curve_DSA http://en.wikipedia.org/wiki/Elliptic_Curve_DSA Unfortunately, gnome-keyring-daemon can't deal with those keys...grrr.
  - zx2c4 13y ago
    As of GnuPG 2.0.21, gpg-agent can deal with ECDSA keys, which is quite nice.
  - deleted 13y ago
    [deleted]
geal 13y ago
Increasing key length has been the main way to protect crypto from Moore's law. That law is somewhat predictable: we can now how much time a key can hold depending on ressources needed to crack it. The real problem here: cryptanalysis advances like Joux's tend to create big leaps, much bigger than what we predict based on Moore's law. And there's the problem that RSA 2048 is slow, and RSA 4096 is so slow that it's impractical...
- tptacek 13y ago
  These are analyses that were available a decade ago, unfortunately. We should already be in the middle of a transition away from RSA and to ECC constructions.
  - geal 13y ago
    What were the reasons for this lateness? IIRC there were patent issues for some curves, but is that the only reason?
conroy 13y ago
> It's past time people started moving away from RSA. What do you recommend instead?
- tptacek 13y ago
  ECDH, ECDSA.
  - cperciva 13y ago
    Over prime fields, please.
    - pbsd 13y ago
      Do you really not trust binary curves that much? I'm certainly not going to defend them, but curves over prime exponent binary fields seem OK for now. For us this might not matter much, but hardware people like binary fields a lot.
      - cperciva 13y ago
        They scare me a bit, simply because of the added structure. I don't have any concrete argument for why they're bad; it's just that there's more places to start from when analysing them. I don't buy the cost arguments... if you're limited by how many asymmetric crypto operations you can handle, you're either doing something very wrong or something very unusual.

trebor 13y ago

If I read this correctly, Schneier is saying that "increasing key size will be enough to stay ahead of the advances in factorization for the foreseeable future." I hope this is true. But I think I'll stick to my guns, saying that RSA will be broken (with)in 5 years.

aortega 13y ago

Even if RSA is broken tomorrow, we already have many other algorithms for asymmetric encryption that do not depend on factoring and can't be broken even with a quantum computer, like the McEliece cryptosystem. We only would need to change the standard quickly like when MD5 was broken.

tptacek 13y ago
However true that is, it doesn't really respond to anyone's point (Schneier's or Ritter/Samuel's); nobody involved in this was saying something like "crypto is dead".
- aortega 13y ago
  Indeed, but then he could go with a less scary title than "The Cryptopocalypse". "RSApocalypse" maybe.
eterm 13y ago
But look at what happened when MD5 was broken. Did everyone move swiftly away from MD5? Well no, it still turns up daily even in new developments[1]. Library maintainers value compatibility over security, so would rather continue to include a broken hash function than remove it and break applications. [1] http://stackoverflow.com/search?tab=newest&q=md5 http://stackoverflow.com/search?tab=newest&q=md5

tptacek 13y ago

Matthew Green breaks this down in considerably more detail here; highly recommended: https://news.ycombinator.com/item?id=6238305 https://news.ycombinator.com/item?id=6238305

tlb 13y ago

Remember folks: people may be capturing and storing your SSL traffic now. If there is a huge advance in factoring 5 or 10 years from now, they'll be able to decrypt all your traffic from today.