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

[Sophie Schmieg <[e-mail]>]

I do agree that we should get something in CFRG, whether that's a standard
or a guidance, but we should be thinking about the protocols that end up
using the constructions, in order to make sure whatever is produced here is
relevant there, so they don't need to modify things further. That
unfortunately means doing something of a special case analysis, but I think
doing so is instructive on its own.

I'm specifically thinking about S/MIME, which might be one of the more
complex situations. At the moment, the most commonly used encryption scheme
there is using RSA-OAEP to encrypt an AES-CBC or (hopefully mostly these
days) AES-GCM key. One of the bigger reasons for RSA-OAEP being popular
there is that it has to support multiple recipients, and OAEP can do so
without adding another keywrap step.
For PQC, we will either have to include this keywrap step, further
increasing ciphertext size and reducing usable email-payload, or
standardize alternative primitives like mKEM [1] for example. I'm not
certain that you could design such a system to be backwards compatible with
non-PQC recipients, but it clearly has worthwhile considerations beyond
just a standard combiner.

As for leveraging existing systems, I think there will be in general some
protocol specific oddities to look into, even just to ensure that such a
system remains secure and is free from downgrade attacks. My general
opinion is that at least an existing key should never be repurposed to be
used in a hybrid, and any hybrid should create its key material
independently. The same classical key should always be combined with the
same pqc key, and never exist on its own, to the point that higher level
abstractions can ignore the fact that any hybridization happens at all.

[1] https://eprint.iacr.org/2022/1046

On Tue, Feb 20, 2024 at 1:05 PM Watson Ladd <[e-mail]> wrote:

