5
$\begingroup$

It is widely known that elliptic curve Diffie-Hellman is vulnerable to maliciously crafted public keys, where a honestly generated private key combined with a malicious public key may result in predictable output. Are KEM algorithms resistant to similar attacks?

Consider the following scenario with respect to KEM algorithms in general. Mallory creates an encapsulating key and sends it to Alice. Alice carries out an encapsulation operation using good quality random source, getting a shared secret and a ciphertext. One would hope that even if Mallory created the encapsulating key maliciously, the shared secret and ciphertext still has good entropy, and there is no way for Mallory or anyone else to guess them before Alice sends the ciphertext to Mallory.

  1. Is there a name for the security property described above? (As in a name like IND-CCA2 or MAL-BIND-K-CT, making it easy to search for)

  2. Is this security property an explicit goal in KEM design, or is it a side effect of some other security properties considered in KEM design, or is it generally not considered?

  3. Do existing KEMs have this security property? I'm mostly interested in ML-KEM, as it is the only one standardized by NIST at the moment, but answers about other KEMs are welcome too.

Background: consider the following protocol:

  • Bob generates a KEM keypair and send the encapsulating key to Alice
  • Alice does an encapsulation, sends the ciphertext to Bob, then encrypts a message with a symmetric AEAD cipher using the shared secret as key and sends the message ciphertext to Bob
  • Bob does a decapsulation, and use the shared secret to decrypt Alice's secret message

(This is essentially the pqNN handshake in Post Quantum Noise.)

If the KEM being used does not have the aforementioned security property, then across multiple transactions, either Bob or an active MitM can use malicious encapsulation keys to force the same shared secret, leading to catastrophic key reuse.

Improve this question
New contributor
twisteroid ambassador is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
  • 1
    $\begingroup$ "It is widely known that elliptic curve Diffie-Hellman is vulnerable to maliciously crafted public keys, where a honestly generated private key combined with a malicious public key may result in predictable output." Actually, there are well known ways to protect against that. For prime order curves (e.g. P256), all you need to do is verify that the public key is a point on the curve (and not the point at infinity). $\endgroup$ Commented 4 hours ago
  • 1
    $\begingroup$ @poncho nit: the criterion is cofactor=1; all the X9/SECG $F_p$ curves were so chosen, as were Brainpool's, but not Bernstein's 25519 and 448 and possibly others. $\endgroup$ Commented 33 mins ago

2 Answers 2

Reset to default
3
$\begingroup$

that elliptic curve Diffie-Hellman is vulnerable to maliciously crafted public keys

That probably doesn't include Montgomery curves and DH instantiated from it, such as Curve25519/X25519: https://www.rfc-editor.org/rfc/rfc7748.

For Diffie-Hellman, the aim of a malicious public key is to, as you say, generate predictable output. This is possible due to:

  1. in finite field, the discrepancy between the additive group and multiplicative group,
  2. in elliptic curve, the discrepancy between the order of the group and the underlying field.

These are attacks against the "subgroup", which are of small order (i.e. easily predictable) (answer to your Q1)

I'm not aware of similar discrepancy with module lattice, or with error-correcting codes, other than that, they apply Fujisaki-Okamoto (or other) transform(s) to obtain CCA security from CPA public-key encryption. (answer to your Q3).

The FO transform used by ML-KEM also hashes the public key, making the output unusable with other instances of the handshake. (answer to your Q2)

The interface of KEM is also worth discussion. Unlike key exchange, the duty of Alice and Bob are not symmetric, so there would be no point in trying to obtain the encapsulator-side secret.

clarification

(from comments)

I do not believe that Fujisaki-Okamoto protects against malicious public keys. ...

Nor do I. What I'm saying (and are quoted from my answer above) is:

1.

The FO transform used by ML-KEM also hashes the public key, making the output unusable with other instances of the handshake.

... there would be no point in trying to obtain the encapsulator-side secret.

I did not imply that it's impossible to obtain the encapsulator-side secret. In fact, reproducing the client-side secrets is precisely part of the process of FO-transform.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If I understand correctly, you're saying that KEMs using Fujisaki-Okamoto construction should be immune from the attack? $\endgroup$ Commented 16 hours ago
  • $\begingroup$ @twisteroidambassador Assuming they're built sans mathematical loopholes like that subgroup thing. $\endgroup$ Commented 15 hours ago
  • 2
    $\begingroup$ I do not believe that Fujisaki-Okamoto protects against malicious public keys. What it protects against are malicious ciphertexts. The FO transform is run by the decapsulator (Bob in your example); this attack is against Alice, who does not perform it. $\endgroup$ Commented 13 hours ago
  • $\begingroup$ @poncho Clarified my intent. $\endgroup$ Commented 15 mins ago
2
$\begingroup$

In the specific case of ML-KEM, it does in fact provide the 'entropy' property you are looking for, at least for the generated shared secret. That is, no matter how the public key is chosen, the shared secret generated by Alice is well distributed (that is, unpredictable before Alice actually performs the encapsulation operation).

This can be seen by looking at the internals of ML-KEM (and I'll be citing the algorithms and steps from FIPS 203)

In it, Alice selects a random value $m$ (step 1 of Algorithm 20). Then, it generates a shared secret $K$ by hashing that random value (and the hash of the public key, this is step 1 of Algorithm 17).

Now, this hash function (denoted $G$ in the algorithm, and is SHA3-512) is a strong hash function, that is, even if one of the inputs are chosen maliciously, the output is unpredictable if enough of the input bits are unpredictable (which they are in this case).

And, the shared secret $K$ is the value returned to Alice (step 3 of Algorithm 17), and is hence uncontrollable by Bob.

On the other hand, the ciphertext generated by Alice need not be well distributed (even against random valid ML-KEM ciphertexts; those consist of packed values between $0$ and $q-1$, and since $q$ is not a power of two, they can be distinguished from a random string). For example, Bob can output an all-zero public key. When Alice processes it, then in Algorithm 14, the $\hat{t}$ value will be all zero, and so the $NTT^{-1}( \hat{t}^{\intercal} \circ \hat{y} ) + e_2 + \mu$ value computed in step 21 will just be $e_2 + \mu$, and since this value is made part of the ciphertext after encoding (in step 23), this can be distinguished from random. In fact, anyone observing this value can recover $\mu$, which allows them to recover $m$ and thus the shared secret.

On the other hand, Bob could have this 'someone else could recover the shared secret' effect by just generating the public key honestly based on a well-known seed, and so this later fact is less ominous than it sounds.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.