Blog & News

In this article I am going to highlight some of the issues concerning the current state of post quantum cryptography. This article is written for readers who want a high level overview and are not much concerned with technical details.

The first part explains how security of cryptographic algorithms is determined in theory. Next, the notion of post quantum cryptography is introduced. Eventually, selected aspects if one decides to use post quantum cryptography are highlighted.

This article deals mainly with asymmetric cryptography, as the impact of quantum computers on symmetric cryptography is easier to anticipate. Further, this article is about post quantum cryptography, i.e., cryptography with classical computers under the assumption that the attacker has access to a quantum computer. This is different from quantum cryptography, i.e., cryptography using quantum computers. Quantum cryptography is not treated in this article.

Background on Cryptographic Security

This section gives an overview of the theoretical underpinnings of security in cryptographic systems.

One obvious question is how to measure the security of a cryptographic algorithm. Often, cryptographic algorithms employ a security parameter which is used to tune the security level, i.e., the effort needed to break the algorithm. Intuitively, for an attacker there should be no better algorithm to break a cryptosystem than brute-force, which means trying all keys. The effort of this attack is exponentially in the size of the key. However, using the same cryptosystem with longer keys should not take significantly more time for the user. The main intuition behind the security parameter is now as a measure of key length, as the effort required to break a secure cryptosystem should most often be exponential in the length of the key.

More formally, a cryptosystem is considered secure if the effort of an attacker to break the algorithm increases exponentially, whereas the effort of using the cryptographic algorithm only increases polynomially in the security parameter.

Security in Asymmetric Algorithms

The current approach among cryptographers for asymmetric algorithms is to reduce their security to a known hard problem. Common problems which are assumed to be hard are the factorization of a number into its prime factors, or the computation of discrete logarithms. As there are better algorithms than brute force for solving these problems, the security parameter corresponds to the size of the number which needs to be factorized or the size of the underlying group in which the discrete logarithms need to be computed, respectively. The resulting measurement of security is a qualitative statement like “If problem A is considered to be hard then breaking the cryptographic algorithm is hard”. Or inversely “If the cryptographic algorithm is broken, then solutions to the underlying problem can be computed easily”. However, there are no proofs that solving the underlying problem is in fact hard. The trust placed by the cryptographic community in the complexity of these problems stems from the fact that finding solutions efficiently has eluded researchers for several centuries. For example, the problem of factoring has already been investigated by Fermat in the 17th century.

Note that for a concrete implementation or a standard, a concrete security parameter needs to be chosen. As an example, a security level of 128 bit is currently considered secure. This means that an attacker has to execute approximately 2^128 steps to break the algorithm. According to the NIST recommendations this corresponds to a key length of 3072 bit in RSA, as RSA is based on the factoring problem and thus better algorithms than brute force are available.

Quantum Computers

The faith of the cryptographic community in the complexity of factoring and computing discrete logarithms took some damage when researchers turned their attention to quantum computing. In 1994, Shor proposed an algorithm to factor a number into its prime factors which runs in polynomial (instead of exponential) time. In the same paper, Shor proposes an algorithm to solve discrete logarithms in polynomial time, another problem which was assumed to be of exponential complexity. Consequently, cryptographic algorithms whose security relies on the complexity of factorizing a number or of computing discrete logarithms are broken in theory. These include most asymmetric cryptosystems such as Diffie-Hellman, RSA, El-Gamal, and cryptosystems based on elliptic curves. However, the main drawback of Shor’s algorithm is the need for a quantum computer to execute it. Thus, these types of cryptosystems are only broken if we allow the attacker access to a quantum computer.

A quantum computer is comparable to a classical computer, but uses qubits, i.e., a two-state quantum mechanical system to store information. There are many intermediate states which can be used in the computations in a quantum computer, but as soon as the qubits are measured in the final result, the superposition collapses and only two states are possible. While a quantum computer can execute classical algorithms, there are some algorithms which have a faster implementation on a quantum computer, as the implementation makes clever use of these intermediate states of the qubit.

When executing Shor’s algorithm, of course the quantum computer needs to be “big enough” in the sense, that there need to be enough qubits available. Regarding the security implications this is mainly a practical problem, as the theory deals only with asymptotic statements. To our knowledge the largest number which has been factored by a quantum computer is 56153 which corresponds to an RSA key length of 16 Bits. For this computation 4 qubits have been used. Real world RSA keys of 3072 or 4096 bits are still far out of reach for current quantum computers.

Currently, it is not certain when large enough quantum computers are feasible. However, since quantum computers are only getting better and not worse, research into cryptosystems whose security is based on different, i.e., quantum safe problems is booming. These novel directions in cryptography are treated under the term “post quantum security” or “quantum proof cryptography”. While there are many contenders, there are no standards yet. Nevertheless, some companies are already offering supposedly quantum proof cryptosystems.