>
>
> On Tue, Feb 20, 2024, 12:54 PM Mike Ounsworth <Mike.Ounsworth=
> [e-mail]> wrote:
>
>> Hi Sophie,
>>
>>
>>
>>
>>
>> I see your point that perhaps this is independently a TLS issue, and an
>> SSH issue, and an OpenPGP, and S/MIME, and JWT issue, but since the
>> cryptographic expertise is concentrated here in CFRG, I would hope that
>> CFRG could provide some overarching advice for protocol WGs to tell if they
>> have implemented the combiner in a sound way – and also have the effect of
>> pushing WGs towards consistency.
>>
>>
>>
>>
>>
>> > Is there a reason to combine arbitrary KEMs, as opposed to
>> specifically combining ECDH and Kyber?
>>
>>
>>
>> First answer: … and RSA … and NTRU … and Classic McEliece … and FrodoKEM.
>>
>
> We SHOULD NOT do this. We need to reduce the number of deployed
> algorithms. There's a big burden here, especially if libraries give up and
> expose a pick two interface (or worse).
>
> This is maybe dreaming, but it would be nice to be able provide a KDF
>> construction which is guaranteed safe for any combination of
>> encryption-like algorithms. That way developers tasked with provided hybrid
>> combinations of different algorithm pairings than those with X-Wing style
>> specs could do so by following the probably-overkill-but-definitely-safe
>> construct.
>>
>
> Developers that do this end up hurting the ecosystem by proliferating the
> set of what must be supported in libraries.
>
>>
>>
>> Second answer: facilitating document review.
>>
>> The original intent of draft-ounsworth-cfrg-kem-combiners was to provide
>> the over-arching security review, and then instantiations of it such as
>> draft-ietf-lamps-pq-composite-kem, draft-wussler-openpgp-pqc,
>> draft-ra-cose-hybrid-encrypt only need to list and justify their deviations
>> from it, rather than each of those documents having complete security
>> analysis that differs from document to document.
>>
>
> No, they should use the resulting KEM like any other kem and not make
> changes. We wouldn't tweak AES in a working group.
>
>>
>>
>>
>>
>> > on the classical side, nobody uses RSA-KEM (a shame, but alas),
>> leaving RSA-OAEP
>>
>>
>>
>> Ugg. This is a good point.
>>
>> Draft-ietf-lamps-composite-kem currently handles the RSA hybrids by
>> referencing RSA-KEM [RFC5990]. Perhaps we should instead or in addition
>> provide ML-KEM + RSA-OAEP.
>>
>> New Issue opened:
>>
>> https://github.com/lamps-wg/draft-composite-kem/issues/21
>>
>
> Encryption isn't a KEM the security notions are a bit different. Shouldn't
> your draft notice this in its construction?
>
>>
>>
>>
>>
>>
>>
>> ---
>>
>> *Mike* Ounsworth
>>
>>
>>
>> *From:* CFRG <[e-mail]> *On Behalf Of *Sophie Schmieg
>> *Sent:* Tuesday, February 20, 2024 1:38 PM
>> *To:* Kousidis, Stavros <stavros.kousidis=[e-mail]>
>> *Cc:* [e-mail]
>> *Subject:* [EXTERNAL] Re: [CFRG] Call for adoption: Hybrid KEM Combiners
>>
>>
>>
>> I agree with all of Ilari's points here. Is there a reason to combine
>> arbitrary KEMs, as opposed to specifically combining ECDH and Kyber? At
>> this point in time, on the classical side, nobody uses RSA-KEM (a shame,
>> but alas), leaving RSA-OAEP
>>
>> I agree with all of Ilari's points here.
>>
>> Is there a reason to combine arbitrary KEMs, as opposed to specifically
>> combining ECDH and Kyber? At this point in time, on the classical side,
>> nobody uses RSA-KEM (a shame, but alas), leaving RSA-OAEP and ECDH as
>> classical mechanisms of key agreement in protocols, neither of which are a
>> KEM. On the PQC side, in the near future, we will have Kyber/ML-KEM as a
>> KEM, with all other KEMs being standardized (by NIST or other orgs) on a
>> substantially later timeline. It does make sense to have a combiner that
>> specifically handles these combinations, and in particular the ECDH+Kyber
>> combination, and that uses the fact that neither are generic KEMs.
>>
>> For protocols like [md]?TLS, SSH, and similar, it makes sense to use the
>> KDF already existing in the protocol to do the combination, and save on
>> hash function calls, given the known security properties of ECDH and Kyber
>> respectively.
>>
>> For asynchronous cases like HPKE or S/MIME, I can see a better story for
>> a generic combiner, but even then, the respective standards already include
>> key derivation in the case of ECDH is used, and S/MIME with RSA-OAEP would
>> require a different approach altogether, given that it uses the non-KEM
>> nature of OAEP to support multiple recipients.
>>
>>
>>
>> This does push the security guarantees of the combined KEM somewhat into
>> the protocol, but arguably that is already the case today when using ECDH
>> based key agreement schemes, as every protocol has their own way of doing
>> that.
>>
>>
>>
>> On Tue, Feb 20, 2024 at 12:04 AM Kousidis, Stavros <stavros.kousidis=
>> [e-mail]> wrote:
>>
>> 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/
>> <https://urldefense.com/v3/__https:/mailarchive.ietf.org/arch/msg/cfrg/84TUdtD0w12qFSNPpdV5ArS4-IE/__;!!FJ-Y8qCqXTj2!fW9i-jLPTEgI8rBX9X11q-V9T5i9bsOFQvO_YOwe7tqdxWw8kMTYv5qMVrx_iH7tDDmZ9OT_VUOnxHTEOymZ1hx7gwP4Iy56MFHj$>,
>> 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
>>
>> _______________________________________________
>> CFRG mailing list
>> [e-mail]
>> https://mailman.irtf.org/mailman/listinfo/cfrg
>> <https://urldefense.com/v3/__https:/mailman.irtf.org/mailman/listinfo/cfrg__;!!FJ-Y8qCqXTj2!fW9i-jLPTEgI8rBX9X11q-V9T5i9bsOFQvO_YOwe7tqdxWw8kMTYv5qMVrx_iH7tDDmZ9OT_VUOnxHTEOymZ1hx7gwP4IxX3-4O1$>
>>
>>
>>
>>
>> --
>>
>>
>> Sophie Schmieg | Information Security Engineer | ISE Crypto |
>> [e-mail]
>>
>>
>> _______________________________________________
>> CFRG mailing list
>> [e-mail]
>> https://mailman.irtf.org/mailman/listinfo/cfrg
>>
>

-- 

Sophie Schmieg | Information Security Engineer | ISE Crypto |
[e-mail]