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
Updated September 2024
Per the analysis of the final standard FIPS 203 in Sophie Schmieg’s “Unbindable Kemmy
Schmidt”, a strictly compliant instantiation of ML-KEM is LEAK-BIND-K-PK-secure
andLEAK-BIND-K-CT-secure, but not MAL-BIND-K-PK-secure nor MAL-BIND-K-CT-secure
(although keep reading for caveats). This means that the computed shared secret binds to the
encapsulation key used to compute it against a malicious adversary that has access to leaked,
honestly-generated key material but is not capable of manufacturing maliciously generated
keypairs. This binding to the encapsulation key broadly protects against re-encapsulation attacks
but not completely.
This step down from MAL security and vulnerability to the Kemmy Schmidt attacks
is due to the ‘expanded’ key format of ML-KEM as specified in FIPS 203: the K-PKE PK
hash is stored in the decapsulation key format instead of being re-computed from the K-PKE secret
key. A MAL attacker can replace this K-PKE PK hash to trick the decapsulator into calculating the
same K for a different CT, therefore violating the MAL-BIND-K-CT and MAL-BIND-K-PK properties. A
MAL attacker can also mess with the z FO-transform rejection value that is cached in the
expanded decapsulation key format, which can be the same as the z in another key pair, and when
the rejection value of K is returned, it will match another K for different keypair, violating the
MAL-BIND-K-PK property.
Luckily, before the standard was finalized, NIST listened to feedback about some of these attacks
and officially supported storing ML-KEM keys as two seeds, the K-PKE seed d, and the FO-transform
rejection value z:
FIPS 203 ML-KEM seed format for keys
This is functionally one 64-byte value, but according to the standard, this is not a single 64-byte
sampled value, but two 32-byte sampled values that together make up the decapsulation key
seed. Unfortunately, implementing this format is not required, merely optional; therefore, one may
have a compliant instantiation of ML-KEM according to FIPS 203, which would be only
LEAK-BIND-K-CT-secure, vs another compliant instantiation of ML-KEM, that only uses the (d, z)
decapsulation key seed format, which is MAL-BIND-K-CT-secure. 🙃
Using ML-KEM keys in this manner in practice protects against the first Kemmy Schmidt attack above,
but it does not protect against the second. It would be nice to have a single 32-byte
seed that could be expanded in a compliant way into both d
and z, but alas NIST said no. If that were allowed, it would have
mitigated the MAL-BIND-K-CTand MAL-BIND-K-PK Kemmy Schmidt attacks completely.
The (d, z) seed format is a fully FIPS-compliant way to store and use ML-KEM, and I recommend
using it in practice and plan to do so myself. To get close to MAL-BIND-K-CT security with this
format, the keypair _MUST_be validated as well-formed via the ‘key pair check’ in section 7.1 - this
regenerates the expanded decapsulation key format and encapsulation key from the seed format and
checks that they match. This does have performance implications.
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.
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_internal from FIPS 203, demonstrating implicit rejection
So to sum up, straight-up ML-KEM is LEAK-BIND-K-PK, LEAK-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. Using the
(d, z) format of the decapsulation keys and validating keypairs mitigates attacks such that
MAL-BIND-K-CT can be achieved…if you don’t fuck it up. 🫠
How do I hold it?
If I’m using ML-KEM in a protocol, in general, because it lacks MAL-BIND-K-CT and MAL-BIND-K-PK
security, I would make sure to commit to the encapsulated shared secret ciphertext (CT) and
encapsulation key (PK) 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.
Unless you write a security proof showing otherwise, the ML-KEM shared secret does not bind to the
ciphertext nor 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.
To get close to MAL-BIND-K-CT security with the compliant seed format, the keypair MUST_be validated as well-formed - I recommend it. You may be able to skip including the CT in your external KDF if you do. Since MAL-BIND-K-PK is not achievable in a compliant way, I _strongly recommend including the PK (encapsulation key) in your KDF.
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
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 Sep 18 2024 for FIPS 203 final and updated analysis of ML-KEM.