Design goals for future KEMs

[Demi Marie Obenour]

Dear PQC Forum:

I'd like to start a discussion about what properties future KEMs
should have. ML-KEM was optimized for IND-CCA2 security. However,
as Sophie Schmieg's excellent blog post [1] pointed out, this comes at
the cost of binding properties.

As someone who could see herself *using* PQC, I agree with Sophie:
future KEMs should use explicit rejection and have the strongest
binding properties possible. Since real protocols generally give
a plaintext confirmation oracle, explicit rejection + plaintext
confirmation is just as secure as implicit rejection in practice.
Similarly, TLS hashes the ciphertext into the session key, so a
practical KEM must be secure if one does that.

While it's too late to do this for ML-KEM, would it make sense to do
this for future KEMs?

[1]: https://keymaterial.net/2024/11/05/hashml-dsa-considered-harmful/
--
Sincerely,
Demi Marie Obenour (she/her/hers)

[D. J. Bernstein]

Demi Marie Obenour writes:
> Since real protocols generally give
> a plaintext confirmation oracle, explicit rejection + plaintext
> confirmation is just as secure as implicit rejection in practice.

Counterexample: using NTRU-HRSS in real protocols (such as the usage of
CECPQ2 in TLS) is unbroken; but changing NTRU-HRSS's implicit rejection
to explicit rejection would destroy its security. See

https://web.archive.org/web/20260725191703/https://03283664099418252878.googlegroups.com/attach/aa2d2617e405/kem.pdf?part=0.0.1&view=1&vt=ANaJVrG49626Wd1S3wLbqmwUU0Hd2xTdcjcmLi4OarP59o48I8qFmbRKhwntZvswmoKCpELT2NT0cE0r0fj6qDlCqcJIC8yO2zT2gX85NONxfpwgJQY7zeI

for more detailed comments and references.

---D. J. Bernstein

[Demi Marie Obenour]

I'm referring to plaintext confirmation in the KEM itself. That's
equivalent to an application using an implicitly-rejecting KEM
rejecting later due to a MAC failure.

Alternatively, one can combine a KEM and an AEAD algorithm to produce
a PKE scheme with explicit rejection: reject if either the KEM rejects
or the MAC tag is bad, and don't reveal which one happened.

The problems arise when the attacker can distinguish "The KEM rejected
my ciphertext" from "I used the wrong derived key". Implicit rejection
turns the former into the latter. Plaintext confirmation turns the
latter into the former.

[D. J. Bernstein]

> > > Since real protocols generally give
> > > a plaintext confirmation oracle, explicit rejection + plaintext
> > > confirmation is just as secure as implicit rejection in practice.
> > Counterexample: using NTRU-HRSS in real protocols (such as the usage of
> > CECPQ2 in TLS) is unbroken; but changing NTRU-HRSS's implicit rejection
> > to explicit rejection would destroy its security. See
> > https://web.archive.org/web/20260725191703/https://03283664099418252878.googlegroups.com/attach/aa2d2617e405/kem.pdf?part=0.0.1&view=1&vt=ANaJVrG49626Wd1S3wLbqmwUU0Hd2xTdcjcmLi4OarP59o48I8qFmbRKhwntZvswmoKCpELT2NT0cE0r0fj6qDlCqcJIC8yO2zT2gX85NONxfpwgJQY7zeI
> > for more detailed comments and references.

> I'm referring to plaintext confirmation in the KEM itself.

Ah, okay, I thought you were referring to the plaintext confirmation
oracle mentioned a moment earlier.

