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
Proposed alpha version
To highlight potential problems and move forward, an alpha version is proposed with:
a new format, "format v2", to ease the migration. Indeed, a new layer is not detected by default by mlar and might be confusing for users (as a silent error). A new format also ease the implementation of breaking changes ;
[X] Key generation outside of MLA -> generation inside MLA code, without giving the API user the chance to unfortunately copy the key. Fixed by #210
[X] Use ml-kem for key generation in MLA #213
[X] Provides a parser/dumper for new MLA Hybrid keys. This is kept ouside of the crate mla as mla can live without the need of ASN.1 serialization #215
[X] remove curve25519-parser #215
[X] re-introduce commented tests from mla needing serialization
[X] update mlar with the new API and keys #215
[ ] document the newly used cryptography #207
[X] finalize and document the hybridation scheme. It might be changed later for a standardized one, but it should at least provide the expected guarantees #217
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:
Proposed alpha version
To highlight potential problems and move forward, an alpha version is proposed with:
mlarand might be confusing for users (as a silent error). A new format also ease the implementation of breaking changes ;ml-kemimplementation https://github.com/RustCrypto/KEMs/tree/master/ml-kemTask tracking, implemented in the formatv2 branch
ml-kemfor key generation in MLA #213mlaasmlacan live without the need of ASN.1 serialization #215curve25519-parser#215mlaneeding serializationmlarwith the new API and keys #215Zeroizationof the private key (needs https://github.com/RustCrypto/KEMs/issues/40, could help #46)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