A Holistic View on Security

From a theoretical point of view the situation is clear: If an attacker is allowed access to a quantum computer, most currently employed cryptosystems are insecure in the sense that breaking the algorithm requires only polynomial effort. Post quantum cryptosystems are secure under the hardness assumption of their underlying respective problem. Consequently, a switch to quantum proof cryptosystems is needed to enable long term security.

In practice, however, the situation is more nuanced:

If an attacker requires only polynomial effort, the cryptosystem is broken in theory but may not be broken in practice. For example, there is an attack on AES due to Bogdanov et al. which needs less effort than brute force. However, the effort is still high enough such that the attack is impossible with current technology.

Further, cryptographic algorithms in the real world are not broken by attacking the mathematical foundations, as these are the most solid part, but rather the implementation or the usage of the cryptosystem. This is akin to storing treasures in a house. Even if secure doors are used, an attacker can sneak in through an open window. In the real world cryptography is usually the secure door, rather than the open window.

In the following I aim to give an overview of some of the issues surrounding the trade offs associated with current post quantum cryptosystems.

Missing Standards

Currently, there are no standards for quantum proof cryptosystems, yet NIST has initiated a competition to standardize a post quantum cryptosystem. According to their timeline this standard is estimated to be ready in 2022 to 2024.

Beyond fixing the security parameter, a standard usually regulates the data format of the messages and keys. Consequently, the landscape of implementations of quantum proof cryptosystems is very fractionated and encrypted messages may be incompatible between different software, even if the same cryptographic algorithm is used. This leads to the situation of a vendor lock-in, where the costs of switching to a different software later may become substantial.

Patents

A further point impeding the adoption of quantum proof cryptosystems is that many algorithms are encumbered by patents. However, their impact on using post quantum cryptography in practice depends heavily on the type of patent. Patents can cover the whole algorithm or only specific parts of the implementation. In the latter case, a slower but compatible implementation may be available. While only few general points can be made regarding the impact of patents on the adoption of quantum proof cryptography, this point certainly needs to be considered when deciding to use such cryptosystems in practice.

Implementation Risks

Another problem when using post quantum cryptography in production is the lack of a vetted implementation. The main problem is that the security of an algorithm is dependent on the security of its implementation. For example, if different code paths are executed depending on the input data, the algorithm can leak information of its input by observing the timing differences of different runs of the algorithm This can leak sensitive internal information such as key material. There are lots of these attacks against implementations of cryptography such as padding oracle attacks, cache attacks, and other timing attacks.

For classical cryptography there are industry grade implementations such as the OpenSSL library, which is hardened against these attacks through many years of experience. For quantum proof cryptography there are no comparable libraries with a similar level of expertise. Consequently, post quantum algorithms suffer from more risk stemming from an insecure implementation than classical cryptosystems.

Organizational Decisions

Decisions in organizations are not made in a vacuum. Especially, decisions may not always focus on achieving the best solution, but other factors can play important roles as well.

In practice, an employee needs to take responsibility for its decisions towards its manager. Thus, the employee may not be blamed for using a government standard, but for using an experimental quantum proof algorithm if it fails. The same argumentation may be applied by a court in the case of privacy violations due to a data leak. Hence, even though quantum proof algorithms may offer more long term security, employees may be reluctant to adopt them. This argument is not separate but can be seen as a further consequence of the lack of a standard.

Long term Security

One argument for quantum proof algorithms is their long term security. Especially, once attackers can afford quantum computers it is estimated that classical algorithms are not secure anymore. It is important to note that multi decade long term data protection is not important for most organizations to begin with, except, e.g., TS/SCI facilities and the healthcare sector. Most cryptographic data such as TLS handshakes are rather ephemeral. Further, remember that the impact of quantum computing on symmetric cryptography, i.e., encryption, is very well understood, and thus only asymmetric cryptography such as signatures and key exchanges are affected when arguing about long term security.

Current governmental recommendations for long term security suggest using classical algorithms with larger keys. The EU project ECRYPT recommends using elliptic curves with 512 Bits for security for thirty up to fifty years. NIST has the same recommendations for security up to 2030 “and beyond”. Consequently, for industry grade applications classical cryptography should suffice for nearly all applications and there is no urgent need to migrate to post quantum cryptography.

Conclusion

We have given an overview of the notion of security in cryptosystems and have shown that for real world applications, currently there is no need to switch to post quantum cryptosystems. Further we have argued that there are currently many forces preventing adoption of quantum proof cryptography.

However, it is clear that cryptographic attacks will only get better and never worse. Hence, changing to quantum proof cryptosystem will become necessary in the future. Until then we hopefully have a standard and some industry grade software libraries.

~ Henning Kopp