CRYSTALS-Kyber for Post Quantum Cryptography demystified

This article is not intended for hard-core mathematicians or cryptographers, instead for the mere mortals among us who, however, don’t want to pass over astonishing things in complete ignorance.

So then, let’s give it a go. You might remember that many experts believe that much of our daily security in communications (including our banking transactions) will one day be broken by the use of large, powerful quantum computers.

What the problem is today

The problem is that many communication protocol stacks use asymmetric encryption as part of a Public Key Encryption system (PKE). A PKE system involves a private secret key (sk) and a public key (pk).

Say a secure connection shall be established between parties Alice and Bob (or my web browser and one of my bank’s servers) where Alice doesn’t know Bob in advance and there is no secure connection between them in the first place. Then the parties can use for example the Diffie-Hellman key exchange method to jointly establish a shared secret key (ss). Once both parties have computed that same secret key, they can use it subsequently to encrypt and decrypt sensitive communication data. Job done.

The trick of the Diffie-Hellman key exchange mechanism is that it involves for each party a private secret key sk from which the party privately derives a public key pk which the party shares with the other one (or the general public if you like) over an insecure channel. Alice then derives the shared symmetric key using her private key and Bob’s public key. Bob follows an equivalent step on his side and ends up with the same symmetric key, which is therefore now shared. Voila!

This procedure is secure because it’s de facto impossible for an attacker to find the private keys and the shared secret key from the public keys using classical computers. An attacker would have to solve a computationally hard mathematical problem, namely the discrete logarithm problem. In case you want to go deeper: a nice, more detailed description of Diffie-Hellman, is available here. For people who don’t fancy multiplicative groups of integers, modulo arithmetic and prime numbers, that same page features an easy-to-understand simple analogy swapping integer numbers with paint of different colours like yellow, red and green.

The issue now is that this hard mathematical problem underlying the above-mentioned PKE system is deemed to be easily solvable using a quantum algorithm (namely Shor’s algorithm) on a future powerful quantum computer as we may expect to become available, maybe in the 2030s?

A solution to the problem – PQC

One way to solve the problem is to come up with even harder mathematical problems, that are expected to be unsolvable even for large quantum computers. Then we arrive at other PKE systems, which are considered quantum-safe, i.e., safe from malicious attacks carried out in the future with the help of quantum algorithms executed on quantum computers. Such systems are also called Post Quantum Cryptography systems, the field in short is referred to as PQC.

From PKE to KE and KEM

In a public key encryption (PKE) system, Bob can use Alice’s public key to encrypt a message m and send her a ciphertext ct, which only Alice using her private key can decrypt to get back message m. This would be asymmetric encryption in action: the keys used to encrypt and decrypt a message are different.

In a key exchange (KE) like Diffie-Hellman, the two (different) public keys of the two communication parties are in fact exchanged by these parties. The result of the protocol is the derivation of one and the same (and thus shared secret) key ss by both parties, where ss is usable for subsequent fast data encryption and decryption. This shared key ss is never sent across the communication link, also not in encrypted form.

In contrast, the key encapsulation method (KEM) we are aiming for here works differently to a key exchange, though it has the same purpose of eventually establishing a shared secret key ss between two parties and is also realised as a cryptographic protocol. The KEM uses asymmetric encryption to secure the communication of a desired (to-be) shared key from Alice to Bob. Thus, a shared key travels in form of ciphertext from Alice to Bob. In a classical KEM, the procedure may start with a random number ss at Alice which will eventually be communicated securely to Bob.

As with the KE, the KEM is not there to encrypt or decrypt the actual sensitive data users want to communicate to each other per se. It’s just there to get a symmetric key into the hands of the two parties.

The difference between a key exchange and a key encapsulation method is nicely illustrated in a picture in this blog by Cloudflare (in there scroll down to the section Kyber).

PQC and CRYSTALS-Kyber

In summer 2022, NIST, the US National Institute of Standards and Technology has selected a PQC-based candidate proposal for a new quantum-safe key encapsulation method called CRYSTALS-Kyber for standardisation. If you are curious about what the name means: CRYSTALS stands for Cryptographic Suite for Algebraic Lattices. Sufficient for us mere mortals to know that a lattice is an object in mathematics which most of us never come across. Advice: Don’t confuse it with a lettuce.

The CRYSTALS suite includes a key exchange method called Kyber and a digital signature algorithm called Dilithium. The name Kyber apparently refers to “the fictional kyber crystals used to power?lightsabers?in the?Star Wars?universe”. Clear?

So then, what is Kyber and how does it roughly work?

Kyber demystified

The specification for Kyber defines both a PKE scheme as well as a KEM. The latter makes use of the former.

Before you attempt to read the Kyber KEM proposal (see section 1.3 there), you may want to think twice as it is rather complex for the cryptographically untrained eye (and mind). However, to get a feel for Kyber, how it roughly works, it will be good enough to know the following:

• Kyber KEM is a proper KEM and thus allows to securely share a common (assume long enough and thus quantum-safe) secret key between two parties like Alice and Bob (just what we want).
• In a client/server type of scenario, the client party needs to create a pair of private and public keys.
• In Kyber, a private key is a vector s of polynomials (ahh, something new in the end!)
• And a public key is now a vector t of polynomials which is computed from a matrix A consisting of random polynomials, s and some error vector (also holding polynomials).

Then, for the PKE scheme, there is a calculation that tells us how to encrypt a message m and turn it into a Kyber cyphertext ct. For the KEM, there is another calculation how to encapsulate a new (to-be) shared key m with a public key to output both a final shared key K and a cypher text to send to the other party.

