Re: [CFRG] ML-KEM for HPKE

[Karthik Bhargavan <[e-mail]>]

Dear All,

Bruno Blanchet recently did a new analysis [2] of the base mode of HPKE
that updates Benjamin Lipp's original analysis in [1].
I am summarizing his results here.

Recall that [1] proves the security of HPKE base mode when using DH-KEM,
under the assumption that the underlying DH construction obeys GapDH.
In the new proof, Bruno models the base mode of HPKE, single shot API in
CryptoVerif, and showed that if the KEM is IND-CCA2, then so is HPKE.
Since CryptoVerif is PQ-sound, that proves the security of the HPKE base
mode, with the single shot API when the KEM is a post-quantum IND-CCA2 KEM.

Bruno also shows that the DHKEM in non-authenticated mode is IND-CCA2,
which, together with the previous result, proves the security of the HPKE
base mode, with the single shot API and the DH-KEM.

In summary, this proof shows that HPKE with ML-KEM (or any other IND-CCA2
KEM) does provide IND-CCA2 security.
The question then becomes: what other properties would we like to have for
HPKE when using these KEMs?

Best,
Karthik

[1] https://eprint.iacr.org/2020/243
[2]
https://gitlab.inria.fr/bblanche/CryptoVerif/-/blob/crypto-library-pq-version/examples/hpke/hpke.base.indcca2.ocv?ref_type=heads



On Sun, Mar 10, 2024 at 5:38 PM Ilari Liusvaara <[e-mail]>
wrote:

> On Wed, Mar 06, 2024 at 12:23:48PM -0500, Deirdre Connolly wrote:
> > >
> > > According to the HPKE RFC, it has been proven that if using DHKem
> > > (over suitably strong group), then HPKE does satisfy its security
> > > goals.
> >
> >
> > However, according to HPKE RFC, it has not been shown that HPKE
> > > satisfies its security goals for any non-DHKem. However:
> >
> >
> > - Such proof might have appeared later.
> > > - HPKE RFC conjunctures that it is sufficient for the KEM part to be
> > >   IND-CCA2 for HPKE to satisfy its security goals. And it would be very
> > >   surprising for this to be false.
> >
> >
> > This is fair. ML-KEM and the wrapped variant I describe in the document
> > (basically Kyber) fulfill the explicit requirements for IND-CCA2 security
> > of the underlying HPKE KEMs. The binding properties
> > <https://eprint.iacr.org/2023/1933.pdf> referenced had not been
> formalized
> > when HPKE was designed and analyzed - now that they have, and
> > DHKEM analyzed to provide MAL-BIND-K-PK and MAL-BIND-K-CT security, the
> > goal is to align with these implicit properties in a new FIPS-compatible
> PQ
> > ciphersuite so as not to downgrade from all the other HPKE ciphersuite
> > binding properties 'accidentally'. If HPKE had committed to the KEM
> > ciphertext and public key independent of the KEM actually being used,
> then
> > there would be nothing to do here, but it uses the raw shared secret from
> > the ciphersuite KEM and knows nothing else about the KEM beyond that.
>
> The binding properties of KEMs are irrelevant for any HPKE user. What
> matters is the properties HPKE gives. And not all KEM properties pass to
> HPKE in any way.
>
> For instance, preventing messages from decrypting under two keys is only
> possible if KEM is explicitly-rejecting. It is impossible for any
> implicitly-rejecting KEM. And since HPKE already has implicitly-
> rejecting KEMs, it can not be HPKE security property.
>
> Furthermore, it is extremely risky to rely on any HPKE properties beyond
> the documented ones.
>
> I think that before any such property is treated as a goal (as opposed
> to non-goal or even anti-goal), one would have to at least conjecture
> (preferably prove) how such properties pass to HPKE as whole and update
> the HPKE RFC.
>
>
> > The goal is to align with existing instances of HPKE ciphersuites in both
> > explicit properties and now these implicit properties that we understand
> > better, so we diverge as little as possible, while providing PQ security
> in
> > a FIPS/CNSA 2.0¹-compatible way, with minimal complexity.
>
> Even without that extra KDF step, there is still re-encapsulation
> resistance, which translates to re-encryption resistance in PSK mode
> (base mode trivially can not resist re-encryption):
>
> If the KDF is secure and PSK is unknown (otherwise re-encryption
> resistance trivially fails), the outputs for different KEM shared
> secrets are pseudorandom and uncomputable. Therefore the attacker must
> match the resulting shared secret.
>
> As the sender is honest (otherwise there is no security), with
> overwhelming probability the the ciphertext is honest (w.r.t. key M).
>
> Coming up with dishonest ML-KEM ciphertext (with respect to any key)
> that decapsulates to the same shared secret as previous is at least
> as hard as second preimage attack against SHA3-256 (because the cases
> are context-separated).
>
> Coming up with honest ML-KEM ciphertext (w.r.t. key B) that decapsulates
> to the same shared secret as previous requires G(m|H(M))=G(m'|H(B)).
> There are two ways to satisfy this:
>
> - H(M)=H(B) and m=m'. Since M and B are different, this is at least
>   as hard as SHA3-256 collision attack.
> - m'|H(B) is 2nd preimage of m|H(M). This is at least as hard as
>   SHA3-256 second preimage attack.
>
> The first requires incompetent adversary (should just retain B and
> not bother with all this). And no incopetent adversary can ever be
> strictly more dangerous than the most dangerous competent adversary.
>
> Therefore for any competent adversary, re-encapsulation is at least as
> hard as second preimage attack against SHA3-256, and thus re-encryption
> in HPKE PSK mode is at least as hard as second preimage attack against
> SHA3-256.
>
>
> I think more general version of the previous statement is that if the
> KEM is IND-CCA2 and LEAK-BIND-K-PK, then HPKE in PSK mode resists re-
> encryption. I think all current HPKE KEMs do provide this.
>
> Of course, stronger assumptions from KEM might lead to even stronger
> properties from HPKE. However, I already view relying on this thing as
> a red flag. Any such additional properties would be even bigger red
> flags.
>
> The extra KDF step has significant complexity cost. Especially given
> that ML-KEM internally uses SHA-3, and that KDF step is based on SHA-2.
>
>
>
>
> -Ilari
>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://mailman.irtf.org/mailman/listinfo/cfrg
>