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. 

4 June, 2025

"A 4096-bit RSA key, while currently considered very secure, could potentially be broken by a quantum computer in a matter of days or weeks, depending on the number of qubits and the specific algorithm used. Google's research suggests it could be broken in 10 days using 1.4 million noisy qubits. "

Ask yourself how many RSA keys we create in a week for TLS alone.

 

 

AES is Broken!

That is the headline. What does it mean? Should you care?

What does it mean to say that a cryptographic algorithm is broken? Does it mean that the cost of recovering the clear-text without benefit of the key has suddenly fallen to zero? Well, that would qualify, but no, crypto does not fail that way. Does it mean that the cost has fallen to be equal to that of encrypting with the key. Clearly that would qualify, but no, it does not mean that either.

Well, how about the cost has fallen to be equal to the value of the data? How about the time required to recover the clear-text has fallen to less than the life of the data? Well, if either of those had happened, even I might agree that the algorithm was broken. However neither of those has happened either.

For a "standard" algorithm, one might claim an algorithm was broken if the cost of attack was lower than that claimed by the standard.

For example, for the Data Encryption Standard, the DES, the claim was that the cheapest attack was an exhaustive attack against the key, on average, half the time required to try all possible keys. By that standard, the DES is still not broken, low these thirty-five years later. It is true that using a bot farm, one can do a brute-force attack in days. However, for many applications, the life and value of the message are such that no one would spend even that much.

For RSA, the claim is that the cheapest attack is a function of the cost to find the factors of the product of two large primes. While finding the product of two primes is trivial, finding those two numbers knowing only the product is a problem that has challenged mathematicians for a long time.

The time required to try all the DES keys falls as the power of computers goes up but we always know what it is. Similarly, the time required to find the factors of the product of two large primes goes down as computers become more powerful. It might even get cheaper as mathematicians get smarter, but it is unlikely to drop suddenly.

AES is not a standard in the same sense as the DES or RSA. No claim is made for its strength. Rather it is a standard because an authority, NIST, says that it is. It's strength is what it is. We know that the most expensive attack is a brute force attack, but not only has no one ever asserted that there is not a cheaper attack, it has been demonstrated, at least mathematically that there are.. Said another way, by definition, one cannot ever say that it is broken. The best one can say, is "I can find a key this fast."

While some claim that ""Broken" in cryptography is the result of any attack that is faster than brute force"" that simply justifies the claim of the headline. It is not a definition that is meaningful in any sense that a laymen, or even a security professional can understand or use.

By one estimate, the time to brute force a 256 bit key is 5 x (10 )^56 years. What the authors of the paper claim is that they can do it in a mere (10)^51 years. While that may be an interesting improvement, certainly worthy of a paper, even a headline, it does not justify the use of the word "broken" in any practical sense, whatever the authors and headline writers might claim. These authors have simply established the new "standard" cost of attack for the AES.

This is a mathematical assertion that defies any other demonstration. Such an attack, begun at the big bang, would not have completed yet. We call that "strong enough" for security work.

I like cryptographers. Most are very nice people. However, like many such guilds, including security professionals, they have their own special jargon. I appreciate the fact that they do all of these heady calculations for me. However, their security advice is on a par with their medical and legal advice.

Creating a cipher that you yourself cannot break, is relatively easy. All the work is in learning enough about it to be able to predict how much work it would take a body of experts to break it. We call that effort "standardization."

Does all of this mean that our cryptography is "safe," that even nation states cannot read our encrypted data? Not. It has always been my assumption that nation states in general, and the US and Russia, in particular, can read any traffic that they wish.

I am reminded of three colleagues: Phil Zimmerman, who wrote PGP and called it "pretty good;" Adi Shamir, one of the authors of RSA, who wrote, "People do not break crypto, they bypass it;" and Brian Snow, who spent a career at NSA, and who said, "At NSA we spend as much resource on systems as on codes and ciphers."

Algorithms are the strong part of our systems, orders of magnitude stronger than we need them to be. People are the weak point and implementations are in the middle. While it might take the life of the universe to try all possible keys, one might brute force the eight character lock-word used to hide it in a day. Failing that, attackers might bug your systems, suborn your associates, or break your fingers, one after another..

Life would be wonderful it our security was determined by the height of our walls rather than by the guards at our gates, by the strongest link in our chain rather than the weakest. On the other hand, then we might not need security professionals or pay them the big bucks.