How to Hold KEMs

How to Hold KEMs

A living document on how to juggle these damned things.

What’s a KEM?

A KEM is a Key Encapsulation Mechanism, a cryptographic primitive that has a KeyGen() algorithm, an Encaps() algorithm, and a Decaps() algorithm. KeyGen produces a (decaps_key, encaps_key) keypair. Encaps(encaps_key) uses an encapsulation key (similar to an asymmetric public key) to compute and return a shared secret and the encrypted ciphertext encapsulation of that shared secret (often called ct or enc). Decaps(ct, decaps_key) takes the encapsulated shared secret ciphertext and the decapsulation key (similar to an asymmetric secret key) to re-construct the shared secret.

KEM diagram from FIPS 203

In general, cryptographic primitives are designed to fulfill a particular security property when instantiated correctly, and that property is defined as being able to beat an adversary modeled with certain abilities within a security game. For digital signatures, there is usually an unforgeability property under chosen message attack (EUF-CMA); for KEMs, the property is indistinguishability under chosen ciphertext attack (IND-CCA). Informally this means that the computed shared secret is indistinguishable from random against an adversary who can decapsulate maliciously constructed ciphertexts, but who doesn’t have direct access to the decapsulation key.

IND-CCA experiment for KEMs, from “Keeping Up with the KEMs”

KEMs have become ‘all the rage’ recently (not because they are sexy or special, they just seem to be the best we’ve got in a post-quantum world). In the shadow of a cryptographically-relevant quantum computer that can break our Diffie-Hellman’s and elliptic curve-based constructions in ~polynomial time, including stuff that’s been hoovered up and stored for a later day when those quantum computers come online (Store and Decrypt Later), there’s been movement to migrate cryptography protocols off of Diffie-Hellman onto primitives like KEMs, because they enable things like key establishment, but base their security on quantum-resistant problems such as Module Learning-with-Errors.

However. KEMs are not DH, and protocols that were originally designed based on the properties (formal and informal) of Diffie-Hellman are now trying to swap them out for KEMs or hybridize them with KEMs. KEMs generally are designed to fulfill IND-CCA and IND-CCA only, and some designs have been changed to simplify and make clearer IND-CCA security proofs and to improve performance, but that also resulted in the removal of some of the other security properties that make them trickier to just use without caveats.

Re-encapsulation attacks

As coined by Cremers et al and explored by the Cryspen team, re-encapsulation attacks exploit the fact that some KEMs allow the decapsulation of a ciphertext to an output key k and then can produce a second ciphertext for a different public key that decapsulates to the same k. Re-encapsulation attacks in protocols, often known as an unknown-key-share attack, result in two parties computing the same key despite disagreeing on their respective partners. This doesn’t sound great, but is completely allowed under the IND-CCA security definition! To avoid these sorts of attacks, we need to know more about a KEM than just that it’s an IND-CCA-secure KEM: we need to know how it binds its shared secrets to encapsulation keys and ciphertexts. This is a thing we didn’t need to think about with Diffie-Hellman, as it was only in weird cases (small-order points, ‘non-contributory behavior’, etc) that Diffie-Hellman public keys were not tightly bound to the shared secret resulting from the computation, and there was no ciphertext to juggle either.

Binding properties

Cremers, Dax, and Medinger formalized these notions of ‘binding’ properties for KEMs and explored their relations to similar notions like ‘robustness’ and ‘contributivity’ in the literature, including describing a spectrum of adversaries with different capabilities, how these notions relate (or imply) each other, and checked them via symbolic analysis with Tamarin. For a value to ‘bind’ another value, such as a shared secret K binding an encapsulation key PK, is to uniquely determine it; more formally, “P binds Q” if, for fixed instances of P, there are no collisions in the instances of Q.

The generic binding property instantiations X-BIND-P-Q before choosing X ∈ {HON , LEAK, MAL} from “Keeping Up with the KEMs”

There are different security models of adversaries for these properties: honest (HON), leak (LEAK), and malicious (MAL). Honest variants involve everyone behaving themselves, such that the involved key pairs are output by KeyGen() and not accessible by the adversary, but the adversary has access to a Decaps() oracle. Leakage variants have honestly-generated key pairs leaked to the adversary. Finally, in malicious variants, the adversary can create the key pairs any way they like in addition to the key generation, so they can do…a lot. Ideally, our KEMs would be resistant to such adversaries, so these MAL-BIND-P-Q properties are attractive.

General hierarchy of binding properties for KEMs from “Keeping Up with the KEMs” (NB: implicit rejection KEMs have a restricted hierarchy)

