tl;dr: take inventory, plan for migration, execute ASAP
In our previous post “Will Quantum Computers break the Internet?“, we discussed the potential impact of quantum computers on modern security and the estimated timeline for when such computers might become a reality. This post explores the options available for addressing the threat posed by quantum computers.
The Quantum Threat
A short recap: quantum computers pose a significant threat to various applications of public key cryptography in the next 15-20 years, including
- web browsing
- messaging apps like WhatsApp, Signal and Telegram
- smart cards and smart keys
- online banking
- cloud storage
General-purpose quantum computers are expected to break RSA-2048 within 8 hours. However, during the process of standardizing and adopting post-quantum cryptography, new and more effective attacks are likely to be discovered – not only against today’s public key cryptography, but also against the post-quantum alternatives. For instance, recent research has found
- more efficient ways to break RSA-2048
- fault attacks against implementations of the quantum-resistant algorithm Kyber
- attacks against an entire class of quantum-resistant algorithms
Quantum-Resistant Algorithms
There are already two important algorithms for post-quantum cryptography: The National Institute of Standards and Technology selected CRYSTALS-KYBER (key-establishment) and CRYSTALS-Dilithium (digital signatures) for standardization. These algorithms serve as quantum-resistant alternatives to traditional public-key algorithms based on RSA, Elliptic Curves and Diffie-Hellmann.
In contrast to these public-key algorithms, most current symmetric cryptographic algorithms and hash functions are considered secure against attacks by quantum computers. Attacks with Quantum Computers running Grover’s Algorithm are conceivable, but impractical. However, it is recommended to increase the key sizes to prevent such attacks altogether.
For public-key algorithms, increasing the key size can provide temporary relief, but this approach has limitations. Implementing the change takes time, and larger key sizes will eventually become insecure. Furthermore, this strategy incurs performance and memory costs that most devices cannot sustain in the long term.
Getting Started
As outlined by McKinsey, there are three main options to address the threat of quantum computers:
- Adopt Post-Quantum Cryptography (PQC) solutions now
- Retrofit PQC solutions in the future
- Focus only on enhancing traditional encryption protocols
Keep in mind that adopting PQC may not be possible for certain systems outside of your control, such as middleboxes hindering TLS updates for current browsers. Furthermore, although options 2 and 3 have lower costs in the short term, transitioning to PQC later with a “big bang” approach is fraught with uncertainty, and traditional encryption protocols can only be enhanced to a certain extent.
You can already identify which cryptographic algorithms are used in your system’s security measures. For example:
- network connections secured with TLS or SSH
- authentication using JWTs
- encrypted data storage
- digital signatures on certificates or firmware updates
Determine the lifespan of cryptographic material and the secured information. For instance, digital signatures in TLS protect against man-in-the-middle-attacks in real-time. On the other hand, the TLS handshake and data sent over TLS can be intercepted, stored, and decrypted later – if this data still needs to be secure in 20 years, additional measures need to be taken.
Once you have a clear understanding of these components and constraints, you can decide on the most appropriate strategy for each security measure.
Enhancing Traditional Encryption
As previously noted, enhancing traditional encryption is not a permanent solution to the threat posed by quantum computers. A more effective approach is to use algorithms specifically designed to be quantum resistant. As a short-term measure, however, it is advisable to increase the security level wherever possible. For example, RSA key sizes should be at least 3000 bits, while EC key sizes can be increased from 256 bits to well above 500 bits.
Adopting PQC Solutions
The German Federal Office for Information Security (BSI) recommends combining two public-key algorithms into a hybrid encryption scheme to future-proof against quantum computing threats. This approach offers the security benefits of both pre-quantum and post-quantum algorithms, but at the cost of performance. While this migration can be challenging, similar migrations have taken place over the past 20 years and can be managed effectively with careful planning.
A key component for a hybrid encryption scheme is a Key Encapsulation Mechanism (KEM), based on a public-key algorithm.
Key Encapsulation Mechanisms
A KEM offers a simple interface to establish a shared secret between two parties over an insecure communication channel:
generate_key_pair()which returns a key pair consisting of a private key and a public keyencapsulate(public_key)which accepts a public key and returns a tuple consisting of a secret and its opaque encapsulationdecapsulate(encapsulated_secret, private_key)which accepts an encapsulated secret and a private key; if the private key corresponds to the public key used to generate the encapsulated secret, then this method returns the secret corresponding to the encapsulated secret
Two parties Alice and Bob can use this interface to establish a shared secret
- Bob generates a key pair consisting of a private key (which only he knows) and a public key (which Alice also knows)
- Alice passes Bob’s public key to the KEM, returning a secret and its encapsulation
- Alice keeps the secret for herself and sends Bob the encapsulated secret
- Bob passes his private key and the encapsulated secret to the KEM, returning the secret
This interface can be expanded so that Bob can trust that it was indeed Alice who sent him the encapsulated secret:
auth_encapsulate(public_key_receiver, private_key_sender)auth_decapsulate(encapsulated_secret, private_key_receiver, public_key_sender)
These methods return the same types as their unauthenticated counterparts. The main difference is that the encapsulation now contains additional opaque information used to verify the sender’s authenticity during decapsulation. Consequently, Alice needs to generate a key pair as well.
Hybrid KEMs
Since the KEM’s interface is independent of the underlying public-key algorithm, we can use this as a building block to combine two public-key algorithms into a hybrid KEM. The following figure shows an exemplary hybrid encryption scheme for the two parties Alice and Bob who want to establish a shared encryption key:
The above workflow consists of the following steps:
- Alice uses two KEMs to generate secrets s₁ and s₂ and their ciphertexts c₁ and c₂ specific to Bob
- Alice sends c₁ and c₂ to Bob
- Bob decrypts c₁ and c₂ to s₁ and s₂
- Alice and Bob each use a KDF to combine s₁ and s₂ into the shared encryption key
Alice and Bob can now encrypt their communication with the shared encryption key. Note that the security of the shared encryption key deteriorates over time, since c₁ and c₂ can be intercepted, so some sort of session management or key rotation needs to be part of a complete solution. Additionally, the public keys involved in the KEMs ought to be retrieved from a trusted source.
Implementations for the building blocks depend on the specific algorithms (e.g. RSA and Kyber as KEMs, HKDF as KDF) and programming language. neXenio has contributed to expanding the C++ crypto library botan, which documents and implements a vast variety of such algorithms. We are also experimenting with a hybrid encryption scheme in our product neXboard, for which you can find the security concept in our GitHub repository.
Final Thoughts
If you rely on the security of another service provider, you should review their position to PQC adoption and consider alternative providers. Examples of early PQC adopters include Google, CloudFlare, Microsoft, and Amazon.
For further considerations, please refer to the BSI’s recommendations for migrating to PQC.