For the PKE scheme, there is further a procedure to decrypt the cyphertext to get back the original message m with high probability. For the KEM, another calculation shows how to decapsulate a ciphertext with a private key to finally restore the final shared key.

You can find the high-level mechanism as described by the Kyber authors neatly on a single page 3 here, though it lacks some explanation for the layperson. It shows the key formulas.

To much more easily embrace some of the core tricks and ideas used in Kyber, I’m pretty sure you will enjoy the easy-to-read blog post created by Ruben Gonzales: It is the best high-level “conveying the gist of the story” description of Kyber I have come across so far, wonderfully simplified for the non-cryptographers among us.

There is also a nice correspondence between the image/visualisation in the blog from Cloudflare, which I mentioned above, and Ruben’s description of a Kyber KEM application programming interface. As he explains, Kyber KEM needs to offer three functions:

1. The first one to generate a key pair. This is what the client does in the Cloudflare graphical illustration.
2. The second one to generate a random value ss and encrypt it to a cyphertext ct with the help of a public key pk. This is the function the server uses in the Cloudflare illustration, called Encapsulate().
3. The third one to decrypt the ciphtertext ct to the plain text ss using the private key pk. This is the function the client uses in the Cloudflare illustration, called Decapsulate() to retrieve the shared secret key.

In the end, these different sources are pretty consistent. However, in case you sense a degree of confusion regarding the notions of key exchange, key agreement and key encapsulation: Unfortunately, even experts seem to use the terminology inaccurately and inconsistently from time to time.?But let's not worry about that here.

How much assurance can be given that the Kyber KEM is really quantum-safe?

As of today not yet a super-huge amount, some experts say. Assurance for the safety of a cryptographic scheme (which has a hard-to-crack mathematical problem at its core) is usually built over time (often many years) through repeated analysis, attempts to break the scheme and publications of findings and failed attacks.

Hybrid KEs and Hybrid KEMs

As the world will need to migrate to quantum-safe implementations of communication protocols like TLS or IPSec, quantum-safe hybrid key agreement schemes will become important. In a Concatenate Hybrid Key Agreement Scheme, two shared keys k1 and k2 can be established with both parties in one go. One key k1 stems from a classical agreement scheme, while the second key k2 stems from a new post-quantum KEM like CRYSTALS-Kyber. These keys can then be concatenated and fed into a key derivation function to produce some final shared key material.

Why would one do so? Such a hybrid scheme pairs e.g., an ‘old’, classical high-assurance but quantum-vulnerable key exchange with a new, currently still low-assurance but hopefully quantum-safe key exchange. If the old scheme gets broken with a future quantum computer, the new scheme, one hopes, would still be fine and the key material produced through the hybrid scheme would be safe too. Even fancier, a hybrid scheme can use more than 2 key exchange mechanisms simultaneously, so all is fine as long as at least one component algorithm is not broken. ?

Overall, things are progressing. ETSI (the European Telecommunications Standards Institute) has produced a specification for Quantum-safe Hybrid Key Exchanges already in 2020 (TS 103 744).

In the IETF (Internet Engineering Task Force), Internet drafts have been created to discuss how to incorporate hybrid key exchange into the Transport Layer Security protocol TLS 1.3, much motivated by the transition to post-quantum cryptography. See e.g. the draft from University of Waterloo, Cisco Systems and Amazon Web Services here or here.

Work is also underway in the IETF IPSec working group to introduce multiple key exchanges into that protocol too, again, motivated by the desired transition to quantum-safe. As stated in RFC 9370: “Since there is currently no post-quantum key exchange that is as well-studied as (EC)DH [no worries, a classical key exchange algorithm], performing multiple key exchanges with different post-quantum algorithms along with the well-established classical key-exchange algorithms addresses this concern, since the overall security is at least as strong as each individual primitive”. Here we go.

What does it mean for us?

All good: Work is well underway to in the end render our well-known and much-loved application-level protocols quantum-safe, like https (as used by your web browser) or VPNs (virtual private networks as used when you work from home and log into your company’s IT systems). This will happen as lower-level protocols like TLS and IPSec get extended to support hybrid key exchanges that include at least one post-quantum algorithm, like CRYSTALS-Kyber.

Although CRYSTALS-Kyber, the real star in this article, has not yet been declared a final standard by NIST as of June 14, 2023, companies have already implemented it as part of commercial hybrid key exchange suites. An example is Amazon AWS Transfer Family, which combines the classical ECDH key exchange with CRYSTALS-Kyber. We may call this a pre-standards commercial implementation of Kyber.

All good if there weren’t a cheeky question: Are there other tricks to establish secret symmetric keys between two parties apart from establishing a symmetric key in a quantum-safe way over the same connection that is also used for the final end user data traffic (called in-band)?

The answer can be easily found by searching for out-of-band, e.g., in the “Hybrid Key Exchange in TLS 1.3” draft. It says: “Any out-of-band method of exchanging keying material is considered out-of-scope.” That’s the ultimate hint for us that out-of-band methods will likely exist as well!

And yes, no need to look far to find an example, e.g., the Phio Trusted Xchange (TX) solution by Quantum Xchange, which can be added to/overlaid over existing legacy networks. See a pretty insightful description here and a short solution brief from cybersecurity company Fortinet, well-known for their firewalls. Mind that this particular out-of-band symmetric key delivery solution builds on proprietary techniques and patents (and not completely open standards). However, I think my hero here, CRYSTALS-Kyber still can play a role even in that solution, namely for the quantum-safe establishment of a symmetric key between two parties, not over the connection where the end user data flows, but over a separate physical connection, thus out-of-band.

Before things get out of hand, better to finish here. Again, all is fine and end users have a choice. Right?