Consider adding Post-Quantum cryptography with hybrid KEM for the encryption layer

[commial]

Objectives

As the MLA archives might last several years, "harvest now decrypt later" attacks must be considered.
To avoid this kind of attack, post-quantum resistant cryptography should be use.
To avoid pre-quantum flaw of these recent algorithms, hybridation must be used.

This issue is made to track the discussions, improvements and design choices regarding the availability of post-quantum (PQ) cryptography in MLA.

Algorithm choice

The NIST competition lead to several finalists [0].
Still, one candidate seems to be more and more adopted: ML-KEM (Kyber).

While the competition is still recent, it has been integrated in Signal [1] and iMessage [2].
It is not perfect, and some have already highlighted concerns [3] [9].

Yet, it is still in line with the French suggestions [4] for PQ cryptography.

So, this algorithm seems to be a reasonable choice in its stronger form (Kyler-5).

Implementation

Crate

Several Rust implementation of Kyber are available ([5] [6] [7] [8] ...).
To the best of my knowledge, none of them has yet received an external review, contrary to the others implementation used in MLA.
Some of them claims to be "verified" [5], even if these steps might involve "unverified" pass (such as translation from a language to another).

IMHO, for now, it is difficult to make a choice among these implementations.

Hybrid KEM

The pre and post quantum keys must be mixed together.
[4] gives some advice and warn about naive scheme.

[1] and [2] both have implemented hybrid schemes. They can serve as inspiration, but the goals are not the same as MLA. In particular, they handle signatures for both participants and Ratchett.

Let's note $ss_1$, $ss_2$ the shared secrets resulting from two KEM (for instance, the pre and the post-quantum ones) and $ct_1$ and $ct_2$ their corresponding ciphertext (used to recover the shared secrets using KEM's private key).

If at least one of the KEM scheme is IND-CCA, we want the resulting scheme to be IND-CCA as well.
[10] urges that the "naive" scheme $ss = KDF(ss_1 . ss_2)$ might not be IND-CCA.

The paper introduces other schemes, which globally falls in 2 categories: "concatenation" and "cascade" schemes.
For instance, the "concatenation" scheme $ss = KDF(ss_1 . ss_2 . ct_1 . ct_2)$ is proven OK in [10].

[11] go further and highlights that the usage of the "Fujisaki-Okamoto" transform by Kyber allow to reduce the constraint by removing $ct_2$ from the calculation.
Regarding MLA, I rather prefer keeping a conservative approach, as there is no need for performance in the KEM part and this result is only verified for Kyber.

Both TLS [12] and IKE [13] seem to also go for a concatenation scheme.

Integration in the format

If a crate is choosen to implement the PQ cryptography part, other questions must be answered:

• is this a format update (MLA v1 -> MLA v2) or rather a new layer in the existing format?
• in this last case, should we keep available the both layer (encrypt and encryptPQ) or the "old" layer might ends deprecated and no more usable for new archives?
• what format should be used for key? For now, the format is compliant with OpenSSL

References

[0] https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
[1] https://signal.org/docs/specifications/pqxdh/
[2] https://security.apple.com/blog/imessage-pq3/
[3] https://blog.cr.yp.to/20231003-countcorrectly.html
[4] https://cyber.gouv.fr/en/publications/follow-position-paper-post-quantum-cryptography
[5] https://cryspen.com/post/ml-kem-implementation/
[6] https://github.com/Argyle-Software/kyber
[7] https://lib.rs/crates/kyber-pke
[8] https://docs.rs/pqcrypto-kyber/latest/pqcrypto_kyber/
[9] https://kyberslash.cr.yp.to/
[10] F. Giacon, F. Heuer, and B. Poettering. Kem combiners, Cham, 2018
[11] https://eprint.iacr.org/2024/039
[12] https://datatracker.ietf.org/doc/draft-ietf-tls-hybrid-design/
[13] https://datatracker.ietf.org/doc/html/rfc9370

Updates

• Add Hybrid KEM references