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.
ContentsBackground and Introduction to Post Quantum Cryptography Public Key Cryptosystems (PKC) Symmetric Key Cryptosystems - Authenticated Encryption (AE) Random Number Generation Quantum Computers and Quantum Threat Impact of Grover’s algorithms Impact of Shor’s algorithm Post Quantum Cryptography Alternatives for mitigating the Quantum Threat Global standard on PQC & certificates German recommendation US recommendations UK recommendations Preparation for Migration ETSIPQC and FIPS 140-2 validation, and FIPS 140-3 validationSSH Quantum TechnologyReferences
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, and
- Elliptic Curve (ECDH, ECDSA) cryptosystems for signature and key exchange and
- 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
- Session Key Agreement using key exchange for agreeing upon Symmetric Session keys for Authenticated Encryption.
- 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.COM 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). 
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 algorithms are 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.
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.
- 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.
- Digital signatures (aka Authentication)
Attacks again Signatures aim to recover signature keys and to forge signatures used for authenticating data, user, or server by calculating the private signature key they target data integrity and authentication. An attack against signatures can only be launched when CRQC is available (day 1)and the impact depends on the protocol.
Signatures constructed with classical PKC and verified before day 1 are safe. After day 1, 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 often called as Quantum Safe Cryptography (QSC). 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 / Learning with Errors [Kyber, Saber, NTRU], and 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 used 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. In a hybrid mode ,both traditional and PQC algorithms contribute to the key material using a Key Derivation Function (KDF)  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 either CHRYSTALS/Kyber, or Saber for online interactions.
Classical DH may be used instead of ECDH if there is hardware supporting the public key exponentiation operations.
CHRYSTALS/Kyber is preferred over Saber because of being slightly faster . 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.
Digital Signatures/Authentication requires long term keys to be regenerated. These keys are the SSH User Identification Keys, and SSH Host Keys, 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 , , .
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 the use of 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 different these, more so than for conventional PKC . 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 from 2022-2024. These standards establish a new baseline for PQC Key Encapsulation and digital signature algorithms suitable for general use cases.
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.
BSI-TR-02102-1  section 3.2 recommend the use of FrodoKEM or Classic McEliece.
NIST will select the preferred algorithms for various use cases after the PQC competition has concluded. The transition management process is independent of this.
As of May 2021 UK National Cyber Security Center (NCSC)  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.
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 n practice there is the NIST recommended set of PQC algorithms: it is time for early adapters to start 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 describes an organizational process of upgrading systems to PQC . 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 Technology
SSH has been a key player in developing post-quantum cryptography in Finland. The company has also developed their own software solution for protecting sensitive and critical communications. Learn more about NQX that provides quantum-ready protection for critical data in transit.
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.
 Banerjee T & M.A. Hasan: Energy Consumption of Candidate Algorithms for NIST PQC Standards http://cacr.uwaterloo.ca/techreports/2018/cacr2018-06.pdf
 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?__blob=publicationFile&v=10
 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
 National Cyber Security Center: White paper: Preparing for Quantum Safe Cryptography https://www.ncsc.gov.uk/whitepaper/preparing-for-quantum-safe-cryptography
 NIST IR.8309: Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf
 NIST SP.800-56C Rev 2, Recommendation for Key-Derivation Methods in Key-Establishment Schemes https://doi.org/10.6028/NIST.SP.800-56Cr2
 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
 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