Is crypto-agility the key to quantum-safe security?

Strong cryptography safeguards our data

With ever-increasing digitization in all areas of our business and social lives, more and more sensitive information is being transferred between IT systems and stored for further processing. It is obvious that the confidentiality of this data is of paramount importance in communication networks – no one should be able to read sensitive data transferred from our laptops to a data center.

Strong cryptography ensures that data remains private. A central task of cryptography is to exchange a secure key over an insecure channel. This so-called public-key (also known as asymmetric) cryptography is based on mathematical problems that are simple to calculate in one direction but extremely complex in the other. A well-known example of such trapdoor functions is the prime factorization that underlies the RSA cryptosystem. This method has found widespread use and is utilized for key exchange and message signing. Prime factorization is suitable for cryptographic applications because it is extremely computationally intensive to decompose a large number into its prime factors. In contrast, the inverse operation, i.e., the multiplication of large prime numbers, can be easily performed on ordinary classical computers.

In the past, there have also been successful attacks on symmetric encryption methods that are used for encrypting data rather than exchanging the keys. The Data Encryption Standard (DES), which was widely used at the time, has fallen victim to sophisticated cryptanalysis and increasing computing power. This led to DES being replaced in 2000 by the Advanced Encryption Standard (AES), which has since then become the standard for symmetric encryption.

Attacks on cryptosystems

Cryptographic procedures for key exchange such as RSA are, in the first place, abstract mathematical formulations that must be implemented in software for use in practice. Attacks on cryptosystems are therefore possible from two different directions. On the one hand, flaws can occur in implementing the crypto algorithms, so the complexity of the underlying mathematical problem no longer offers any protection. An example of this would be if the encryption operation’s computation time allows inferences about the key or the plaintext. 

The second type of attack on cryptosystems directly targets the theoretical foundations. If new algorithms can be found that can quickly solve “hard nuts” like the prime factorization mentioned above, the security of the encryption is no longer guaranteed. Such an algorithm has been known for almost 30 years. Named after Peter Shor, Shor’s algorithm makes it possible to break most classical cryptographic algorithms for key exchange. To execute Shor’s algorithm, however, a powerful quantum computer is required. Such quantum computers are the subject of intense research in academia and industry, but the most powerful currently available are still many orders of magnitude from the computational power required to break currently used public-key cryptography. Unfortunately, however, it is possible today to store highly sensitive data encrypted using classical methods on a large scale. This can then be decrypted in the future using a powerful quantum computer. This attack scenario is called “store now – decrypt later” and represents a practical threat that needs to be addressed today. 

Consequently, the advent of quantum computers makes the key exchange procedures in today’s cryptosystems vulnerable to attacks. The AES algorithm used to encrypt the payload data is, however, considered quantum secure if a key with a length of at least 256 bits is used. 

Post-quantum cryptography 

Post-quantum cryptography (PQC), an emerging quantum-safe encryption method, is necessary if highly sensitive data is to remain secure for a long time. Quantum security here means that there is no known efficient algorithm for cracking the process, even on a quantum computer, at this point. In 2016, the US National Institute of Standards and Technology (NIST) launched a project to invite submissions and peer reviews of new quantum-safe methods. After several rounds of evaluation, NIST in July 2022 selected “CRYSTALS-Kyber” for standardization and sent four other algorithms to another round of evaluation. (Interesting side note: The SIKE procedure chosen for further assessment was broken just weeks after moving into the fourth round.)

Standardization of Kyber by NIST is generally expected in 2024. However, even before this standardization, and certainly afterward, there are several hurdles to overcome. In addition to unclear licensing surrounding the use of Kyber, initial implementations of Kyber and all other post-quantum techniques may have a different maturity compared to what classical crypto techniques have achieved in decades of deployment. It must be assumed that hackers may be able to exploit inevitable flaws in the programming. In addition, no market standard has yet been established, as the recommendations of the various national institutes and offices diverge. While NIST has selected the high-performance Kyber cryptosystem, the German Federal Office for Information Security (BSI) recommends the more conservative “Classic McEliece” and “FrodoKEM” methods. NIST only considers these as standardization candidates in the fourth round or, in the case of FrodoKEM, not at all.

Crypto-agility

What conclusions must be drawn for the implementation of today’s cryptosystems? At this point, there is no definitive guidance on which quantum-safe methods are best suited for specific use cases. As a result, it is crucial to have the flexibility to update production systems as new information becomes available.

Modern cryptosystems must therefore embody crypto-agility. This means that cryptographic methods should be developed and deployed in IT systems in such a way that they can be adapted to evolving threat landscapes and cryptographic standards. Even in the event of a weakness in a procedure used, the overall system’s security must not be compromised, and the vulnerability must be patched promptly utilizing trustworthy update mechanisms.

Agile cryptosystems are thus highly complex and require years of expertise in theoretical and practical cryptography to be implemented securely. However, this security technology can protect sensitive data in the long term, even if novel side-channel attacks or even quantum computers are used in the attack.