The Cryptopocalypse | Hacker News Reader

The Cryptopocalypse

schneier.com

80 pointsGarbage21 comments

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.

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?

Recent versions of SSH (6.1p1 on Ubuntu 13.04) support ECDSA, http://en.wikipedia.org/wiki/Elliptic_Curve_DSA

Unfortunately, gnome-keyring-daemon can't deal with those keys...grrr.

As of GnuPG 2.0.21, gpg-agent can deal with ECDSA keys, which is quite nice.

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.

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

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

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.

What were the reasons for this lateness?

IIRC there were patent issues for some curves, but is that the only reason?

> It's past time people started moving away from RSA.

What do you recommend instead?

ECDH, ECDSA.

Over prime fields, please.

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.

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.

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.

Matthew Green breaks this down in considerably more detail here; highly recommended:

https://news.ycombinator.com/item?id=6238305

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.

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.

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

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

Indeed, but then he could go with a less scary title than "The Cryptopocalypse". "RSApocalypse" maybe.

Reply on news.ycombinator.com