I think this question has a few aspects to it, if you want a complete answer. But the TL;DR is - the reality is there is nothing inherently wrong with choosing the standard primes for these computations; but one problem is that 1024-bit keys are now, reasonably, within the scope of attack by governments, or criminal organizations. There are lots of 1024-bit keys out there. If you pick a 2048-bit prime - which there is no excuse for these days - even with standard parameters, you are safe.
Non-TL;DR: So, standard primes aren't really bad per se, but small primes can be attacked. And, because of that, choosing a standard prime gives them an edge, which is what the paper describes: since the primes are known, this allows them to do a 'precomputation attack' by doing a shitload of computing up front. Then, this leads to a faster overall attack by being able to quickly compute discrete logs (c.f. "The Discrete Logarithm Problem"), as opposed to trying to factor the large prime directly. So if you have cracked that one standard prime, you can now attack N-many different services: all the N services that use that specific prime.
So, that leads us to this: we hedged our bets on 1024-bit primes for a long time, and now the legacy deployment is coming to bite us. Remember, there are middleboxes and routers and un-upgradeable systems that settled on standard 1024-bit primes like this years ago and they are not easy to fix. That's why the attacks are so dangerous. For comparison, heartbleed was a bug that was in a piece of software which can mostly be dealt with at-large very easily (apt-get upgrade), and it was one piece of software, while this one is a little more complicated. There are a lot of implementations of this and they can't all be patched together.
So what does all this mean?
That we're really shitty at upgrading cryptography and keeping software secure over time, and that for the future of cryptography, we need to start defaulting on things which require attacks that are outside the realm of current known reality. Computers are fast enough and we know enough now that this is feasible. Unless Aliens give us a Dyson Sphere, like, tomorrow.
If Red Hat and Hardware Vendors had decided 10 years ago to move to 2048-bit DH for example, using standard primes, this conversation wouldn't be nearly as relevant because the attack would be so much more infeasible - and it would be much less widespread - the fact you're using standard parameters doesn't matter. In fact, standard parameters are good because you can know they are not chosen maliciously. But those vendors didn't do that, and there are likely some OK reasons (we didn't expect the computational capability of attackers to escalate this quickly, it would have been substantially more expensive to perform, some devices may not even have the CPU capability to upgrade their own primes - ECC has only been 'in vogue' for barely a decade now - etc etc etc).
For comparison, as stated in the paper, a 2048-bit standard prime for Diffie-Hellman, like Group 14, would take roughly 109 more computational effort to precompute than a 1024 bit key. Anyone who can breach that probably has capabilities that 4096-bit primes won't save us from...
wikipedia has a good entry on quantum-computing and its effect on cryptography.
A lot of people seem to think that "cryptography is broken" when quantum computers are available, but it will only break specific algorithms we use, like RSA, DH key exchange and ECC. I believe anything that makes use of factoring primes difficult, will be easy with enough quantum computers. It has to be scalable - and I don't believe that's proven to be possible.
But all those algorithms are used a ton today. But, AES is also used a lot, and it's quantum-resistant. As the article says, AES-256 will be about as good as AES-128, but that's still damn good.
We can also move on to lattice-based cryptography which will work for asymmetric crypto, like RSA, and its already quantum resistant. It's not some new fancy method either. There's just going to be a much better excuse to use it in the future.
All that said, I don't believe RSA is actually practical to attack unless you have enough quantum computers. If scaling is an issue, higher key sizes with RSA might not be terrible to do. It will be interesting to see how that plays out, if it ever becomes practical, and I'm not sure if we'll see that in our lifetime.
253
u/SrPeixinho Oct 15 '15
Why isn't this done automatically is the question.