Post-Quantum Cryptography: Preparing for the Future of Security

The rise of quantum computers poses a significant threat to current cryptographic systems. These powerful machines could potentially break the encryption algorithms we rely on today to secure our data and communications. This article explores the need for post-quantum cryptography, alternative cryptographic solutions being developed, and the challenges of implementing them in real-world applications.

by Johann-Philipp Thiers

Quantum Computers: A New Threat to Cryptographic Security

Quantum computers are getting more and more powerful every year, pushing the boundaries of what was once thought to be possible in computation. Although there are currently no quantum computers that pose a threat to cryptographic systems, the rapid advancements in this field suggest it may only be a matter of years before they become a reality. This impending possibility necessitates proactive measures, as many systems today rely on cryptographic security that needs to remain robust for decades.

The fundamental difference between quantum computers and conventional computers lies in their basic units of information. Conventional computers operate with bits, each representing either a one or a zero. In contrast, quantum computers use qubits, which can exist in a superposition of both one and zero simultaneously, thanks to the principles of quantum mechanics. This unique property enables quantum computers to process certain complex problems much more efficiently than classical computers. However, it's important to note that this advantage does not extend to all computational problems.

The Risk to Current Cryptographic Algorithms

While not all problems can be solved efficiently with quantum computers, there are some problems for which all conventional algorithms require exponential time, whereas quantum algorithms require only polynomial time relative to the bit length. Unfortunately, some of those form the backbone of most of today’s security concepts, mainly the Rivest-Shamir-Adleman (RSA) algorithm and the elliptic curve cryptography (ECC).

The most prominent cryptographic algorithms are symmetric encryption algorithms, these can be compared to a safe, which can be locked with a number combination and only be unlocked with the same number combination. For data storage, this is often sufficient, but problems arise in the case of data transmission. In this case, Alice can lock the data in a safe, which is shipped to Bob. However, Alice needs to tell Bob the combination of the safe, without allowing any eavesdropping.

To solve the issue, we use so-called public-key cryptography. The main difference to symmetric cryptography is that each entity has a key pair consisting of a public and a private key. If some data are encrypted with the public key, they can only be decrypted with the corresponding private key. With such a system Alice can encrypt the combination of the safe with Bob’s public key, and only Bob can decrypt them. The security of these cryptographic algorithms typically relies on one-way functions, i.e., functions that are (relatively) easy to compute in one direction but extremely hard in the inverse direction. But for all commonly used algorithms, this inverse can be solved relatively easily with a sufficiently powerful quantum computer.

Exploring Alternative Cryptographic Solutions

Due to the dawn of quantum computers, we need some alternative cryptographic algorithms for public-key encryption, key exchange, and digital signatures. Note, that some concepts, which have been around for some decades are believed to be secure even against quantum computers. However, due to their inefficiency compared to RSA and ECC, these were barely applied.

Hash-Based Signatures: Strengths and Limitations

Hash-based Signatures are digital signature algorithms based solely on the one-wayness of cryptographic hash functions. Cryptographic hash functions are functions, which given an input of arbitrary length produce an output of constant length, which has no recognizable connection to the input. However, they are designed such that changes to only a single bit of the input lead to a completely different output. The most important property of a hash function is that it is impossible to obtain the input when given the output of the hash function.

Hash-based signatures are built upon Winternitz One-Time Signatures (WOTS), which allow for only a single signature per key pair. However, as the receiver verifies the signature against a trusted public key, this means that for each signature a public key needs to be transported in a trusted manner, i.e., with a digital signature. However, if we use a binary hash tree, i.e., a binary tree structure, where each node is the hash of its two children, we can use the tree’s root as a long-term public key and its leaves as private keys use for signing a message. This way we can verify multiple signatures against the same public key, but the amount is still limited. Hash-based signatures are also very large, which may lead to a significant communication overhead, depending on the use case.

While hash-based signatures are well-known and trusted, and some are already standardized, they are fairly inefficient and allow only for a limited number of signatures. Hence, there is a need for alternative algorithms.

NIST's Efforts in Standardizing Post-Quantum Cryptographic Schemes

To find alternatives to the few standardized post-quantum secure public-key algorithms the National Institute of Standards and Technology (NIST) started a competition in 2016 to find and standardize the best post-quantum cryptographic schemes. This competition is ongoing, but some algorithms have already been chosen, and the first final standards are published.

