Quantum Safe Cryptography
The Problem – Current Cryptography is Vulnerable to Quantum Computing
Cryptography experts believe that by 2030 quantum computers will be advanced enough to cut the strength of symmetric key algorithms (such as AES, 3DES and RC4) by half, and completely break public key cryptography schemes (such as RSA, ECDSA, ECDH, DSS). Before then, industry must replace vulnerable keys and algorithms with ones that are “Quantum Safe”. The length of symmetric keys will have to be doubled at least, and Quantum Safe public key algorithms will have to be created and/or standardized. IBM has been at the forefront of quantum computer R&D and is an important contributor to the effort to create and adopt Quantum Safe cryptography methods.
Symmetric Key Cryptography
From Wikipedia:
Symmetric-key algorithms[a] are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. The requirement that both parties have access to the secret key is one of the main drawbacks of symmetric-key encryption, in comparison to public-key encryption (also known as asymmetric-key encryption).
‘Symmetric’ refers to when the keys used to encrypt and decrypt are the same, or one is easily obtained by transforming the other. Symmetric keys are used to do the bulk of encryption and decryption in many cryptography algorithms. Symmetric keys are also used in trap door hash functions like those used to convert passwords to binary strings before storing. They are susceptible to Grover’s algorithm, a quantum search algorithm that speeds up finding the unique input to a particular instance of a black box function’s output. For instance, if you have an output of a password hashing function and want to know the input (password) that generated it, in a classic brute force attack you would have to try 50% of all possible passwords to have a 50% chance of hitting the known output. Grover’s algorithm provides a quadratic speedup – you only need to try the square root of all possible passwords to hit the known output. So for instance, classically, to brute force a 128 bit key would take up to 2**128 iterations. Grover’s algorithm reduces that to at most 2**64 iterations. Similarly, Grover’s algorithm can find the input hashed with a 256-bit key in 2**128 iterations. This is why the Quantum Safe ‘fix’ for symmetric keys is to simply double the key length. Of course, increasing it further helps future-proof the key against faster processors as well as better Quantum algorithms.
Asymmetric (Public) Key Cryptography
From Wikipedia:
Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of keys. Each pair consists of a public key (which may be known to others) and a private key (which may not be known by anyone except the owner). The generation of such key pairs depends on cryptographic algorithms which are based on mathematical problems termed one-way functions.
‘Asymmetric’ refers to the fact that the key used to decrypt is not the same as, nor can it be practically derived from, the key used to encrypt. In a rudimentary scenario, a sender encrypts the message with the receiver’s published public key. A public key can only be used to encrypt and so is freely available to all. The receiver decrypts the message with the associated private key, which they must not share. Thus the sender is guaranteed that only the intended recipient can decrypt the message. The inverse operation can also be done – the sender can encrypt a message using the sender’s private key, and the message can only be decrypted using the sender’s associated public key. The receiver is thus guaranteed the message is genuine, and so this technique is often used to create digital signatures. By performing these operations sequentially on a message, it is guaranteed to be authentic, uncorrupted, and non-repudiable, as well as confidential – so long as the private keys on both sides remain private. In practice, public keys are often communicated via certificates, and the chain of trust of those certificates is what guarantees that the public keys contained therein are genuine. Asymmetric cryptography is often too slow (because it is CPU intensive) for protection of a large data set and is more commonly used to securely exchange one-time-use symmetric keys that are in turn used to encrypt the large data set. This is called a hybrid cryptosystem. In another type of key exchange (e.g. Diffie-Hellman), each side combines their own private key with the other side’s public key to come up with the same shared secret key which can be used as a key for a symmetric cipher or to encrypt the secret symmetric key. The strength of public key comes from the difficulty of determining the private key from the public key through brute force, because it involves factoring a composite of two large prime numbers. Though it is fairly easy to come up with two 600-digit prime numbers, factoring their 1200-digit composite product N can only be done in sub-exponential time (faster than polynomial time but significantly less than exponential time) using the best classical methods. For instance, in 2019, a 795-bit composite of two primes was factored in hundreds of core-years, and it was estimated that increasing the number of bits to 1024 (a 29% increase) would take 500 times as long. Obviously no matter how fast the classical computer gets, it will always be cheap and easy for key length to stay well ahead of it. But Shor’s quantum algorithm can factor a composite of two primes in polynomial time (specifically, in log N time), and so can easily break public key encryption based on composites of two primes. For example, using Shor’s algorithm, if a quantum computer can factor a 1000-bit composite number in 3 hours, it can theoretically factor a 10000-bit composite in 4 hours, and even a composite number taking up every byte in any modern computer’s central storage could still be theoretically be factored in less than a day. So merely increasing the key’s length won’t ‘fix’ asymmetric key encryption algorithms whose strength depends on the difficulty of factoring a composite of two primes. Thus new Quantum Safe algorithms – ones that require sub-exponential time or greater to crack on a quantum computer – must replace the current non-Quantum Safe ones.
NIST Quantum Safe Recommendations and Standards
In 2016, the US National Institute of Standards and Technology (NIST) called for proposals for Quantum Safe algorithms. Currently they are in Round 3 of the analysis phase. In early 2022 they expect to finish Round 3 and to complete selecting the best proposals and alternates. Then they will start the standardization phase to finalize the selected proposals into draft standards, with final standards expected to be adopted sometime in 2024-5. The Chinese Association for Cryptologic Research has already selected the proposals they will standardize on and is in the standardization phase already.
IBM and IBMers are participating in the NIST process and have several finalist candidates for Quantum Safe algorithms, including key encapsulation mechanism (KEM) algorithms CRYSTALS-Kyber, McEliece, as well as digital signature algorithms CRYSTALS-Dilithium and FALCON. IBM is also participating in one alternate KEM algorithm (SIKE).
NIST is advising to begin planning to replace hardware, software and services that use public key algorithms, and for high security applications, not to wait for the final standards to be released but begin using “hybrid” schemes which combine classical algorithms like RSA with Quantum Safe algorithms such as Kyber or Dilithium.
IBM z16 Leading the Way to Quantum Safety
IBM is working now to leverage Quantum Safe technologies to future-proof customer’s business critical infrastructure and data from quantum computer attacks.
On the hardware side, they are introducing the new PCIe CEX8S Crypto Express Hardware Security Module (HSM) which will add support for Quantum Safe cryptographic algorithms to Common Cryptographic Architecture (CCA 8.0) mode and Enterprise PKCS #11 (EP11) mode. It will also support Quantum Safe Miniboot using dual signatures, Dilithium and ECC. Another hardware feature, the Trusted Key Entry (TKE) workstation, which is used to administer the HSM, will have internal changes that will use Quantum Safe key negotiation and signing.
On the software side, IBM will have new APIs that exploit the new Crypto Express Quantum Safe algorithms. IBM is also looking to embed cryptographic technology at the system level by, for instance, encrypting main memory using Quantum Safe algorithms. Pervasive Encryption is being broadened for more uses within the system (e.g. CF encryption, z/VM paging encryption, and Quantum Safe RACF database encryption). Withing the system itself, internal key management and signing is being enhanced to use hybrid Quantum Safe technology. EKMF key management will be updated to support CRYSTALS Dilithium and Kyber keys using the new Quantum Safe APIs. Finally, on z/VM, support for the new APIs running on virtualized Crypto Express features will be available for z/OS, Linux and VSE guests.
Conclusion
This is intended as an overview of Quantum Safe cryptography and IBM’s most recent efforts to support Quantum Safety in IBM zSystems. There are many details left out, and many more to be decided, but right now everyone can start down the path leading to Quantum Safe computing by taking inventory of their current cryptography techniques and identifying those that are not Quantum Safe. The next step after that is to begin transitioning the most security sensitive applications to use Quantum Safe algorithms. IBM zNext hardware and software solutions can play a central role in the journey to Quantum Safe computing.
Capgemini (CG) develops and maintains IBM’s Connect:Direct for z/OS (CDZ), which currently supports TLS 1.3 and current state of the art encryption. CG is committed to implementing quantum-safe algorithms as they become standardized.
Originally published on the IBM Z LinuxONE Community Blog.