Quantum-Safe Cryptography And the Quantum Threat

This article is intended to help technical decision-makers on evaluating how and when their environments need to react to the security threat posed by the development of quantum computers. It also explores how post-quantum cryptography (PQC) / quantum-safe cryptography (QSC) and quantum-safe algorithms can help mitigate risks.

 

Background and Introduction Post-Quantum Cryptography 

Since mid 1990’s Public Key Cryptography (PKC) has become a basic building component of global communication digital infrastructure. Protocols like TLS (Transport Layer Security), SSH (Secure Shell), and IPsec (IP security) support applications that are important to our economy, our security, and our way of life, such as mobile phones, banking, internet commerce, social networks, cloud computing, and connected devices.

In addition to using PKC, these communications protocols utilize symmetric key encryption cryptosystems, such as Authenticated Encryption, and Random Bit Generators.

Public Key Cryptosystems (PKC)

Most communication protocols rely on Public Key Cryptographic (PKC) functions: public key encryption, digital signatures, and key exchange to enable scalability and usability by removing need for prior key agreement before communications. Currently these functions are primarily implemented using the

• RSA (Rivest-Shamir-Adleman) cryptosystem for signatures and encryption
• Elliptic Curve (ECDH, ECDSA) cryptosystems for key exchange and signatures
• Diffie-Hellman (DH) key exchange

Collectively these are called as Classical PKC. The security of these algorithms depends on difficulty of number theoretic problems such as Integer Factorization and the Discrete Logarithm Problem over various groups, and the theory behind these systems was derived between late 1960’s and early 1980’s.

On online communications security application domain these algorithms are used for

1. Session Key Agreement using key exchange for agreeing upon Symmetric Session keys for Authenticated Encryption.
2. Peer Authentication using digital signatures provides Identification, Access Control, and Data Origin authentication.

Symmetric Key Cryptosystems - Authenticated Encryption (AE)

Authenticated Encryption (AE) is used to protect utility data while in transit.

AE works by enciphering the secret plaintext data with the session encryption key using a Cipher function, such as Advanced Encryption Standard (AES), and further authenticating the encrypted data with a Message Authentication Code (MAC) - which may be a keyed Hash MAC (hmac-sha2-512) or may be combined with encryption as is done in case of AES-GCM - producing an authenticated ciphertext. The same session key can be used to decrypt the data and verify that it was not altered during transit.

Random Number Generation (RNG)

High quality (high entropy) random data is crucial for correct operations of PKC and some symmetric algorithms, and also for the future Post-Quantum Cryptography/ Quantum-Safe Cryptography algorithms.

We at SSH believe classical Deterministic Random Bit Generators (DRBG) are good for years to come when properly seeded during run-time. Seeding may be performed from devices based Quantum Mechanics, although most of the time classical environmental noise is sufficient.

For some use cases - such as AES-GCM nonces that require collision resistance - RNG may need to be replaced with a deterministic function over data being encrypted to avoid encrypting different data with the same nonce.

Quantum Computers and Quantum Threat

Recently there have been great improvements on the area of Quantum Computing (QC) which means leveraging the physical properties of matter and energy to perform calculations.

Quantum Computers allow solving some of the mathematical problems behind current crypto systems in an efficient manner not possible in today’s classical computers. From cryptography's point of view, the following algorithms are particularly interesting:

• Grover’s algorithm - Lev Grover described an algorithm allowing a QC to perform a brute force key search using quadratically fewer steps than would be required classically (Grover’s algorithm)
• Shor’s algorithm - Peter Shor showed that QC can efficiently solve integer factorization and and discrete logarithm problems used on existing public key crypto systems, thereby rendering these systems impotent (Shor’s algorithm).

Together these two algorithms form the basis of the Quantum Threat towards current PKCs. When used within a powerful Quantum Computer they will put many forms of modern communication — from key exchange  to encryption to digital authentication— in peril.

For the Quantum Threat to become real, it would need a sufficiently large QC with number of good noiseless cubits relatively close to double the public key size in bits (n) and the ability to implement a circuit with 64*n^3*lg(n) gates. Such computer is called a Cryptographically Relevant Quantum Computer (CRQC). [3]

