[openpgp] Re: WG: BSI view on KEM combiners

[Phillip Hallam-Baker <[e-mail]>]

On Sat, Sep 14, 2024 at 2:22 PM D. J. Bernstein <[e-mail]> wrote:

> Phillip Hallam-Baker writes:
> > What is it about combining KEM and ECC outputs that is supposed to be so
> > difficult that HKDF does not already address it?
>
> Sure, 99% of the real-world problem that combiners are supposed to
> address is solved by simply upgrading from "ECDH session key" to "hash
> of ECDH session key and KEM session key", with any of the usual hash
> functions. (Similarly, checking an ECC signature and a PQ signature
> deals with 99% of the problem for signatures.)
>

Ah, now that makes sense, thanks.

An issue folk might want to consider is that hybrid systems might not be
doing 1:1 ML-KEM/PQ encryptions. If I am running a CRM system, I don't get
much leverage from a KEM that doesn't support threshold because I have no
separation of roles. So my configuration is going to be primarily ECC based
with the ML-KEM scheme being limited to backup in the unlikely event
someone builds a CRQC*.


[*] yes, I am aware that $100m just went into startups promising to build a
trapped ion machine. The folk putting the money up are the same folk
managed to make $billions out of promising to transform finance through
blockchain and not doing it.



> However, there are security arguments for having an ECDH+KEM combiner
> hash the full transcript: not just the session keys but also the KEM
> ciphertext, the KEM public key, and both of the ECDH public keys.



> https://eprint.iacr.org/2021/708 and https://eprint.iacr.org/2021/1351
> include arguments for hashing at least a prefix of the public key.
> Having a KEM combiner that includes the ECDH public key and KEM public
> key as extra inputs means that people don't have to worry about the
> possibility of problems here. The arguments in these papers are weak,
> but the counterarguments are weak too.
>

Thanks, arguments may be weak, but cost of the control is minimal.

I am really not sold on the notion this is a combiner issue though, if it
matters at all, it likely matters whether you have one key or many.



> Once one has settled on what to hash, there are further engineering
> questions about the hashing details and about which system component
> should be responsible for each part of the hashing. As an example of
> why this is tricky:
>
>    * KEMs vary in whether they include their own hashing of ciphertexts
>      and of public keys.
>
>    * Kyber said that for "robustness" it was hashing "the entire
>      transcript" to make Kyber "as robust and misuse-resilient as
>      possible". However, NIST then (for unclear reasons) dropped Kyber's
>      ciphertext hashing.
>
>    * X-Wing uses a combiner that (for speed) omits ciphertext hashing.
>      But X-Wing also uses specifically Kyber-768, and has a security
>      analysis claiming that Kyber is still doing something _tantamount_
>      to ciphertext hashing, maybe at a 2^128 security level.
>
> This puts unnecessary load on security reviewers, and I think it'll turn
> out to be fragile. I would just have the combiner hash the transcript so
> that we don't have to worry about whether KEMs are aiming for something
> beyond IND-CCA2 and don't have to worry about whether protocols are
> secure with less hashing. But there's a specific claim that extra
> hashing would cost Google "millions of dollars/CO2 emissions/energy";
> there's a claim that failing outside the Kyber context is a positive
> feature; etc. One can't expect CFRG to have an easy decision here.
>

If people are doing ML-KEM they are already committed to a heck of a lot of
hashing. The fact that Google's operations are so extensive that any
marginal increase in CPU multiplied by billions of operations turns out to
be a lot doesn't seem to be a useful line of argument to me.

The difference between signing every entry in .com rather than just the
entries that had signatures was the difference between a few thousand
operations and hundreds of millions and a 600% increase in data volume.

Seems to me that we should be looking for a composable approach to getting
robust mechanisms for turning KEMs into KDF inputs.


I like to construct any protocol so that there is a digest function between
any quantity an attacker might manipulate and my crypto.

The way that I generate key identifiers in the Mesh is SHA-2-512 (
SubjectKeyIdentifier) so I have a 65 byte quantity (1st byte specifying
SHA-2-512) which is bound to the algorithm and public key. Dropping 70-ish
extra bytes into the KEM should not be a huge inconvenience. One more round
of hashing at most. Seems right for single key encryption.

Will have to think about the two key approach.