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

[Ilari Liusvaara <[e-mail]>]

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.

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.

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).
c) No unneeded complexity. If key can be elided, do so. If both key and
   ciphertext can be elided, do so.
d) Number of recommended pre-made instantiations for real-world use,
   complete with test vectors. The rest is NOT RECOMMENDED for use.
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