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