The Coming Quantum Computing Crypto Apocalypse

Modern media, both fact and fiction, loves the Apocalypse and the Dystopian future.  The Quantum Apocalypse is just one example but one close to the subject of this blog.  It posits that the coming revolution called quantum computing will obsolete modern encryption and destroy modern commerce as we have come to know it.  It was the hook for the 1992 movie Sneakers starring Robert Redford, Sydney Poitier, Ben Kingsley, and River Phoenix.

This entry will tell the security professional some useful things about the application of Quantum Mechanics to information technology in general, and Cryptography in particular, that will help equip him for, and enlist him in, the effort to ensure that commerce, and our society that depends upon it, survive.  Keep in mind that the author is not a Physicist or even a cryptographer.  Rather he is an octogenarian, a computer security professional, and an observer of and commentator on the experience that we call modern Cryptography beginning with the Data Encryption Standard.

For a description of Quantum Computing I refer you to Wikipedia.  For our purpose here it suffices to say that it is very fast at solving certain classes of otherwise difficult problems.  One of these problems is to find the factors of the product of two prime numbers, the problem that one must solve to find the message knowing the cryptogram and the public key or the private key knowing the message, the cryptogram, and the public key in the RSA crypto systems.

This vulnerable algorithm is the one that we rely upon for symmetric key exchange in our infrastructure.  In fact, because it is so computationally intensive, that is the only thing we use it for.

In theory, using quantum computing, one might find the factors almost as fast as one could find the product, while the cryptographic cover time of the system relies upon the fact that the former takes much longer than the latter.  Cryptographers would certainly say that, by definition, at least in theory, the system would be "broken."  However, the security professional would ask about the relative cost of the two operations.  While the former can be done by any cheap computer, the latter can only be done quickly by much more rare and expensive "quantum" computers.

Cryptanalysis is one of the applications that has always supported cutting edge computing. One of the "Secrets of ULTRA" was that we invented modern computing in part to break the Enigma system employed by Germany.  ULTRA was incredibly expensive for all that.  While automation made ULTRA effective, it was German key management practices that made it efficient.    On the other hand, the modern computer made commercial and personal cryptography both necessary and cheap.

One can be certain that NSA is supporting QC research and will be using one of the first practical implementations for cryptanalysis.  They will be doing it literally before you know it and exclusively for months to years after that.

Since ULTRA, prudent users of cryptography have assumed that, at some cost, nation states (particularly the "Five Eyes," Russia, China, France, and Israel) can read any message that they wish. However, in part because the cost of reading one message includes the cost of not reading others, they cannot read every message that they wish.

The problem is not that Quantum Computing breaks Cryptography, per se, but that it breaks one system on which we rely.  It is not that we do not have QC resistant crypto but that replacing what we are using with it will take both time and money.  The faster we want to do it, the more expensive it will be.  Efficiency demands that we take our time; effectiveness requires that we not be late.

By some estimates we may be as much as 10 years away from an RSA break but then again, we might be surprised.  One strategy to avoid the consequences of surprise is called "crypto agility."  It implies using cryptography in such a way that we can change the way we do it in order to adapt to changes in the threat environment.

For example, there are key exchange strategies that are not vulnerable to QC.  One such has already been described by the Internet Engineering Task Force (IETF).  It requires a little more data and cycles than RSA but this is more than compensated for by the falling cost of computing.  It has the added advantage that it can be introduced in a non-disruptive manner, beginning with the most sensitive applications.

History informs us that cryptography does not fail catastrophically and that while advances in computing benefit the wholesale cryptanalyst, e.g., nation states, before the commercial cryptographer, in the long run they benefit the cryptographer orders of magnitude more than the cryptanalyst.  In short, there will be a lot of work but no "Quantum Apocalypse."  Watch this space.