How will quantum computers impact cryptography?
2016-05-01 21:32 by Ian
This post is an effort to short-circuit some FUD regarding the susceptibility of different classes of cryptographic algorithms to attacks made possible by quantum computers.
A 5-qubit computer is big news. Too much gets lost by journalists. Here’s a more-complete picture than most every journalistic outlet at which I've seen this covered…
http://news.mit.edu/2016/quantum-computer-end-encryption-schemes-0303
Symmetric algorithms are mostly safe from quantum because the security is based on a shared key (which might be anything).
Asymmetric, by contrast, relies directly on mathematical relationships between numbers that are publicly-exposed. Such cryptographic strategies will need to be replaced eventually, assuming they are not abandoned entirely.
Quantum factoring systems aren’t on our doorstep quite yet. But one of the quotes in that link above is telling (emphasis mine):
“…you probably don’t want to publicly store your secrets using encryption that relies on factoring as a hard-to-invert problem,”
Shore’s algorithm attacks a specific subset of asymmetric algorithms.
Let’s henceforth denote this subset as asymm{PF} (PF, for “Prime Factorization”). As-opposed to the only other major family of which I am aware: asymm{DL} (DL, for “Discrete Logarithm”).
RSA is asymm{PF}.
ECC and Diffie-Hellman are both asymm{DL}. I can go into Diffie-Hellman at a later time, but it underlies most modern implementations of TLS (among other things). Despite the fact that it uses primes, it is not based on the difficulty of factoring them out of products.
RSA (and asymm{PF} in-general) has been dead to me for many years, even absent quantum. It’s time to ditch it, IMO.
- It’s too-easy to parallelize, and the difficulty is too-close to linear with-respect-to to resources under attacker control (I don’t want to have to re-plan my crypto every time Intel undergoes a process upgrade).
- The usable-fraction of the set required to contain its operands is absurdly-small, making it heavy-to-implement and store.
I’m not aware of a quantum algo that can attack asymm{DL}, but I am personally-convinced it is possible, and when it is invented (if it isn’t already) it will do as much damage to asymm{DL} as Shore’s algo did to asymm{PF}. It just isn’t an issue yet.
Symmetric algos work on entirely different principles. So Shore’s algorithm won’t hurt their strength at all.
At least: not directly.
To the extent that those keys are protected by asymmetric algos, the (far stronger) symmetric classes can be simply bypassed by recovering their keys from an asymmetric implementation that you’ve broken with a quantum attack.
It also might make possible attacks against certain block-modes and stream-ciphers by quickly pruning unlikely state-chains and allowing for key-recovery in shorter-periods than would be possible with classical algorithms. But even in this case, it could only ever be a side-channel attack, and it will almost certainly be trivial to defend against it.
Quantum doesn’t attack the premises of a pre-shared symmetric secret in any way whatever.
Previous: Open ports are not a security hole
Next: Symmetrical asymmetries