At time of writing it is fair to say that we’re still far away from having practical CRQC both in number of qubits and the quality of qubits required to implement multi-gate computation. The level of error correction needed for high fidelity requires a large number of additional qubits and a supporting infrastructure, making CRQC unfeasible today - but as said, progress is fast, and CRQC will become viable eventually.

Impact of Grover’s algorithms

Grover’s algorithms can target Symmetric Key Crypto systems.

Grover’s algorithm for key search suggests that an attacker with CRQC could break a symmetric cipher with a key up to twice as long as without QC. However Crystof Zalka proved in 1997 that to obtain the full quadratic speedup, the algorithm must be performed in series. In the real world, where attacks on cryptography use massively parallel processing, the advantage of Grover’s algorithm will be smaller.

Taking this into account along with the cost of building CRQC it is quite likely that Grover’s algorithm will provide only little or no advantage in attacking AES, and AES 128 will remain secure.

Even if QCs were less expensive than anticipated, the problems on parallelizing Grover’s algorithm suggests that AES with a longer key size will be safe for a very long time, assuming new attack vectors are not found.

The relevance of Grover’s algorithm is even more reduced considering the current protocol trend of having short symmetric cryptoperiods and the dynamic nature of symmetric encryption keys.

According to U.S. NIST and UK National Cyber Security Center (NCSC), respective Governmental entities may continue to use AES with key sizes 128, 192, or 256 bits until further notice despite Grover’s algorithm.

To meet compliance, AES 256 may be required. For example, the U.S. Commercial National Security Algorithm Suite 2.0 mandates 256 bit AES keys to be used for all classification levels.

Impact of Shor’s algorithm

Shor’s algorithm can target Public Key Cryptosystems.

The impact of Shor’s algorithm is far more serious than that of Grover’s, as it reduces the time complexity of Integer Factorization and Discrete Logarithm from sub-exponential to polynomial, and targets keys that can have long cryptoperiods.

The CRQC running Shor’s algorithm can be used to attack two aspects on the application protocols in the order of importance.

1. Key Exchange (aka Key Agreement)

• Attacks against Key Exchange aim to recover the session keys used for encrypting data and therefore are attacks towards data confidentiality.
• If the data transferred over a protocol needs to retain its confidentiality for a long period of time, it is important to prepare for the emergence of CRQC. This is because an eavesdropper that has read access to an encrypted session today can record the data, and later, when CRQC’s have evolved, use one to recover the session key and get access to the data.

2. Digital signatures (aka Authentication)

• Attacks against Signatures aim to recover signature keys and to forge signatures used for authenticating data, user, or server by calculating the private signature key. These attacks target data integrity and authentication. An attack against signatures can only be launched when CRQC is available (day one) and the impact depends on the protocol.

• Signatures constructed with classical PKC and verified before day one are safe. After day one, the bad actor may use CRQC to acquire a signature key and use that to sign arbitrary documents still verifying correctly - as if the original key had been disclosed. Classical PKC Signatures will not be usable for their purpose.

Post-Quantum Cryptography or Quantum-Safe Cryptography addresses the Quantum Threat towards Public Key Cryptosystems.

Post-Quantum Cryptography

Post-Quantum Cryptography (PQC) is Quantum-Safe Cryptography (QSC) designed to be quantum-safe and operate on existing computers and networks. PQC replaces PKC algorithms already five decades old with ones that can resist the Quantum Threat.

PQC (or QSC) algorithms are built on problems that are hard for the Quantum Computers, and they are executed on classical computers. Examples of such algorithms are based on problems of Lattice such as Modulo Learning With Errors [Kyber] , Modulo Learning with Rounding [Saber], Ring Learning With Rounding [NTRU] and Learning With Errors [FrodoKEM], or problems of codes such as Goppa codes [Classic McEliece].

New applications could be built entirely using PQC algorithms, but the existing applications need to transfer to new cryptography in an incremental and managed manner. To ease the transition, cryptographic agility - the ability to use mixed algorithm suites - is needed.

As PQC algorithms are new, and have not been as widely studied as their traditional counterparts, there is an inherent risk that they may contain flaws that make them less secure to traditional cryptanalysis.

