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

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

Dear Ilari,

let me try and give some guidance specific to the mindset and content of draft-ounsworth-cfrg-kem-combiners.

Inline, see below '[SK]: ...'.

Best
Stavros

> -----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
> 
> On Wed, Jan 31, 2024 at 10:28:50AM -0500, Nick Sullivan wrote:
> > Dear CFRG,
> >
> > There has been a lot of discussion on the list over the last few weeks
> > around the topic of hybrid KEMs, including discussion around the topic of
> > where we should go as a group. There seems to be significant interest in
> > this topic from around the IETF and in broader industry. We (the chairs)
> > have decided to open up a research call for adoption for a topic in this
> > area, described below.
> >
> > The standard context for the group applies here as always: As part of the
> > IRTF, the CFRG is a research group, producing research documents relevant
> > to the IETF and broader community. The CFRG does *not* publish standards
> > and does *not* dictate cryptographic choices to IETF working groups. CFRG
> > documents often come with concrete specifications for parameterizations
> > relevant to groups within the IETF. Recent examples of documents of this
> > style resulting from topics adopted by the CFRG include RFC 9497 (OPRF) and
> > RFC 9381 (VRF), which provide a thorough overview of the topic along with
> > concrete parameterizations that can adopted by protocol designers.
> >
> > The CFRG has a full docket of important ongoing work, so it’s important to
> > ensure that any work the CFRG adopts at this point aligns with the charter
> > by offering necessary guidance (for network security in general and for the
> > IETF in particular) on the use of emerging mechanisms.
> >
> > With that preamble done,* this email starts a three-week call for the
> > adoption* of a work item within the CFRG to produce an informational
> > document exploring how to safely combine KEMs. This document
> > * Will use draft-ounsworth-cfrg-kem-combiners as a starting point for
> > describing generic combiners
> > * Will include an analysis of the non-generic combiner mechanisms for
> > specific KEMs outlined in draft-connolly-cfrg-xwing-kem and other published
> > works in the area
> > * Will describe the security properties and trade-offs of various methods
> > of combining KEMs
> > * Will provide concrete instantiations of hybrid KEMs that are relevant to
> > IETF protocols (potentially similar to X-Wing and Chempat-X), including
> > pseudocode and test vectors
> 
> 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.

> 
> 2) The uses of that draft in various protocols have picked all sorts of
>    combinations of algorithms. Supporting that in crypto libraries is a
>    PITA. Much worse, the protocols use it in slightly incompatible ways,
>    which is just about impossible to deal with in crypto libraries.
> 
>    Considering how important crypto libraries are, this is very bad.
> 
> 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.

- Abstract: "The combiners defined here are practical split-key PRFs and are CCA-secure as long as at least one of the ingredient KEMs is."
- Section 3.2. k_i construction: "Including the ciphertext guarantees that the combined kem is IND-CCA2 secure as long as one of the ingredient KEMs is, as stated by [GHP18]."
- Section 6. Security Considerations: "Our construction can thus be seen as an instantiation of the IND-CCA2 preserving Example 3 in Figure 1 of [GHP18], [...]"

IMHO: We propose a very robust construction.

BTW: I think the widely known method of producing an ECC-based IND-CCA2 KEM is described in the 2001 paper of Cramer and Shoup, "Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack". That paper is also cited in HPKE (RFC9180) and (I believe, judging based on https://www.shoup.net/papers/iso-2_1.pdf) ECIES-KEM derives from this.

> 
> 4) Because it is generic, it needs to deal with all sorts of badly
>    behaving KEMs that hopefully nobody is using. This makes things
>    slower and more complex than needed.
> 
>    E.g., KEM that does not resist ciphertext second preimages. Or
>    a KEM that does not resist re-encryption.
> 
> If version based on draft-ounsworth-cfrg-kem-combiners gets posted, it
> should have major warnings not to use it for any protocol work until
> published as RFC. Incompatible uses are really bad.
> 
> 
> What multiple protocols actually want is a set of fixed-parameter hybrid
> KEMs, constructed from ML-KEM (or sometimes other PQC KEMs) and ECC (or
> sometimes RSA) And any such can be optimized for both performance and
> simplicity (usually the goals do not compete).
> 
> 
> 
> What I think CFRG needs to cover:
> 
> a) Protocol-universal KEM combiner, accepting KEMs, ECC and RSA as
>    components, with no unneeded degrees of freedom.
> b) Presumably based on NIST SP 800-56Cr2 (apparently some want that,
>    it doesn't really add complexity and haven't seen any conflicting
>    requests).

[SK]: This is actually exactly what draft-ounsworth-cfrg-kem-combiners is doing. See e.g.

- Abstract: " This document defines a comprehensible and easy to implement Keccak-based KEM combiner to join an arbitrary number of key shares, that is compatible with NIST SP 800-56Cr2 [...]
- Section 3 KEM combiner construction: " In Section 4 several possible practical instantiations are listed that are in compliance with NIST SP-800 56Cr2 [...]"#

> 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.

> d) Number of recommended pre-made instantiations for real-world use,
>    complete with test vectors. The rest is NOT RECOMMENDED for use.

[SK]: Actually this is on our Todo-list for draft-ounsworth-cfrg-kem-combiners.

> e) How to use ML-KEM as a component (simpler/faster than generic).
> f) (Possibly how to use NTRU prime as component).
> g) How to use ECDH as component (it is not a KEM).
> h) How to use X25519/X448 as component (ditto).
> i) How to use RSA as component (yes, apparently some do want RSA)
> j) How to use generic KEM as component.
> k) Description of security properties of all previous (sometimes those
>    seem to get a bit funky...)
> 
> Details for each algorithm class (except generic KEMs) need to be
> worked out anyway for the recommended instantiations.
> 
> The actual instatiations will presumably look something like what is
> in this PR:
> 
> https://github.com/lamps-wg/draft-composite-kem/pull/11
> 
> (I think ciphertext is needed for RSA, even if IND-CCA2 proof would go
> through without...)
> 
> 
> 
> 
> -Ilari