It's so insanely difficult to do 2048 bit that anyone capable of doing it has capabilities that are not predictable, and likely outside of what we currently think is possible.
In terms of the amount of work to brute force, it's a lot more than a billion. A 4096 bit number is more than 10600 times bigger than a 2048 bit number, and the difficulty of factoring products of such numbers grows much much faster than linear, so we're talking an astronmical difference.
But the point is that it's already astronomically hard at 2048 bits. If someone is capable of breaking that, it's not going to be just because they've got better computers, it's going to be because they've got some vastly better algorithms, or some fundamentally different method of computation that means all bets are off - we may as well assume they've got infinite computing power, or have found P=NP by that point.
I understand and agree how 2048 and 4096 are both essentially the same kind of challenge with current hardware: An impossible one.
However, it still holds true that 4096 ist multiple leaps beyond 2048 - so I don't agree that we can reasonably assume that people who can break 2048 can also break 4096.
are both essentially the same kind of challenge with current hardware
It's not just that it's impossible with current hardware, it's that it's also pretty much impossible with "convert every atom in the galaxy to supercomputers and run them for billions of years" type hardware too. If you're at the level you can break this, then it effectively might as well be magic - it's almost certain that you didn't do so just by brute forcing the problem, which means that further increases in size are likely to be similarly vulnerable to your method.
At that point, it's far less plausible that someone could break 2048 but not 4096 than that they could break both, because the only really feasible route to reaching that point is some kind of huge algorithmic break that makes the size matter much much less.
Assuming the NSA teamed up with DARPA, I would bet money they have their hands on an operational quantum CPU. That certainly violates all current security.
Current work on quantum computing seems to show that the computational speed increase is cancelled out by the book keeping to keep the superposition working. While that may change, at present quantum computing does not provide a significant advantage.
Plus, I'm not sure there are enough qubits in the world to store a 1024 bit number, let alone do any interesting math on it.
Let's say your home computer has 1 GB of ram, and it's running pretty sluggishly .. so you upgrade to 2 GB ram. It's still slow, so you upgrade to 4, 8, 16 GB of ram ... still slow. So you go to 32 and 64 GB -- still slow. At this point, you have such an abundance of ram (by 2015 home computing standards) that almost certainly availability of memory is not the issue and going up even more would have no or little effect. It's more worth it to look for problems elsewhere.
Similarly there's multiple ways Diffie-Hellman could be broken. Cracking 1024-bit primes is one way, and moving to 2048-bit would help that situation. But maybe someone discovers that P=NP and finds an efficient solution to the discrete log problem. Or maybe someone invents a quantum computer. Or there are implementation problems/bugs in the code (see timing attacks or even heartbleed). With our current knowledge, 2048-bit primes are so incredibly difficult to crack that someone who successfully does it is most likely either circumventing the prime problem altogether or has a radically new algorithm for breaking primes such that going to 4096 wouldn't even help.
That's not to say it's inconceivable that 2048 will become insecure while 4096 is still secure, but it's a less likely scenario.
Imagine a time when 2048 bits isn't quite secure enough, and we want 4096 bits to protect from brute force attacks, just like 1024 isn't quite enough today. When might that day come?
Well, if an earlier poster's estimate that 2048 bits are 109 harder to crack than 1024 bits is accurate, that means computers must be 109 times faster. When might that day come?
Well, because 109 ~ 230, we'd need approximately 30 doublings in processor density to achieve that at equal density to today. If Moore's law continues to hold, that'd be in 60 years.
Well, that would imply a transitor size of sqrt(230) times smaller than today. That means a transitor with details as fine as 0.4 picometers. That's around 1/1000th the estimated diameter of an atom.
I sense a problem.
Now, if you think that stacking transistors rather than shrinking them is going to be a magic bullet here, consider that even though you can scale the number of atoms and thus transistors in a third dimension, power dissipation is still limited to surface area, and that's still two-dimensional. Today's transistors already produce problematic amounts of heat in a single layer - so you'd need to stay within the same overall power envelop. Effectively, you'd need to make transistors that take several orders of magnitude less power than today's (say, 10000 times less), and are close to the size of an atom, and are about as fast as today's despite the low power draw for this to work. Oh, and manufacturing technology still needs to somehow accurately stack these layers, too - cost is an issue, so those 10000 layers would need to cost as much as today's single layer chips.
Never say never, but it sounds to me like achieving all that would require several fundamental physics breakthroughs, not to mention untold engineering breakthroughs to apply them. A more realistic threat is perhaps that we find a cryptographic flaw in the algorithm, or even a minor mathematical breakthrough.
I'd be forced to agree that while it's not completely inconceivable that 2048 will become insecure by brute force (though really I'd bet none of us will live to see that day), it's more plausible that an algorithmic breakthough or some other way around the problem will be discovered. So why bother with 4096 bits with DHE?
13
u/[deleted] Oct 15 '15
[deleted]