Racing the Quantum Hare

What can a German fairy tale tell us about the threat of quantum computing and the fate of post-quantum cryptography? Surprisingly much! The story of an unequal race between a hare and a hedgehog reminds us of the situation that the cryptographic world has found itself in: With the advent of commercially viable quantum computers that can break established cryptographic algorithms, any outside observer would say that the race has already been lost. But that is far from the truth.

Most modern cryptography relies on a simple premise: For encryption algorithms, you use a mathematical problem that is so complex that conventional computers would require decades or centuries to crack. It may not be impossible in theory, but it certainly is in any real-world scenario. When Peter Shor demonstrated how a working quantum computer could factorize large numbers with ease and speed, all of this confidence went out of the window. Though quantum computers were still the stuff of science fiction at the time, the cryptographic community started looking for new hard mathematical problems to build new cryptographic algorithms on, some for the love of math and theory, and some because they saw the actual thread – in the far future.

Nearing the Tipping Point

But quantum computers have now become a real factor to contend with, as working devices, however immature and limited the technology might still be, are already being operated by state and private actors and even available via cloud access. So, is now the right time to panic?

How Serious has the Threat Become?

Indeed, conventional cryptographic algorithms have lost their USP as practically unassailable fortresses. Well-known schemes like RSA are no longer absolute guarantees for security. The technical underpinnings of digital signatures and certificates, like the DSA and ECDSA algorithms or the Diffie-Hellman key agreement, have become vulnerable. Sooner or later, a powerfulenough quantum computer could crack essentially any protocol, or even work back from any public key to compute the matching private key and break through any protection layer.

No Need to Panic

However, all of these threats apply primarily to asymmetric encryption. Symmetric schemes like the popular AES encryption or hash functions like the SHA family are not as easily broken. Quantum computing pioneer Lov Grover did propose an algorithm that would allow quantum computers to work out the secret key for AES encryptions or calculate back from a hash value, but not with the dramatic leaps in performance that are proving so worrying for other cryptographic approaches. It is not years or decades of computing turned into a leisurely afternoon’s work for a would-be hacker, but just a noticeable, but minor acceleration in the calculation process.

For symmetric encryption schemes, the response to the quantum threat is therefore simple: Just up the key length! Switching from AES-128 to AES-256, an easy change even for standard consumer devices, would level the playing field again and return the cryptographic arms race back to its old balance.

Taking Stock

How fares the cryptographic world? Even though symmetric encryption schemes still offer real security, the threat to asymmetric encryption is real, and that has serious implications for our ability to securely exchange encryption keys and maintain integrity and authenticity.

And the arms race is heating up: Modern quantum computers have passed into what is called the NISQ (noisy intermediate-scale quantum computers) stage, as they are large enough to conduct fundamental computation and error correction operations, but still far from sophisticated enough to pose a real threat for actual cryptography. In practical terms, quantum computers are currently working with several dozens to hundreds quantum bits or qubits, but they would need around 2000 logical qubits to break RSA 1024 or EDSA/ECIES 256. And with their inherently error-prone nature, this would translate into more than a million actual qubits to get to the necessary 2000 error-corrected qubits.

The quantum computers of today are also still unwieldy in more than the logical sense: They require massive investments and extremely sophisticated technology, e.g. for cooling the superconducting qubits down to near absolute zero. At the time of writing, any attempt to crack current encryption algorithms would be prohibitively costly and very far from worth the effort, if even technically possible.

Still, Pandora’s box has officially been opened, and quantum computers are constantly evolving and getting better, cheaper, and more easily available. With this prospect, the National Institute of Standards and Technology NIST and Germany’s Federal Office of Information Security BSI are officially recommending that the cryptographic world starts thinking about alternative options. The magic term is: Post-quantum cryptography.

Entering the PQC Arms Race

NIST officially began the new game of cat and mouse in 2016 by standardizing quantum-secure algorithms. The sense of urgency in the industry meant that the complex and usually slow standardization process was accelerated beyond expectations. Candidates were screened in several rounds, a shortlist prepared, and the algorithms selected for standardization announced in 2022.

The thinking was to prepare a set of algorithms that use different mathematical means under the hood. Should any one of them be broken by quantum computers, this would leave other options open and keep the arms race active by the simple and brute principle that underlies much of cryptography: Making it harder, costlier, and simply not worthwhile for attackers. A quantum computer might, at considerable cost in terms of money, manpower, and time, break one algorithm, but that victory would be shortlived, as others are already being put in place by the defenders.

The NIST approach offers some reassurance for the cryptographic community, although one candidate, SIKE, has indeed already been broken, not even requiring a quantum computer at all. This should remind everybody that the threat is serious, acute, and not to be ignored, and that nothing can be taken for granted.

The Hare and the Hedgehog: Speed beats Agility?

In the fairytale of the hare and the hedgehog, the apparent loser hedgehog challenges the obvious winner hare to a race that seems a foregone conclusion. But on race day, the hare darts off, leaves the hedgehog trailing in the dust, nears the finish line – and finds himself face to face with the hedgehog waiting for him. Little did he know that it was the hedgehog’s wife, waiting there all along. Frustrated and hurt in his honor, the hare races back to the starting line and back again, back and forth until he dies from exhaustion.

The hedgehog can be a model for what is needed now in cryptography: Not speed – where the quantum-computer-empowered attacker has the natural advantage – but cleverness and crypto-agility.

If single cryptographic algorithms are likely to fall in the future, the crypto-agile answer would be to have in place other algorithms to take their place. Software architectures need to be designed to allow cryptographic algorithms to be replaced immediately in the case of a breech. When one quantum-safe system is revealed to be not as safe as we had hoped, migrating to another system should be an obvious and immediate option.

Crypto-agility calls for more than flexibility. It needs a new way of developing software, as new performance tradeoffs need to be made, new algorithms or entire protection systems need to be introduced that require more work in terms of protecting against side-channel attacks or all the other factors that one could consider the soft underbelly of cryptography. And as the threat still seems so far-off and unreal, developers might be wary of switching outright to real quantum-safe algorithms. Ideally, they should allow for a combination of conventional and quantum-safe cryptography to cover all possibilities.

I’m Already There

“I’m already there”, the hedgehog’s wife taunted the hare. Post-quantum cryptography needs to be able to say the same: When the quantum tipping point is reached, it has to already have its house in order. Now is the right time to start preparing your organizations, your cryptographic choices, and your software architectures for the post-quantum moment.