Cryptographic Protocols and Quantum Threat

This white paper is indented to help technical decision makers on evaluating how and when their environments need to react to the security threat posed by development of Quantum Computers.

Background and Introduction

Since mid 1990’s Public Key Cryptography (PKC) has become an 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

  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 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

High quality (high entropy) random data is crucial for correct operations of PKC and some symmetric algorithms, and also for the future Post Quantum / Quantum Safe algorithms. Here at SSH Communications Security we 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 has been great improvements on area of Quantum Computing (QC) leveraging physical properties of matter and energy to perform calculations. Quantum Computers allow solving some of the mathematical problems behind current cryptosystems in an efficient manner not possible for today’s classical computers. For cryptography 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 cryptosystems, thereby rendering these systems impotent (Shor’s algorithm).

Together these two algorithms form basis for the Quantum Threat towards current PKC’s. 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 realize one would need a sufficiently large QC with number of good noiseless cubits relatively close to double the public key size in bits (n) and able 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 is fair to say, that we’re still far away from having practical CRQC both in number of qubits and quality of qubits required to implement multi-gate computation. Error correction needed for high fidelity requires large number of additional qubits and supporting infrastructure, making CRQC infeasible today - but as said, progress is fast, and CRQC will realize eventually.


Impact of Grover’s algorithms

Grover’s algorithms can target Symmetric Key Cryptosystems.

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, 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. Accounting this, and 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 QC’s were less expensive than anticipated, problems on parallelizing Grover’s algorithm suggests that AES with longer key size will be safe for a very long time, assuming new algorithms are found.

Relevance of Grover’s algorithm is even more reduced considering current protocol trend of having short symmetric cryptoperiods and dynamic nature of symmetric encryption keys,

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

Impact of Shor’s algorithm

Shor’s algorithm can target Public Key Cryptosystems.

Impact of Shor’s algorithm is far more serious than that of Grover’s, as it reduces 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 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 protocol needs to retain its confidentiality for a long period of time it is important to prepare for appearance of CRQC, as the adversary (eavesdropper) having a 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.
  1. Digital signatures (aka Authentication)
  • Attacks again Signatures aim to recover signature keys and forge signatures used for authenticating data, user, or server by calculating the private signature key they target data integrity and authentication. Attack against signatures can only be launched after having CRQC at time T0 and impact depends on the protocols.

  • Signatures constructed with classical PKC and verified before T0 are safe. After T0, adversary may use CRQC to acquire 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 addresses the Quantum Threat towards Public Key Cryptosystems.

Post Quantum Cryptography

Post Quantum Cryptography (PQC) replaces five decades old PKC algorithms with ones that can circumvent Quantum Threat. PQC 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].

PQC is often called as Quantum Safe Cryptography (QSC).

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

As the PQC algorithms are newcomers, and have not seen so widely studies 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, so hybrid (composite) algorithm suites should be used. In hybrid mode both traditional and PQC algorithms contribute to the key material using a Key Derivation Function (KDF) [6] are 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 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 [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.

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 [4], [7], [8].

Alternatives for 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 - short confidentiality period 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 of PQC algorithms, via 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 [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 from 2022-2024. These standards establish new baseline for PQC Key Encapsulation and digital signature algorithms suitable for general use case.

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 use of FrodoKEM or Classic McEliece.

US recommendations

NIST will select preferred algorithms for various use cases after PQC competition has concluded. The transition management process is independed of this.

UK recommendations

As of May 2021 UK Natinal 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 endorce 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 high priority for transition. Priority systems could be those that process sensitive personal data and are hardest to replace. The standardization of use of PQC protocols is progressing, and there practically is the NIST recommended set of PQC algorithms, it is time for early adapters to start migration process..

Transition to PQC for Key Exchange is an incremental and staged process that can be commenced already during 2022. There is on little 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 an 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 can not get FIPS validation for the time being.

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

SSH.COM Quantum Technology

SSH.COM 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.

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?__blob=publicationFile&v=10

[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.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

[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