Some of the big takeaways here are that we like MAL-BIND-K-CT and MAL-BIND-K-PK properties in our KEMs:

  • A MAL-BIND-K-PK-secure KEM means that the KEM’s shared secret (K) binds to the encapsulation key (PK) used to compute it, even against a malicious adversary that has access to leaked key material and is capable of manufacturing maliciously-generated keypairs. This strong binding to the encapsulation key protects broadly against re-encapsulation attacks because different parties (as identified by their public key) cannot be coerced into deriving the same key.

  • A MAL-BIND-K-CT-secure KEM means that the KEM’s shared secret (K) binds to the encapsulated shared secret ciphertext (CT), even against a malicious adversary that has access to leaked key material and is capable of manufacturing maliciously-generated keypairs. This strong binding to the ciphertext protects broadly against re-encapsulation attacks so that two different ciphertexts cannot decapsulate to the same shared secret K.

Implicit rejection

Digging even deeper, a lot of popular KEMs are implicitly rejecting, as a result of their particular flavor of applying the Fujisaki-Okamoto (FO) transform. The FO transform takes a public key encryption (PKE) scheme secure under chosen-plaintext attack (IND-CPA) and turns it into an IND-CCA KEM scheme. Implicitly rejecting KEMs always return a value, even if the PKE decryption step inside Decaps() fails or returns an unexpected value. This design means that Decaps() always returns a pseudorandom value, even if decryption fails. This is hopefully safer to use in higher-level protocols that may or may not check the decapsulation value. Because of this implicit rejection design, there are fewer binding properties available to such KEMs, period, and this generally eliminates their ciphertexts alone binding to public keys or shared secrets: any ciphertext will be accepted, and these will almost certainly decapsulate to different shared secrets. This means that implicitly rejecting KEMS cannot be X-BIND-CT-K-secure or X-BIND-CT-PK-secure for any of the binding adversary variants, and we are only possibly left with the subset of binding properties below.

Restricted hierarchy of binding properties for implicitly-rejecting KEMs from “Keeping Up with the KEMs”


ML-KEM is MAL-BIND-K-PK-secure. This means that the computed shared secret binds to the encapsulation key used to compute it even against a malicious adversary that has access to leaked key material and is capable of manufacturing maliciously-generated keypairs. This strong binding to the encapsulation key protects broadly against re-encapsulation attacks.

ML-KEM is also LEAK-BIND-K,PK-CT-secure (ciphertext collision-resistant, CCR). This means that the computed shared secret and the encapsulation key together bind the ciphertext. Since ML-KEM is MAL-BIND-K-PK-secure, given a shared secret K, we know it uniquely binds to a PK, and because together K and PK uniquely bind to a CT, that means we get LEAK-BIND-K-CT for ML-KEM, but not MAL-BIND-K-CT. This is formalized by corollary A.8 in keeping-up-with-the-kems.

LEAK binding is secure against leaked, honestly-generated keypairs available to the adversary, but not against maliciously generated keypairs generated by the adversary (MAL).

In contrast, once upon a time, there was Kyber before it was changed to not hash in the ciphertext anymore. Kyber as defined in version 3.02 of the NIST PQC submission hashed in the ciphertext into the derivation of the shared secret, and thus was MAL-BIND-K-CT as well as MAL-BIND-K-PK. This was removed as Kyber transformed into ML-KEM, ostensibly to get the speedup by avoiding hashing the large ciphertext, while also making the IND-CCA proofs of security simpler because that was the security goal at the time. Alas.

ML-KEM (and Kyber, and some others) are implicitly rejecting KEMs. In ML-KEM, the implicit rejection value is derived from randomness (part of the decapsulation key) and the ciphertext (which is ostensibly attacker-controlled). Yes, I am aware of the irony that the ciphertext is bound by the implicit rejection ‘key’ but not the real shared secret. 💀 This means that ML-KEM cannot be X-BIND-CT-K-secure or X-BIND-CT-PK-secure for any of the binding adversary variants, and we are restricted to the smaller set of binding properties for implicitly rejecting KEMs.

ML-KEM.Decaps from FIPS 203, demonstrating implicit rejection

So to sum up, ML-KEM is MAL-BIND-K-PK, MAL-BIND-K,CT-PK, LEAK-BIND-K,PK-CT, and LEAK-BIND-K-CT -secure, but not any flavor of X-BIND-CT-K or X-BIND-CT-PK -secure.

How do I hold it?