For KEM designers, implicit rejection inside the KEM and plaintext
confirmation inside the KEM are separate layers of defense (see, e.g.,
https://pqsrc.cr.yp.to/ntrw-20221025.pdf#implicit-rejection) and can be
used simultaneously (see, e.g., mceliece*pc and sntrup). To again take
NTRU-HRSS as an example of the basic security picture:

* real ntruhrss701, implicit rejection internally, no plaintext
confirmation internally: unbroken (even when the application has
its own plaintext confirmation, such as a subsequent MAC test).

* hypothetical ntruhrss701ex, same as ntruhrss701 but modified to
eliminate implicit rejection internally in favor of explicit
rejection (API difference: dec can fail): efficiently broken.

* hypothetical ntruhrss701pc, same as ntruhrss701 but modified to
add plaintext confirmation internally (API difference: 32 bytes
extra ciphertext size), still implicit rejection: unbroken. (The
2017 version of ntruhrss701 was similar to this, with longer pc.)

* hypothetical ntruhrss701expc, same as ntruhrss701 but modified to
add plaintext confirmation internally and eliminate implicit
rejection internally in favor of explicit rejection (API
differences: 32 bytes extra ciphertext size and dec can fail):
unbroken.

The unbroken options here have theorems in simplified models, but this
doesn't mean that they have identical risk levels in the real world.
The main attack demo in https://cr.yp.to/papers.html#ntrw is an example
of the risks being different.

https://classic.mceliece.org/nist/mceliece-mods3-20221023.pdf explains
some reasons that people avoid pc but also some reasons to use it, even
when implicit rejection is in place. The link I gave before covers
various reasons to use implicit rejection in the first place.

> Alternatively, one can combine a KEM and an AEAD algorithm to produce
> a PKE scheme with explicit rejection: reject if either the KEM rejects
> or the MAC tag is bad, and don't reveal which one happened.

Yes, that's a common combination. The "don't reveal" part, in situations
where it's relevant, becomes easier if the KEM uses implicit rejection,
since the surrounding code doesn't see any KEM failures that it has to
stay quiet about.

In effect, the failure bit is being passed along in encrypted form to a
MAC, and the MAC sees only at the last moment that there's a failure.
People can still mess that part up with, e.g., variable-time memcmp or
wrong memcmp substitutes, but at least callers don't have to worry about
passing around and using a separate failure bit.

Note also that binding to labels (for example, user identities) is
easier at the AEAD stage than in the KEM. This observation goes back to
Shoup in https://eprint.iacr.org/2001/112 ("it is easier to implement
labels in the data encapsulation mechanism than in the key encapsulation
mechanism itself").

> The problems arise when the attacker can distinguish "The KEM rejected
> my ciphertext" from "I used the wrong derived key". Implicit rejection
> turns the former into the latter. Plaintext confirmation turns the
> latter into the former.

Not when they're used together. In a modular construction and security
analysis, the inner decryption layer is (maybe) surrounded by plaintext
confirmation, which in turn is (maybe) surrounded by implicit rejection.
Implicit rejection has the last word on whether the KEM can ever fail.

If both defenses are in place then attacks looking for the pattern of
decryption failures on modifications of a user ciphertext have to get
through (1) plaintext confirmation trying to create failures for those
modifications and (2) implicit rejection trying to hide all failures.

---D. J. Bernstein

[Natalia]

Hi all,

Following up on the implicit rejection vs. plaintext confirmation thread. Given the recent HAWK-n key recovery result, I think this is a good moment to make sure we're not narrowing down to a single design philosophy too early.

DJ's point that implicit rejection and plaintext confirmation are separable layers that can be used together (as in mceliece*pc and sntrup) seems worth treating as a first-class option, not just a fallback if either approach alone has weaknesses. Cutting off decoding access right after key acceptance, combined with internal implicit rejection, closes off more of the piggyback/oracle surface than either mechanism does alone.

Given how quickly the security picture can shift for any one primitive, I'd rather we evaluate future KEMs with this combined approach on the table from the start, rather than defaulting to one or the other.

Happy to discuss further.

Thank you,

Natalia D'Onofrio, FRP, MBA

Affinity Ventures, LLC  |  Founder

P.O. Box 2059

Palm Beach, FL 33480

Tel: (561) 501-1033

 

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20260726182154.1673124.qmail%40cr.yp.to.

[Demi Marie Obenour]

Indeed so. In this case, one doesn't actually need the full implicit rejection machinery, though. All one needs is for the KEM to output a (random or deterministic) secret value not related to other secrets. This will cause the AEAD to fail no matter what ciphertext is provided.

In particular, the attack on NTRU-HRSS where the implicit rejection key has a bit-flip does _not_ apply in this context, because the output of decapsulation is not available to the attacker.

> Note also that binding to labels (for example, user identities) is
> easier at the AEAD stage than in the KEM. This observation goes back to
> Shoup in https://eprint.iacr.org/2001/112 ("it is easier to implement
> labels in the data encapsulation mechanism than in the key encapsulation
> mechanism itself").
>
>> The problems arise when the attacker can distinguish "The KEM rejected
>> my ciphertext" from "I used the wrong derived key". Implicit rejection
>> turns the former into the latter. Plaintext confirmation turns the
>> latter into the former.
>
> Not when they're used together. In a modular construction and security
> analysis, the inner decryption layer is (maybe) surrounded by plaintext
> confirmation, which in turn is (maybe) surrounded by implicit rejection.
> Implicit rejection has the last word on whether the KEM can ever fail.
>
> If both defenses are in place then attacks looking for the pattern of
> decryption failures on modifications of a user ciphertext have to get
> through (1) plaintext confirmation trying to create failures for those
> modifications and (2) implicit rejection trying to hide all failures.
>
> ---D. J. Bernstein

I think of implicit rejection and plaintext confirmation as transforms from KEMs to KEMs.

1. _Implicit rejection_ takes an explicitly-rejecting KEM and returns an implicitly-rejecting KEM.

2. _Plaintext confirmation_ takes a KEM, which may be explicitly _or_ implicitly rejecting, and returns an explicitly-rejecting KEM.

In both cases:

1. The produced KEM is OW-Passive iff the original KEM is OW-Passive.
2. The produced KEM is IND-CPA iff the original KEM is IND-CPA.
3. The produced KEM is IND-CCA2 if, _but not only if_, the original KEM is IND-CCA2.

In the case of ML-KEM and HQC, my understanding is that implicit rejection is not actually required for security. This is due to the T-transform, which makes the ciphertexts non-malleable. Omitting implicit rejection from ML-KEM would have improved binding properties and saved 32 bytes from secret keys. One could maintain API compatibility by returning 32 random bytes instead of an error.

NTRU-HRSS and Classic McEliece _do_ require implicit rejection or plaintext confirmation for security. In both cases, the explicitly-rejecting versions without plaintext confirmation are insecure.

ML-KEM-BIND can also be viewed as the result of a transformation from a KEM to a KEM. The generic transformation works by:

1. Appending a hash of the secret key to the public key. The hash is chosen such that it is not useful to an attacker.
2. Hashing the original shared secret, the public key, the ciphertext, and the hash of the secret key into the shared secret.
3. Add plaintext confirmation to convert implicit to explicit rejection.

ML-KEM already hashes the public key into the shared secret, so ML-KEM-BIND didn't need to repeat this. Furthermore, due to how ML-KEM uses the FO transform, the plaintext and public key uniquely determine the ciphertext. Therefore, there's no need to hash the ciphertext into the shared secret either.

HQC already uses a 32-byte seed, so it provides stronger binding properties than ML-KEM does as long as the seed is used. However, some binding properties are not achievable with implicit rejection, so explicit rejection might well be a better choice.

[D. J. Bernstein]

Demi Marie Obenour writes:
> In this case, one doesn't actually need the full implicit rejection
> machinery, though. All one needs is for the KEM to output a (random
> or deterministic) secret value not related to other secrets. This
> will cause the AEAD to fail no matter what ciphertext is provided.

Handling a decryption failure of the internal PKE by having the KEM
output a long-term secret z or a new random z would indeed fit an
error-free KEM API. However, by itself this wouldn't defend against
chosen-ciphertext attacks, such as the NTRU-HRSS attack we're talking
about. One of the basic types of chosen-ciphertext attacks is to try
modifications of a ciphertext and observe the pattern of decryption
failures; if an output of z were the only defense, this pattern would be
revealed via the subsequent MAC failures.

Implicit rejection is just one extra step to hash a long-term secret z
together with the ciphertext. This still gives an error-free KEM API; it
defends against the pattern of failures being visible outside the KEM
boundary; it blocks tons of known attacks, including this attack; and it
leads to better proofs than the proofs available for systems without
implicit rejection.

I often see wild exaggerations of the guarantees provided by proofs, so
I think it's important to emphasize that, when I say "better" for
implicit-rejection proofs, I don't mean "perfect":

* These proofs rely solely on one-wayness of the underlying PKE,
unlike many other FO proofs making stronger assumptions about the
PKE; but we've seen many examples of PKEs for which one-wayness
was broken because of mathematical flaws in the PKEs, bugs in the
software (the deployed PKE isn't necessarily the specified PKE),
or side-channel attacks against the software.

* These proofs are simpler than many other FO proofs, but this isn't
a magical guarantee of correctness. Within my list, this is the
limitation that feels easiest to fix via formal verification, but
clearly more work is needed to get this right. (For example, a
week ago there was a wrong AI-generated proof getting past the
built-in Lean verifier and an "independent" Lean verifier:
<https://web.archive.org/web/20260731201835/https://leanprover.zulipchat.com/#narrow/channel/270676-lean4/topic/Counterexample.20to.20the.20Lean.20Conjecture.20.28Soundness.20Bug.29/near/613316580>.)

* These proofs have security levels much closer to one-wayness
security levels than many FO proofs, but there are still at least
a few bits of gap, and there are further limits coming from the
hash sizes and from many proposed PKEs not being perfectly correct
(PKE decryption not always inverting PKE encryption; people often
talk about decryption failures here, not to be confused with the
decryption failures coming from attacker-generated ciphertexts).

* These proofs have the rare feature of coming close to the
one-wayness security level for QROM IND-CCA2, but there could be
IND-CCA2 attacks much faster than QROM IND-CCA2 attacks. Maybe
there are vulnerabilities in the choice of hash function, for
example, or in the software doing the hashing. Even if this is a
lower risk than the PKE risks, it isn't zero risk. (The official
Keccak software allowed buffer overflows for many years! On the
bright side, I don't think typical KEMs could trigger those.)

https://eprint.iacr.org/2019/1336 gives an impressive list of examples
of "provable security" failing to live up to what it promises, even when
software is perfect.

> I think of implicit rejection and plaintext confirmation as transforms from KEMs to KEMs.
> 1. _Implicit rejection_ takes an explicitly-rejecting KEM and returns
> an implicitly-rejecting KEM.
> 2. _Plaintext confirmation_ takes a KEM, which may be explicitly _or_
> implicitly rejecting, and returns an explicitly-rejecting KEM.

That's session-key confirmation, not plaintext confirmation. (My own
motivation for introducing and switching to the plaintext-confirmation
terminology some years ago was to make this distinction clear. I think
the terminology is solidly established at this point.)

Plaintext confirmation converts a PKE into another PKE by sending and
checking a hash of the PKE plaintext. Once you wrap the PKE into a KEM
with Shoup's hashing of the plaintext, the plaintext is no longer
visible, so outside that layer you can't send a hash of the plaintext.
KEMs that use both plaintext confirmation and implicit rejection have
the plaintext confirmation on the inside.

Here's an example of how wrapping session-key hashing around that raises
different concerns: the session key can easily be shorter than the PKE
plaintext. Concretely, maybe the session key is only 128 bits (e.g., to
fit with usage of AES-128), and then sending a hash of that key opens up
a 2^128/T attack that finds one of T session keys (so already feasible
for moderate T), even if the PKE plaintext is bigger than 128 bits.

This example is part of a broader problem with people cutting corners.
Common defense layers include (1) trying to randomize every output,
which can damage security via RNG failures and in any case is a lot of
work that people keep screwing up (which is why, e.g., FrodoKEM issued a
security patch in 2023), and (2) moving up to 256-bit secrets, which is
relatively easy to get right.

> In the case of ML-KEM and HQC, my understanding is that implicit
> rejection is not actually required for security. This is due to the
> T-transform, which makes the ciphertexts non-malleable.

It's clear how the T transform gets in the way of some known types of
chosen-ciphertext attacks, but it's not at all clear how strong this
protection is. For example, Theorem 9 of

https://web.archive.org/web/20260215132734/https://eprint.iacr.org/2025/062.pdf

multiplies the expected sqrt(CCA advantage) by 8(d+q_D)sqrt(w), where
d is the number of stages of hash queries, w is the number of hash
queries per stage, and q_D is the number of decapsulation queries, and
then adds further terms related to correctness failures and how "spread"
the PKE is.

The factor 8(d+q_D)sqrt(w) by itself makes the theorem content-free for
proposed cryptosystems. It's not as if there has been intensive public
cryptanalysis trying to figure out whether this gap is exploitable;
cryptanalysts are overloaded with attack targets.

> Omitting implicit rejection from ML-KEM would have improved binding
> properties and saved 32 bytes from secret keys. One could maintain
> API compatibility by returning 32 random bytes instead of an error.

This seems difficult to evaluate without a clear definition of the
binding properties at issue, evidence that aiming for those properties
_decreases_ risks rather than _increasing_ risks (otherwise "improved"
is not the right word), and evidence that the two changes in question
achieve these properties.

Meanwhile the changes have other effects. The first change introduces
errors into the API. The second change avoids that, but amplifies the
question of what sort of binding we're talking about. Each change
eliminates the CCA protection provided by implicit rejection; this
_maybe_ isn't a problem given other defenses, but the evidence is
quantitatively and qualitatively weak. Removing a defense needs clear
justification.

Two years ago, when I saw a claim that compressing the ML-KEM secret key
to a 32-byte seed would achieve some "MAL-BIND-K-CT" property, I asked
for an explanation of what exactly the security problems are that were
supposedly addressed by this compression, and why those problems aren't
triggered at the moment that, e.g., someone decompresses a seed for
decapsulation. I haven't seen an answer.

Standard ML-KEM is like many other cryptosystems in not providing
MAL-BIND-K-CT. People who think that the lack of MAL-BIND-K-CT is a
security risk should be able to spell out concrete scenarios of security
failures that would be stopped by MAL-BIND-K-CT, so that the probability
and impact of such failures can be evaluated and weighed against
competing considerations. For comparison, there are many papers stating
CCA attacks that worked only because there wasn't implicit rejection,
and in the broader security literature there are many attacks that rely
on errors from APIs being mishandled.

---D. J. Bernstein