Re: [CFRG] Proposed CFRG hybrid KEM scope (was: "Millions of dollars of hashing")

[Ilari Liusvaara <[e-mail]>]

On Thu, Feb 22, 2024 at 11:01:05PM +0000, Scott Fluhrer (sfluhrer) wrote:
> Here is a thought that occurred to me.
> 
> Suppose we had an existing protocol that used a key exchange (either
> DH or KEM) to generate keys.
> 
> In particular, this protocol performs a DH or KEM operation to
> generate a shared secret S, computed A := I(S) (where I is the
> identity function – why I call that out will be obvious) and then took
> A and used that somehow in its key derivation protocol.  We will also
> assume that this unmodified protocol meets some unspecified security
> goals.
> 
> Now, we take this protocol and make it hybrid; we perform two DH/KEM
> operations which generate two shared secrets S, T, and then we compute
> A := Hash(S, T) (where Hash is a secure hash function), and then took
> A, and used it in the exact same way in its key derivation protocol.
> 
> We will further assume that one of the DH/KEM operations turns out to
> be weak (and to the extent that the attacker can freely control its
> output)
> 
> The obvious question is: does this updated protocol still meet the
> unspecified security requirements?  That is, can replacing the
> identity function I with a hash of the secret along with attacker
> controlled material add a vulnerability to the protocol that wasn’t
> already there?

It can introduce weaknesses that were not already there.

The standard security notion used for this is IND-CCA2:
indistinguishability under adaptive chosen ciphertext attack.

If S and T are outputs of two KEMs that meet IND-CCA2, then Hash(S, T)
still might not meet IND-CCA2.

Turns out there is exactly one way this can happen: If attacker can come
up with another ciphertext for either KEM that still decapsulates to the
same shared secret, then IND-CCA2 security breaks down.

The way to fix this is to add ciphertext for DH and KEMs where such
thing is possible.

Fortunately, turns out that for ML-KEM (FIPS-to-be 203), finding such
ciphertext is equivalent difficulty to 2nd preimage attack against
SHA3-256. Any practical attack complexity would totally destroy SHA-3.

So if ML-KEM is paired with some DH, then only the DH part (which is
very small) of the ciphertext needs to be hashed. If this does not
cause more hash blocks to be needed, this is very cheap thing to do.

Another question is if this failure mode can introduce practical
vulnerability. The answer in most cases seems to be no: Finding another
ciphertext that decapsulates to the same shared secret does not seem to
be anything helpful for an attacker. And in fact, many protocols let
the attacker to trivially do just that.

This is in contrast to single KEMs that fail IND-CCA2. Those failure
modes are usually something very nasty. E.g., being completely broken
or processing malformed ciphertexts leaking the private key.

However, crypto libraries are important consideration. One wants as few
combinations as possible, and more importantly, there not to be
variants. Thus one wants to make the construct to be IND-CCA2 secure.
Frequently this is extremely cheap to do.


Protocols that do very exotic things beyond IND-CCA2 require separate
analyis. The property might turn out to be something that is ruined
by one component not having it. Or it might not propagate through
combiner even if all components have it.

Furthermore, it is much more difficult to find information about
properties of various KEMs beyond IND-CCA2. And such properties can turn
out to be flawed. Recently that happened with signature security
property called NR, turns out there is no way to meet it.




-Ilari