Should we have a security proof for the ML-KEM+RSA-OAEP composite KEM?

[johngray-dev]

For a security proof of the ML-KEM + ECDH combos, we can point to the X-Wing paper. We should have a similar proof for the RSA-OAEP combos. Not sure how to go about attracting someone to help with this, or if we should attempt proof-writing ourselves.

[ounsworth]

What we need is some justification of the statement "A composite of ML-KEM and RSA-OAEP is IND-CCA so long as either component is." That breaks down into two cases:

A) "A composite of ML-KEM and RSA-OAEP is IND-CCA as long as RSA-OAEP is": We need some sentence about how the RSA component is bound to the composite. I'm sure this is a single sentence, but I don't know what it is. Next, we claim that RSA-OAEP is IND-CCA, which is proved in [1]

B) "A composite of ML-KEM and RSA-OAEP is IND-CCA as long as ML-KEM is": Here, I think we get to just point at the X-Wing paper. To my reading, it's proof that the QSF framework is allowed to omit the ML-KEM public key and ciphertext from the combiner hinges only on ML-KEM being ciphertext second pre-image resistant, which FO transform based KEM is. To my reading, this should hold for any choice of the second KEM, even a horribly insecure one (which is what we want for a composite).

I am not at all confident about this, and would love for someone with some more academic background to review and help draft Security Considerations text.

[1]: Barthe, G., Grégoire, B., Lakhnech, Y., Zanella Béguelin, S. (2011). Beyond Provable Security Verifiable IND-CCA Security of OAEP. In: Kiayias, A. (eds) Topics in Cryptology – CT-RSA 2011. CT-RSA 2011. Lecture Notes in Computer Science, vol 6558. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19074-2_13

[ounsworth]

I found this:

The original 1994 paper of Bellare and Rogaway [9] proves that, under the hypothesis that the underlying trapdoor permutation family is one-way, OAEP is semantically secure
under chosen-ciphertext attacks.

Also this paper
https://link.springer.com/chapter/10.1007/978-3-642-19074-2_13

contains:

Theorem 1 (IND-CCA security of OAEP)

but it's behind a paywall. Is it cheating to cite it anyway?

[ounsworth]

Maybe I have enough to cobble this paragraph together. Here's an attempt (borrowed heavily from the security consideration of the X-Wing I-D)

Informally, a Composite ML-KEM algorithm is secure if the combiner (HKDF-SHA2 or SHA3) is secure, and either ML-KEM-768 is secure or the traditional component (RSA-OAEP, ECDH, or X25519) is secure.

More precisely, if HKDF-SHA256, HKDF-SHA384, and SHA3-256, may be modelled as a random oracle under multiple concatenated inputs, then the IND-CCA security of X-Wing is bounded by the IND-CCA security of ML-KEM-768, and the IND-CCA security of RSA-OAEP. ML-KEM is known to be IND-CCA secure [FIPS.203] and RSA-OAEP is known to be IND-CCA secure, see [1].

The overall security of the composite inherits the IND-CCA property of RSA-OAEP trivially since the composite combiner binds the RSA-OAEP public key and ciphertext meaning that even if RSA-OAEP is not ciphertext second preimage resistant, any alternate publickey-ciphertext pairs will result in a different output shared secret key. The composite inherits the IND-CCA property of ML-KEM due to the specifics of the Fujisaki-Okamoto transformation used in ML-KEM as proved in [X-Wing]: the Composite combiner cannot be assumed to be secure when used with different KEMs. In particular it is not known to be safe to leave out the post-quantum ciphertext from the combiner in the general case.

[1]: Barthe, G., Grégoire, B., Lakhnech, Y., Zanella Béguelin, S. (2011). Beyond Provable Security Verifiable IND-CCA Security of OAEP. In: Kiayias, A. (eds) Topics in Cryptology – CT-RSA 2011. CT-RSA 2011. Lecture Notes in Computer Science, vol 6558. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19074-2_13

[fluppe2]

I found this:

The original 1994 paper of Bellare and Rogaway [9] proves that, under the hypothesis that the underlying trapdoor permutation family is one-way, OAEP is semantically secure
under chosen-ciphertext attacks.

Also this paper https://link.springer.com/chapter/10.1007/978-3-642-19074-2_13

contains:

Theorem 1 (IND-CCA security of OAEP)

but it's behind a paywall. Is it cheating to cite it anyway?

I think the paper you are looking for is available here: https://software.imdea.org/~szanella/Zanella.2011.RSA.pdf

[fluppe2]

With ML-KEM + RSA-OAEP you leave the QSF Framework described in the X-Wing paper (https://eprint.iacr.org/2024/039), which in its building blocks uses a nominal group (an abstraction of an elliptic curve) and another KEM (ultimately intended to deliver quantum safety but does not harm pre-quantum safety even if it gets broken). The pre-quantum security is therefore reduced to a Diffie-Hellman intractability notion and C2PRI for the KEM.

I think, it is not relevant if RSA-OAEP is C2PRI for your ML-KEM + RSA-OAEP composites, as this is not the security property that RSA-OAEP is asked to deliver in this construction. It is rather that one has to argue that the IND-CCA2-security of the ML-KEM + RSA-OAEP composites (where the RSA-OAEP ciphertext is fed to the combiner) reduce to the IND-CCA2-security of RSA-OAEP and C2PRI of ML-KEM. I guess in that light you are getting closer to a construction given in the paper "KEM Combiners" (https://eprint.iacr.org/2018/024), i.e. one might rather argue along their arguments that one can drop the ciphertext of a C2PRI KEM.

[ounsworth]

Douglas points out that the rsaSS is completely variable-length (chosen by the sender), and the rsaCT and rsaPK may be variable length.

We could add length tag into the combiner input, or maybe more simply is add a step to the Decaps() routine to check the lengths since the decryptor knows what the lengths of all these things should be.

[ounsworth]

Thanks @fluppe2 !

I think, it is not relevant if RSA-OAEP is C2PRI for your ML-KEM + RSA-OAEP composites, as this is not the security property that RSA-OAEP is asked to deliver in this construction. ... i.e. one might rather argue along their arguments that one can drop the ciphertext of a C2PRI KEM.

Yes. This is also my understanding. I guess I did not do a good job of writing it clearly. Thanks for the extra references. I have also asked a few other people to look at this. I'm will do another round of edits.