To mitigate this risk, hybrid (composite) algorithm suites should be used whenever possible. In a hybrid mode, both traditional and PQC algorithms contribute to the key material using a Key Derivation Function (KDF) [6] that is well studied. The resulting key is at least as hard to break as the strongest composite.

Both PKC and PQC algorithms in Hybrid Key Exchange use Ephemeral (temporary, one-time) key pairs. We recommend a combination of ECDH and CRYSTALS-Kyber for online interactions.

Classical DH may be used instead of ECDH if there is hardware supporting the public key exponentiation operations.

CRYSTALS-Kyber is preferred over other lattice-based algorithms for being faster [1]. Additional algorithms may be implemented for constrained systems or to meet external requirements and interoperability needs.

As described earlier, there are two distinct PKC problems to solve.

Correcting problems in Key Exchange is urgent, but fortunately rather straightforward, and easy to implement. Also adopting the hybrid approach provides additional assurance so there is no reason to delay.

Digital Signatures/Authentication requires long-term keys to be regenerated. These keys include the SSH User Identification Keys/Certificates, and SSH Host Keys/Certificates, and TLS Server/User public key certificates, and IPsec device certificates.

To further complicate the issue these keys may be enclosed within Public Key Certificates issued by external Certificate Authorities (CA), whose keys shall also need to be redone - full Post-Quantum Identification solution requires industry-wide effort [4], [7], [8].

Alternatives to Mitigating the Quantum Threat

Quantum Key Distribution (QKD) addresses the Key Agreement problem via Quantum Mechanics. QKD requires specialized hardware and networking resources. It can be seen as a partial expensive point solution, but not viable for the Internet scale or general purpose use.

Classical Key Agreement and Authentication can be augmented by using pre-placed symmetric keys that are mixed into key using KDF auxiliary input data.

Pre-placing these keys creates additional key management and usability problem nullifying the upsides of PKC - therefore this solution is not suitable when communications are needed without prior agreement and arrangements.

For short term data protection - with periods of short confidentiality or only integrity requirement, such as measurements and actions on IoT and OT domain - the Quantum Threat towards Key Exchanges can be mitigated by having short term sessions with Classical Key Exchange, or having long term sessions rekeyed frequently.

Overall the best mitigation is to gradually move to use the PQC algorithms via a Hybrid mode.

Global standard on PQC & certificates

Many algorithms for PQC have been proposed and there is a wide variation in performance characteristics between these, more so than for conventional PKC [5]. This means that some algorithms will be more suited to particular use-cases than others.

Also there is an expanding set of requirements for cryptography, including deployment in resource constrained devices, and therefore it is unlikely there will be a single algorithm suitable for all applications.

NIST standards for quantum-safe cryptography will be available between 2022-2024. These standards establish a new baseline for PQC Key Encapsulation and digital signature algorithms suitable for general use cases.

In 2022 NIST selected the first public-key encryption and key-establishment algorithm that will be standardized: CRYSTALS–KYBER. The NIST Fourth Round selects the alternate KEM(s) based on different underlying mathematical problem.

The NIST preferred signature algorithm after Third Round is CRYSTALS-Dilithium and the alternates were selected as well. However, NIST is looking for new submissions for alternate signature algorithm candidates during the fourth and likely final round.

Standards bodies such as NIST and ETSI are working with industry to develop guidance for the transition to PQC, which will allow organizations to mitigate risks in PQC transition effectively.

German recommendation

BSI-TR-02102-1 [2] section 3.2 recommend the use of FrodoKEM or Classic McEliece. This recommendation is unchanged even after NIST no longer considers the conservative lattice-based algorithm FrodoKEM as potential alternate key-establishment algorithm.

US recommendations

As of July 2022, NIST has selected CRYSTALS-Kyber and CRYSTALS-Dilithium as the preferred algorithms for standardization. NIST will select the preferred and alternate algorithms including recommended parameters for various use cases after the PQC competition has concluded.

The U.S. Commercial National Security Algorithm Suite 2.0 requires Level V parameters, that target 256-bit security, for all classification levels. Migration from current CNSA 1.0 to CNSA 2.0 is expected in 2025-2030.

The transition management process is independent of the standardisation efforts. In 2021, US Department of Homelands Security together with NIST published a guideline Preparing for post-quantum cryptography. By May 2023, U.S. government agencies are required to provide a full inventory of active cryptographic systems of high-priority assets and systems.

