Re: [CFRG] Call for adoption: Hybrid KEM Combiners

["Kousidis, Stavros" <[e-mail]>]

Ilari,

Concerning your reply:

> "fixedInfo is some protocol-specific KDF binding,"
> 
> That's no KEM...
> 
> And there is a precedent on this sort of thing. Turned out to be a major
> mistake. Except I think this one is even worse.

[SK]: Let me repeat, we define a KEM combiner through the use of a KDF (from NIST SP 800-56Cr2). Of course we have to explain the interface and consequently it is obvious that you will find many such sentences as the one you cite.

Concerning your replies:

> What if none are IND-CCA2-secure, but there is Diffie-Hellman with hard
> {CDH}^{DDH} in the mix?
> 
> That case absolutely has to work, but no generic reasoning is possible.
> 
> In this sort of stuff, correct result for incorrect reasons is wrong.

And 

> Ciphertext can be elided if KEM resists both ciphertext 2nd preimages
> and re-encryption. ML-KEM is known to satisfy those assumptions.
> 
> Yes, this is a special case, but so is Diffie-Hellman.

[SK]: I would like to cite https://mailarchive.ietf.org/arch/msg/cfrg/84TUdtD0w12qFSNPpdV5ArS4-IE/, i.e.

"More importantly, a combiner that simply asks for IND-CCA2 KEMs is easier to review than a combiner that makes ad-hoc assumptions about KEMs, such as the QSF combiner inside X-Wing."

And let me repeat, the KEM combiner described in draft-ounsworth-cfrg-kem-combiners asks for at least one IND-CCA2 KEM.

Best
Stavros


> -----Ursprüngliche Nachricht-----
> Von: [e-mail] <[e-mail]>
> Gesendet: Montag, 19. Februar 2024 18:16
> An: [e-mail]
> Betreff: Re: [CFRG] Call for adoption: Hybrid KEM Combiners
> 
> On Mon, Feb 19, 2024 at 08:46:52AM +0000, Kousidis, Stavros wrote:
> 
> > > -----Ursprüngliche Nachricht-----
> > > Von: [e-mail] <[e-mail]>
> > > Gesendet: Sonntag, 18. Februar 2024 16:26
> > > An: [e-mail]
> > > Betreff: Re: [CFRG] Call for adoption: Hybrid KEM Combiners
> > >
> > > I think CFRG work on hybrid KEMs is very much needed. However, I do not
> > > think draft-ounsworth-cfrg-kem-combiners is a good starting point.
> > >
> > > Some of the major issues with that draft are:
> > >
> > > 1) It solves the wrong problem. The construction in that draft looks
> > >    like a multi-key KDF, not a KEM. Protocols usually integrate the KDF
> > >    rather tightly, making replacing the KDF very difficult. Whereas non-
> > >    exotic asymmetric confidentiality can usually be replaced by a fixed-
> > >    parameter KEM (exotic uses are usually pre-quantum anyway).
> > >
> > >    (D)TLS 1.3, COSE, JOSE, CMS and HPKE are all that way.
> >
> > [SK]: The construction is not a KEM it is a *KEM Combiner* that is
> > instantiated by picking a suitable one-step KDF from NIST SP
> > 800-56Cr2. So IMHO it solves the right problem by building upon
> > existing functions. There is no need for protocols to replace already
> > integrated KDFs. The composite KEMs that are offered in
> > draft-ounsworth-pq-composite-kem illustrate this. To be precise, the
> > resulting (combined) shared secret that results from e.g.
> > id-Kyber768-X25519-KMAC256 can be fed subsequently into your already
> > integrated KDF.
> 
> "fixedInfo is some protocol-specific KDF binding,"
> 
> That's no KEM...
> 
> And there is a precedent on this sort of thing. Turned out to be a major
> mistake. Except I think this one is even worse.
> 
> 
> > > 3) It labels its slots as IND-CCA2 KEM. It is not safe to just stuff
> > >    ECC into such slot. I don't think there is any widely known
> > >    IND-CCA2 KEM construction based on ECC (HPKE introduced its own one).
> > >    And using such would lead to goofy hash duplication.
> > >
> > >    It is very bad to offer crypto tool that will just be widely misused,
> > >    even if that misuse has no practical security impact.
> >
> > [SK]: I would like to point out that we propose a KEM Combiner that is
> > CCA2-secure as long as at least *ONE* ingredient KEM is CCA2-secure.
> > We point that out at several places in the draft and give arguments in
> > the security considerations, e.g.
> 
> What if none are IND-CCA2-secure, but there is Diffie-Hellman with hard
> {CDH}^{DDH} in the mix?
> 
> That case absolutely has to work, but no generic reasoning is possible.
> 
> In this sort of stuff, correct result for incorrect reasons is wrong.
> 
> 
> > > What I think CFRG needs to cover:
> > >
> > > c) No unneeded complexity. If key can be elided, do so. If both key and
> > >    ciphertext can be elided, do so.
> >
> > [SK]: I assume you mean *public* key here. In general, you must not
> > elide the ciphertext. This is what Giacon et al "KEM combiners"
> > tells us.
> 
> Ciphertext can be elided if KEM resists both ciphertext 2nd preimages
> and re-encryption. ML-KEM is known to satisfy those assumptions.
> 
> Yes, this is a special case, but so is Diffie-Hellman.
> 
> 
> 
> 
> -Ilari