Generating ML-KEM z from d to prevent rebinding attacks

[Demi Marie Obenour]

Disclaimer: I'm just an amateur cryptographer. This might have mistakes,
though (to the best of my knowledge) it is correct. No LLMs were used
in writing it.

The ML-KEM seed actually has 2 32-byte parts: d, used to generate the
encryption and decryption keys, and z, used only for implicit rejection.
This allows a (very minor) rebinding attack [1].

However, the only use of d is to compute SHA3-512(d || k), where k is
the module dimension. k is always a single byte and is never zero.
Since SHA3-512 is a PRF, this means that one can use the bottom 32
bytes of SHA3-512(d || 0 || k) for z without losing any security.
This saves 32 bytes in secret storage (potentially valuable for
hardware tokens) and prevents the rebinding attack.

The only disadvantages of this approach I can think of are:

1. It technically violates FIPS-203, although its security follows
from that of FIPS-203 + "SHA3-512 is a PRF".

2. It requires an extra SHA3-512 computation for every decapsulation.

Is this something that would be useful in practice?

[1]: https://keymaterial.net/2024/09/14/unbindable-kemmy-schmidt/
--
Sincerely,
Demi Marie Obenour (she/her/hers)

[Sophie Schmieg]

yes, this approach works, and was more or less what I originally suggested in Kemmy Schmidt [1] (I technically suggested using a PRF call to create sigma, rho, and z). Currently the second half of the G(d || k) call is used for rho, which becomes part of the public key, so it obviously cannot be reused for z, but by inserting a second SHA3-512 call or by using SHAKE to derive 3 32 byte values you could reduce the seed to a single one. However, back when the discussion surfaced this problem, NIST had already all but finalized the spec and this rewrite would force a bunch of rework of the function definitions as they exist in FIPS 203, so it was decided that it wasn't worth the trouble given that it is unclear whether this is an actual problem in practice.

If deriving ML-KEM keys is following FIPS (I'm unclear on the status of that, it's required for a bunch of use cases like MLS, but it requires a rework of the key derivation SP), then there is a FIPS compliant way of making this work, by using some FIPS compliant key derivation function and deriving the seeds for ML-KEM from another seed, storing only this meta seed as the private key.

[1] https://eprint.iacr.org/2024/523

--
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/d84e0aa5-5252-4b8d-993e-4482f02cc7ed%40gmail.com.

--

Sophie Schmieg | Information Security Engineer | ISE Crypto | ssch...@google.com

[Demi Marie Obenour]

On 7/6/26 16:06, Sophie Schmieg wrote:
> yes, this approach works, and was more or less what I originally suggested
> in Kemmy Schmidt [1] (I technically suggested using a PRF call to create
> sigma, rho, and z). Currently the second half of the G(d || k) call is used
> for rho, which becomes part of the public key, so it obviously cannot be
> reused for z, but by inserting a second SHA3-512 call or by using SHAKE to
> derive 3 32 byte values you could reduce the seed to a single one.

This could be quite useful for smart cards due to their very limited
storage capacity. For non-exportable keys, there is no way to know
whether this approach was used.

> However,
> back when the discussion surfaced this problem, NIST had already all but
> finalized the spec and this rewrite would force a bunch of rework of the
> function definitions as they exist in FIPS 203, so it was decided that it
> wasn't worth the trouble given that it is unclear whether this is an actual
> problem in practice.

Purely a curiosity question: why was the rework a problem, given that
the result would definitely be no less secure?

> If deriving ML-KEM keys is following FIPS (I'm unclear on the status of
> that, it's required for a bunch of use cases like MLS, but it requires a
> rework of the key derivation SP), then there is a FIPS compliant way of
> making this work, by using some FIPS compliant key derivation function and
> deriving the seeds for ML-KEM from another seed, storing only this meta
> seed as the private key.
>
> [1] https://eprint.iacr.org/2024/523

Should this be standardized in the IETF or a future version of FIPS 203?
It would be best to not have multiple non-interoperable techniques in use.