The submissions for the NIST challenge were based on different mathematical problems, such as some problems over lattices or problems in error correction coding, but there was also a submission for a modern hash-based signature scheme.

The most prominent algorithms selected for standardization are the CRYSTALS-Kyber and -Dilithium lattice-based public-key encryption (PKE) and digital signature schemes, which use the same underlying arithmetic for both schemes and all security categories. They are relatively efficient, and the use of the same arithmetic allows for small hardware implementations. The standards for those schemes (NIST FIPS 203 ML-KEM & 204 ML-DSA) have already been published, used in some real-life tests, and implemented in multiple cryptographic libraries. These algorithms are also part of the NSA’s Commercial National Security Algorithm Suite (CNSA) 2.0.

The most efficient post-quantum secure public-key algorithms are the modern ones, which on the other hand, have the disadvantage that we lack analysis of their secure implementation. Hence, many security agencies, such as the German BSI, do not yet recommend relying only on those but implementing them in parallel to the conventional algorithms, such that both need to be broken by an attacker to break the hybrid system.

Real-Life Tests and Use-Cases for Post-Quantum Cryptography

As we saw, there are use-cases that require post-quantum cryptographic algorithms. However, as these algorithms are less efficient, one should always review which use cases really need them, and which could be implemented using symmetric cryptography.

Simplified, we can say that any data transmission requires some form of public-key cryptography, which needs to be updated to post-quantum secure alternatives. However, there are use-cases that currently apply public-key cryptography but could actually do without it.

Let us consider secure firmware updates and secure boot. The secure firmware updates require data transmission and cannot be done without public-key cryptography. A firmware update needs to be signed by the vendor such that the device can verify its authenticity. Depending on the use case the secure boot could use the same signature by the vendor, however, if hash-based signatures are applied (as required by CNSA 2.0) this would require a significant overhead in storage for the firmware and would slow down the boot procedure due to relatively slow signature verification.

On the other hand, if the device has a secure symmetric key, which can only be known by the device and only if the device is in a secure working state (as provided by the Trusted Computing Group’s Device Identifier Composition Engine (DICE)). The device could verify a hash-based signature on a firmware update and after applying the update sign the new firmware using symmetric alternatives (HMAC). This way the boot procedure would be significantly faster, and the storage required for the firmware would be lower due to much smaller HMAC digests instead of hash-based signatures.

Note, that such symmetric alternatives may require very secure handling of long-term symmetric keys. The TCG DICE concept mentioned earlier may help with that, as the symmetric keys are never stored, but only generated at runtime. This concept also allows to distinguish between different working states, e.g., when debugging is enabled, the device derives a different symmetric firmware signing key, which is not trusted after debugging is disabled.

Challenges and Considerations for Embedded Applications

In the past years, there were multiple real-life tests of post-quantum cryptography, such as the TLS post-quantum experiment by Cloudflare and Google in 2019. In this experiment, they implemented two post-quantum key exchanges in Cloudflare’s edge servers and Chrome Canary clients and integrated them into their TLS stack. With this experiment, they could evaluate the performance of hybrid-TLS on a large scale.

Such tests lead to an increased interest in post-quantum cryptography, which is a positive development, as companies think about their own transition. However, this increased interest was also seen in embedded security applications, such as authentication keys or IoT devices. The problem with embedded security applications is that they typically have very limited resources, especially considering memory, and those devices often require hardware acceleration to perform public-key cryptographic algorithms in a timely manner.

Another problem is that for many use cases, such as FIDO authentication keys, there are not even draft standards for the protocols. Until such standards are available only evaluation tests are possible. Interoperability is another issue, especially when considering industrial applications. In such applications the devices are used for such a long time, that there are instances where even the data encryption standard (DES) is still in use despite NIST’s withdrawal in 2005. Hence, for applications where interoperability is required the transition might take a long time.

The Importance of Early Transition to Post-Quantum Cryptography

Despite the possibly long transition period, it is key to consider the transition early on. Only if one knows the assets and the cryptography currently used to protect these assets a smooth and timely transition is possible. In many cases, a transition is fairly easy due to software updates including post-quantum cryptography, but for highly constrained embedded devices this may not be possible. If such a software update is not possible but the existing device should remain in use, an upgrade with an external hardware security module in the form of an SD card or USB drive may be possible.