The Cryptopocalypse
There was a presentation at Black Hat last month warning us of a “factoring cryptopocalypse”: a moment when factoring numbers and solving the discrete log problem become easy, and both RSA and DH break. This presentation was provocative, and has generated a lot of commentary, but I don’t see any reason to worry.
Yes, breaking modern public-key cryptosystems has gotten easier over the years. This has been true for a few decades now. Back in 1999, I wrote this about factoring:
Factoring has been getting easier. It’s been getting easier faster than anyone has anticipated. I see four reasons why this is so:
- Computers are getting faster.
- Computers are better networked.
- The factoring algorithms are getting more efficient.
- Fundamental advances in mathematics are giving us better factoring algorithms.
I could have said the same thing about the discrete log problem. And, in fact, advances in solving one problem tend to mirror advances in solving the other.
The reasons are arrayed in order of unpredictability. The first two—advances in computing and networking speed—basically follow Moore’s Law (and others), year after year. The third comes in regularly, but in fits and starts: a 2x improvement here, a 10x improvement there. It’s the fourth that’s the big worry. Fundamental mathematical advances only come once in a while, but when they do come, the effects can be huge. If factoring ever becomes “easy” such that RSA is no longer a viable cryptographic algorithm, it will be because of this sort of advance.
The authors base their current warning on some recent fundamental advances in solving the discrete log problem, but the work doesn’t generalize to the types of numbers used for cryptography. And they’re not going to generalize; the result is simply specialized.
This isn’t to say that solving these problems won’t continue to get easier, but so far it has been trivially easy to increase key lengths to stay ahead of the advances. I expect this to remain true for the foreseeable future.
rdm • August 19, 2013 7:11 AM
You’ve left out advances at other levels of abstraction. The significance of cryptography changes when we build systems which can observe the plaintext.
This is similar, in some respects, to the mathematical advances, but these kinds of systems are not only inevitable, they have existed for a long time and have been subject to the same moore’s law growth as everything else.
Of course, so far, the economics here have been different from civilian economics. I believe we’ve been holding back on civilian growth in this field, while we try to resolve some cultural issues which scare us.
Or maybe I’m just a nutcase?