Summarizing BSI's View on Quantum Technologies and Quantum-Proof Cryptography

In the first article of our series of views on (post) quantum cryptography from various institutions we focus on the post quantum computing recommendations by the German Bundesamt für Sicherheit in der Informationstechnik (BSI). 

Bundesamt für Sicherheit in der Informationstechnik (BSI)

BSI is Germany’s federal cybersecurity authority. This institution’s goal is to promote and enforce the secure use of information and communication technology in business, government and society. It is Germany’s supervisory authority for security of critical infrastructure and digital services information technology. The BSI employs around 1,400 people who work to ensure the secure use of information and communication technology in government, business and society.

The BSI views quantum computers as a serious threat to today’s Public Key Cryptography and therefore evaluated strategies and recommendations on quantum technologies and quantum-proof cryptography.

Cryptography Threats of Quantum Computing

As of right now, there are no quantum computers available that could break cryptographic algorithms being used today. 

But as asymmetric encryption and digital signatures will be broken as soon as the first cryptographically relevant quantum computer is developed (Q-Day) the confidentiality and authenticity of todays protected data is lost instantly. Long term security will fail if protected data is stored today and decrypted on Q-Day (“store now – decrypt later” modus operandi).

BSI’s working hypothesis is that cryptographically relevant quantum computers will arrive during the early 2030s.

Which strategies does the BSI define for “Quantum Security”?

The BSI regards quantum computers as a serious threat for today’s public key cryptography and recommends evaluating measures to switch to a post quantum secure state already today.

There are two methods the BSI recognizes for quantum security:

• Quantum Key Distribution (QKD)
• Post Quantum Cryptography (PQC)

Quantum Key Distribution uses quantum physical effects for secure key distribution, whereas Post Quantum Cryptography defines cryptographic algorithms which are resistant to algorithmic attacks performed on a quantum computer (see Shor’s and Grover’s algorithm for more information).

Which protocols does the BSI recommend for Quantum Key Distribution (QKD)?

Since there are no standardized protocols for QKD yet, the BSI takes a conservative stance and currently does not recommend any of the protocols. However, once standardization is completed, the BSI will evaluate the protocols and give concrete recommendations for protocols, authentication, and application of QKD.

In general, the BSI only sees QKD as suitable only for special use cases (because there are a lot of limitations for practical implementation). 

Which algorithms does the BSI recommend for post quantum cryptography?

In contrast to their view on QKD, the BSI already recommends measures to be taken for PQC ALTHOUGH standardization (by NIST) is not completed yet and will not be completed until 2024. The BSI justifies this with a simple risk assessment:

It is important to mention here that the BSI highly welcomes the NIST standardization process for Post Quantum Cryptography as it defines standards to be used worldwide. They consider a separate standardization process in Europe or Germany to be counterproductive. However, they emphasize that organizations should not wait until standardization is complete (probably in 2024).

The PQC standardization process by the National Institute of Standard and Technology (NIST) in the USA is a currently ongoing process with the goal of selecting and standardizing algorithms for the post quantum age. The process already defined algorithms to be standardized in 2022 and is aiming for a full set of algorithms in 2024.

The Post Quantum Cryptographic algorithms recommended by BSI are based on different fundamentals, which are:

1. Code-based cryptography which is based on the difficulty of decoding general error-correcting codes.

• Recommended algorithm by BSI: Classic McEliece

2. Lattice-based cryptography which is based on the difficulty of solving hard problems in mathematical lattices.

• Recommended algorithm by BSI: Frodo KEM

3. Hash-based cryptography which is based on the security guarantees of the underlying cryptographic hash function.

• Recommended algorithms are the following stateful* algorithms: XMSS and LMS including their multi-tree variants HSS and XMSSMT

Some further side notes:

• Frodo KEM is not included anymore in the NIST standardization process, but it has been excluded because of its efficiency NOT because of its security** and is therefore still valued by the BSI
• Classic McEliece is currently in round 4 of the NIST standardization process
• The BSI recommends the Merkle signatures (XMSS, LMS and their multi-tree variants) for long-term secure signatures. 
• The multi-tree variants of the hash-based signature schemes HSS and XMSSMT are recommended by the BSI if large number of messages has to be signed with the same cryptographic key.

How should the PQC algorithms be integrated according to BSI?

Now that we know the “what”, we will look at the “how” to be quantum-proof from a BSI perspective. In their papers, the BSI outlines several recommendations for organizations on how to address this topic, with the main ones being:

1. Hybrid Cryptography
2. Crypto Agility
3. Perfect Forward Secrecy
4. Upgrading the key length of AES

Hybrid cryptography – Combining classic and post quantum algorithms

As mentioned above, the BSI recommends to already test and use post quantum algorithms, although they have not been standardized yet. Because of the missing cryptanalytic results, they recommend using them only in combination with classic, well studied algorithms. 

Especially in productive systems, BSI gives the recommendation to use the PQC algorithms only in combination with a classic key exchange or key transport protocol based on ECC or RSA. The ECC-based key exchange should be based on NIST or brainpool curves with at least 256-bit key length.

They make an exception for the stateful hash-based signatures, since those are already proven and standardized, they can also be applied alone. 

Crypto Agility – remain flexible so that you can adapt to new development in the crypto world

Because the development of quantum computers turns the crypto world upside down, the BSI sees flexible systems as a necessity. Crypto agility describes the ability to quickly switch from one cryptographic algorithm to another, without long and complicated transition periods. With systems being designed crypto agile, organizations can quickly implement newly recommended and standardized cryptographic algorithms into their infrastructure.

Perfect Forward Secrecy (PFS) as a secure way for key agreement

For secure key exchange of PQ cryptographic keys, the BSI recommends “Perfect Forward Secrecy” as a desired security property. Each session requires a new public key to be generated and distributed and can then be used in combination with a PQC key agreement protocol without PFS.

Upgrading the key length of AES

Although AES as a symmetric encryption method is not the main focus of the quantum threat, the BSI recommends to use long keys, since Grover’s algorithm does not break symmetric encryption but significantly weakens its security. In particular, the BSI recommends upgrading from AES-128 to AES-256.

Summary: BSI emphasizes the need for Crypto-Agility and Hybrid Cryptography

BSI’s goal is to promote the secure use of information and communication technology in business, government and society. Many companies and they have begun to assess and evaluate how susceptible their various data types and systems are to quantum threats. By identifying and evaluating vulnerabilities, security measures may need to be replaced or upgraded and this should allow for a realistic time frame for the implementation. 

For now, BSI recommends that quantum-safe methods should be used in combination with a classical method during the transitional implementation period - also referred to as hybrid cryptography. Because the suitability of key lengths or the security of cryptographic methods, there is a need for crypto-agile solutions. These solutions allow the secure and easy exchange of cryptographic methods or protocols.

The transition to PQC in a crypto-agile environment is essential to thwart the Quantum threat. However, it may be a cumbersome journey that needs a lot of effort and attention.

Start by testing PQC algorithms in your environment!

^{* The cryptographic state has to be handled with care!
** See https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413-upd1.pdf, page 38}

References:

The content of this blog post relies mostly on the documents

BSI TR-02102-1: Cryptographic Mechanisms: Recommendations and Key Lengths (January 9, 2023)
Quantum-safe cryptography – fundamentals, current developments and recommendations (October 2021)