Legislation like Quantum Computing Cybersecurity Preparedness Act mandates even more ambitious timeline for the Quantum-Safe journey. 

UK recommendations

As of May 2021, UK National Cyber Security Center (NCSC) [4] states:

NCSC recognises the serious threat that quantum computers pose to long-term cryptographic security. QSC using standards-compliant products is the recommended mitigation for the quantum threat, once such products become available.

• NCSC does not endorse QKD for any government or military applications.
• NCSC does not endorse any particular PQC algorithm at the moment.
• NCSC advises on the deployment of suitable mitigation for long term secret data.
• NCSC advices to wait for standardized and interoperable set of algorithms.

NCSC guidance for quantum-safe algorithms will follow the outcome of the NIST process by recommending specific algorithms for representative use cases.

Preparation for Migration

Right now, large organizations should factor the Quantum Threat into their long-term roadmaps, and conduct investigation to identify which of their systems will be a high priority for transition.

Priority systems could be those that process sensitive personal data and are hardest to replace. The standardization of the use of PQC protocols is progressing, and in practice now that there is the NIST recommended first set of PQC algorithms: it is time for early adapters to start the migration process.

The transition to PQC for Key Exchange is an incremental and staged process that can be commenced already during 2022. There is some risk - as always when new software versions are deployed - but with proper hybrid implementation the security concerns and operational aspects are limited.

Transition to full PQC is a complex and expensive process that must be planned and managed with care. There are risks to security as systems and cryptographic keys are changed, and risks to business continuity if there are unforeseen dependencies on said components that require replacement.

ETSI

ETSI describes an organizational process of upgrading systems to PQC [7]. This document provides pointers to other related ETSI specification documents.

PQC and FIPS 140-2 validation, and FIPS 140-3 validation

FIPS 140 validation does not cover PQC algorithms. These algorithms cannot get FIPS validation for the time being.

The FIPS 140 series cryptographic of validation allows additional inputs for the validated key derivation functions. The PQC algorithms are used for generating such inputs, and therefore the use of PQC is allowed on FIPS-140 validated cryptosystems.

SSH Quantum-Safe Technology

SSH Communications Security has been a key player in developing post-quantum cryptography in Finland. The company has also developed their own software solutions for protecting sensitive and critical communications. Learn more about NQX that provides quantum-safe protection for critical data in transit in Ethernet and IP networks, application layer protection with Tectia Quantum Safe Edition for securing data in transit in TCP/IP networks and SSHerlock for post-quantum resilience discovery and audit tool that aids in transitioning to Quantum-Safe security posture in existing Secure Shell estate.

We also recommend learning why Financial Institutions need to start protecting against the quantum threat with quantum-safe algorithms today. Click the banner below to read more.

References

[1] Banerjee T & M.A. Hasan: Energy Consumption of Candidate Algorithms for NIST PQC Standards http://cacr.uwaterloo.ca/techreports/2018/cacr2018-06.pdf

[2] BSI TR-02102-1: Technical Guideline: Cryptographic Mechanisms: Recommendations and Key Lengths https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.pdf

[3] Craig Gidney, Martin Ekerå: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits https://www.researchgate.net/publication/333338015_How_to_factor_2048_bit_RSA_integers_in_8_hours_using_20_million_noisy_qubits

[4] National Cyber Security Center: White paper: Preparing for Quantum Safe Cryptography https://www.ncsc.gov.uk/whitepaper/preparing-for-quantum-safe-cryptography

[5] NIST IR.8413: Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf

[6] NIST SP.800-56C Rev 2, Recommendation for Key-Derivation Methods in Key-Establishment Schemes https://doi.org/10.6028/NIST.SP.800-56Cr2

[7] ETSI TR 103 619 V1.1.1 (2020-07) CYBER; Migration strategies and recommendations to Quantum Safe schemes https://www.etsi.org/deliver/etsi_tr/103600_103699/103619/01.01.01_60/tr_103619v010101p.pdf

[8] NIST CSWP.04282021, Getting Ready for Post-Quantum Cryptography: Exploring Challenges Associated with Adopting and Using Post-Quantum Cryptographic Algorithms https://doi.org/10.6028/NIST.CSWP.04282021