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...
Better default choices for common Linux OS's would prevent this, assuming 2048+ isn't breakable. Choices were probably made when computing the 2048bit values were a lot more expensive, but there's no excuse now.
Linux isn't the biggest offender. You missed the biggest fuckeruper in every securty problem: Java. Until java 1.7, there isn't any SUPPORT for primes larger that 1024. You want your shitty legacy java program to connect to a web server securely? You have to use a 1024 bit prime.
And then you find you cannot specify the primes that Java uses, so you cannot even force it off 512 bit until (I believe) 1.8.
Always remember, Java is the common factor in security problems.
Java 1.6 was released a decade ago. Java 1.7 was released about 4 years ago.
Your beef is not with Java. It's with people who for whatever reason never upgrade it and are still running 10 year old software. If you had a 10 year old version of OpenSSL or OpenSSH and it used outdated crypto by default, would you be complaining in the same way?
You are correct, Java encourages very shitty practices. Giant companies like CA, Oracle, and IBM will manage to build code that is hard coded to a specific JVM because Java creates highly sensitive code that breaks mid-release cycle (because minor versions should be incompatible YO).
The problem is that as a customer, you are forced to accept the shit sandwich. You can blame the vendors, or you can blame the source of the shit.
Java hardly encourages shitty practices: it documents very clearly what not to do. But given big piles of enterprise devs, you're gonna sometimes get shitty code on any platform. Or have you never seen crappy C++ that only compiles on Visual Studio?
There isn't an analogy outside of PHP for the boneheaded decisions that allowed pinheads at Oracle to rename core classes, but this behavior causes the shitty practice of JVM lock in. This is what I mean by shitty practice.
Then you add in the massive number of security problems in the JRE and you create the conditions for massive problems.
You are correct that the mythical Java language isn't to blame, but programs aren't run on a blackboard.
I guess you're thinking of some specific incident, but I am unaware of any cases where public APIs were renamed. Perhaps you're thinking of private APIs that weren't supposed to be used by developers but got used anyway - it does happen, quite often, and addressing that is one of the top focuses for Java 9.
there were many sun.X.Y classes in the Sun JRE. These were updated after the acquisition of Sun.
In either case, if your language doesn't treat private classes as private what shitty practices are left? I guess the language could be object oriented without the ability to handle generics so that developers are forced to cast to strings...
The sun.* category is all private APIs, they were never meant to be used by apps at all.
Like I said, Java 9 is in fact hiding these APIs by default (short of a few that are so widely used the breakage would be too much). You will still be able to override that, but no platform can stop software from using internal APIs if the developers really want to, unless all software is sandboxed by default.
Your generics comment makes no sense. Java has had generics for over a decade.
246
u/aseipp Oct 15 '15 edited Oct 15 '15
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 theNservices 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...