If I’m using ML-KEM in a protocol, in general, because it lacks MAL-BIND-K-CT security, I would make sure to commit to the encapsulated shared secret ciphertext (CT) along with the decapsulated shared secret, either in the final protocol KDF or something similar. TLS 1.3 commits to basically everything in the handshake transcript as part of its key schedule, so they are already doing this ‘for free’. Apple’s PQ3 upgrade to iMessage includes the ML-KEM ciphertext and encapsulation key in the label field of the HKDF-Expand() call in its KDFRKCK KDF function, along with a lot of other transcript stuff. In general, if you can afford it, I would hash in / commit to all public data in the protocol transcript, including the encapsulation keys - It can really save your ass.

You may need to commit to the encapsulation keys for other reasons in your protocol, but for ensuring that the ML-KEM shared secret binds to a specific encapsulation key, that’s not strictly necessary for ML-KEM. However. We do have this LEAK-BIND-K-CT property, which is weaker than MAL-BIND-K-CT but still protects against key leakage being used against us. If your higher-level protocol has protections against maliciously-generated ciphertexts, you can commit to the shared secret and encapsulation key in your protocol KDF and get the LEAK ciphertext binding property.

Unless you write a security proof showing otherwise, the ML-KEM shared secret does not bind to the ciphertext against adversaries that maliciously twiddle key material, so I would recommend hashing it into your KDF or equivalent along with the shared secret. Otherwise, there is a burden of proof to demonstrate security against MAL adversaries.

Classic McEliece

Classic McEliece is another PQ-secure KEM that is built on code-based cryptography (instead of lattices, like ML-KEM or Kyber). It is a fourth-round candidate in NIST’s PQC KEM competition, a proposed ISO standard, and the general McEliece public-key encryption design has a long and robust history behind it.

Classic McEliece, as specified in the NIST submission, is MAL-BIND-K-CT-secure and MAL-BIND-PK,K-CT-secure. This means you can use the shared secret output without also committing to the encapsulated shared secret ciphertext. But that’s it. Classic McEliece lacks any binding to the encapsulation key (PK) in any of the adversary security models, as the underlying public key encryption scheme allows a ciphertext CT to decrypt to the plaintext message under any decryption key, not just the decryption key associated with the public encryption key used to generate the ciphertext. Since Classic McEliece derives the KEM shared secret only from the ciphertext CT and the randomness (message), and the underlying PKE allows us to generate the same shared secret K from multiple ciphertexts for any key pair, Classic McEliece is not HON-BIND-K-PK or any other variant thereof.

Since Classic McEliece is also an implicitly rejecting KEM, it lacks the X-BIND-CT-PK and X-BIND-CT-K properties too.

Classic McEliece from Anonymous, Robust Post-Quantum Public Key Encryption

Therefore Classic McEliece is MAL-BIND-K-CT-secure and MAL-BIND-PK,K-CT-secure, but not any flavor of X-BIND-CT-K, X-BIND-CT-PK, X-BIND-K-PK, or X-BIND-K,CT-PK -secure.

How do I hold it?

You MUST commit to the Classic McEliece public encapsulation key (PK) as well as the derived shared secret K in your KDF or equivalent. This may be quite annoying as Classic McEliece encapsulation keys are much larger than, say, ML-KEM encapsulation keys, and hashing them or including them as inputs to your KDF may be computationally expensive.


FrodoKEM is another implicitly rejecting PQ KEM based on lattices, but it relies on the learning-with-errors problem instead of the module-LWE problem (like ML-KEM and Kyber), and it uses a different flavor of FO-transform to produce a KEM from its underlying FrodoPKE public key encryption scheme. It was a NIST PQC candidate KEM and is a proposed ISO standard.

FrodoKEM hashes in its encapsulation key (PK) and its ciphertext (CT) into the final internal hashing step that produces the final shared secret (K). Even without looking at the underlying PKE scheme, we can see it has MAL-BIND-K-PK, MAL-BIND-K,CT-PK, MAL-BIND-K-CT, and MAL-BIND-PK,K-CT security. Since it’s an implicitly rejecting KEM, it does not have any X-BIND-CT-K or X-BIND-CT-PK binding properties. Easy-peasy.

FrodoKEM FO-transform IND-CCA construction

How do I hold it?

In terms of binding properties, FrodoKEM is pretty great. In general, I still would commit to all the public transcript data in my KDF, along with the shared secret produced by FrodoKEM, but not because the shared secret is not bound to the FrodoKEM encapsulation key or ciphertext but for other protocol security properties.

Updated Feb 27 2024 to include Classic McEliece and FrodoKEM.