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