ML-KEM-BIND: A wrapper around ML-KEM with better binding properties

[Demi Marie Obenour]

It's actually possible to build a KEM that wraps ML-KEM and meets
all desired binding properties. It's secure assuming only:

1. ML-KEM is secure even with a plaintext-checking oracle.

2. If z is a 32-byte secret random string and a ≠ b,
SHA3-256(z || a) leaks no information about SHA3-256(z || b).

I'll call this ML-KEM-BIND. It adds 32 bytes of overhead to
both the public key and the ciphertext. The additional bytes are
indistinguishable from random unless one knows the secrets of the
party who generated them.

Let k be the module rank, and dk be the semi-expanded decapsulation key.
Then the secret key holder can compute:

z ← dk[768k + 64 : 768k + 96]
Zconf_extra ← (0 || dk[0 : 768k + 32])
Zconf ← SHA3-256(z || Zconf_extra)

Since k is always 2, 3, or 4, Zconf_extra is always of length 1569,
2337, or 3105 bytes. Since the ciphertext is always of length 768,
1088, or 1568 bytes, Zconf_extra cannot be a ciphertext. This means
that Zconf does not leak any value that can be produced by implicit
rejection.

Therefore, it's safe to append Zconf to the public key. Both parties
hash Zconf into their shared secret. Any changes to the the secret key,
*except* for those in dk[768k + 32 : 768k + 64], will be caught by this.
dk[768k + 32 : 768k + 64] is already hashed into the shared secret key,
so it doesn't need to be hashed again.

One can then turn the implicitly-rejecting KEM into an
explicitly-rejecting one in a standard way. For ML-KEM-BIND, I'll go
with a simple approach: use SHA3-512(K' || Zconf) for the final hash,
append the first 32 bytes to the ciphertext, and keep the last 32
bytes as the shared secret. The decapsulating party rejects if the
first 32 bytes from the hash don't match the last 32 bytes of the
ML-KEM-BIND ciphertext.

The reasons for this rather convoluted scheme are:

1. It works with existing secret keys, even semi-expanded ones.
2. It uses only APIs that FIPS 203 allows to be exported from a
cryptographic module.
--
Sincerely,
Demi Marie Obenour (she/her/hers)

[Natalia]

I like this extra layer of security.

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/17829ee9-607b-4ba4-9dc8-220b361e9db6%40gmail.com.

[John Mattsson]

Hi Mari,

Thanks for bringing this up. I agree that it would be preferable for future KEMs to provide BIND-CT-K and BIND-CT-PK. As with symmetric key commitment and signature malleability, I would not be surprised if the absence of these properties leads to vulnerabilities in the future.

I concerned by the argument that, because there are relatively few use cases strictly requiring SUF-CMA, it is acceptable to standardize new signature schemes with malleability vulnerabilities. In my view, that is the wrong design philosophy. Instead, we should follow the approach highlighted in NISTIR 7977:

"robust against accidental misuse"

"Cryptographic standards and guidelines should be chosen to minimize the demands on users and implementers as well as the adverse consequences of human mistakes and equipment failures."

Building a wrapper around ML-KEM to provide BIND-CT-K and BIND-CT-PK seems like a good idea, and I think it is something NIST should consider specifying. The problem with this approach is that it will only be used by users/developers who understand BIND-CT-K and BIND-CT-PK. In practice, that is likely to be a very small fraction of the developers writing code that uses ML-KEM. Future KEMs providing BIND-CT-K and BIND-CT-PK by default would be much better.

Cheers,

John Preuß Mattsson

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAMux9nCgm7qRtAHMVsyAgBjQ2VmXwW%2BU6LK%3DKu2b26BZjfYubw%40mail.gmail.com.

[Bas Westerbaan]

Neat idea, but is the squeeze worth the juice? ML-KEM has pretty good binding properties already: it's all the LEAK-* and HON-* that Cas et al defined. It only lacks MAL-BIND-K-PK with the FIPS 203 seed format, and on top of that MAL-BIND-K-CT for the expanded private key format.

We have seen attacks that exploit lack of LEAK-*. Has any attack been demonstrated or conjectured that exploit lack of MAL-*?

We originally suggested a more rigorous seed format as the only key format so that it'd have all these binding properties [1]. This is not because we knew of an attack, but because the change is cheap, and it'd prevent later pain if it did turn out to be useful. Unfortunately NIST chose to support both private key formats which has led to a serious delay in downstream standardization because of endless discussions on private key format [2]. We need a really good reason to open up that can of worms again.

Of course, if it's not too expensive, it's wise to get all the nice security properties for the next KEM that's standized in one variant.

Best,

 Bas

[1] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/5CT4NC_6zRI/m/lpifFrpWAwAJ

[2] https://na.eventscloud.com/file_uploads/54794b767e219a0f87f6322a2df15f02_Day2-1340-EntrustLandminesandMigrationStrategies.pdf