[CFRG] Re: DHKEM binding properties

[Peter C <[e-mail]>]

Deirdre,

> > DHKEM is MAL-BIND-K-CT and MAL-BIND-K-PK secure as analyzed
> > in the symbolic model” and cite Cremers et al (https://ia.cr/2023/1933)

> This was an error from previous slide decks, those properties are modelled
> in Tamarin and tested with several protocols to see if attacks showed up
> when the KEMs used in protocols such as Kyber-AKE have varying binding
> properties. The eprint version seems to be weird (all the previous versions
> are 404'ing?) so I've attached the version I have in my archive as it has lots
> more material, case studies, and short proofs for different KEMs about their
> binding properties (as written, vs as in practice, but still)

Thanks for the clarification and a copy of the earlier version.

> > As specified in RFC 9180, DHKEM is not MAL-BIND-K-PK secure because
> > DHKEM.Decaps recomputes the public key from the private key.  To achieve
> > MAL-BIND-K-PK, I think the public key needs to be provided as input to
> > DHKEM.Decaps and used in the KDF instead of the recomputed

> Fair enough. Either way, we get much stronger BIND properties from the
> default HPKE construction DH-KEM than swapping DH-KEM out for say
> Classic McEliece, which is IND-CCA secure but gets us zero binding to the
> PK, not even HON, and which earlier drafts of HPKE would have protected
> against, but no longer does.

Classic McEliece is not HON-BIND-CT-K or HON-BIND-CT-PK since it is
implicitly rejecting.  It is not HON -BIND-K-PK or HON -BIND-K, CT-PK by
Grubbs et al (https://ia.cr/2021/708)  For one of the parameter sets, it is
not even HON-BIND-K-CT or HON-BIND-K, PK-CT if the implementation
does not check the ciphertext padding bits (see “IND-CCA2 for encodings”
in https://classic.mceliece.org/mceliece-rationale-20221023.pdf)

> Relatedly, depending on how thing like Kyber/ML-KEM are implemented and
> used in practice, we may rarely get MAL-BIND security in practice if the encaps
> keys are only partially used in the interior KDF, or other shenanigans (see the
> 'Kemmy Schmidt' note for more fun: https://eprint.iacr.org/2024/523.pdf) We
> may cover ourselves by including everything in the higher protocol key schedule
> anyway (like TLS 1.3) but in HPKE we don't do that. LEAK-BIND may be sufficient
> and achievable in practice for general KEM usages but since HPKE is supposed
> to be a pretty bulletproof building block (and basically is for DH-KEM) it would be
> even nicer to change HPKE to be as bulletproof for other KEM cipher suites, or
> whatever action actually results in users getting security in deployments without
> having to do this bespoke analyst themselves every time.

Again, I think any MAL-BIND-P-Q claims need to be interpreted very carefully as
they can work in a very different way to their HON- or LEAK- counterparts.  For
example, Cremers et al dismiss X-BIND-PK, CT-K on the basis that “if Decaps is
deterministic, this is trivally true”, but that only holds for HON- and LEAK-.  An
implicitly rejecting KEM will not be MAL-BIND-PK, CT-K if malformed public keys
can be used to cause decapsulation failures.

Peter