Post-Quantum OpenMLS

Franziskus Kiefer
April 11, 2024

OpenMLS now offers security against harvest-now-decrypt-later (HNDL) quantum adversaries.

In #1546 we merged support for the X-Wing KEM draft, which is an early draft for securely combining elliptic-curve-based Diffie-Hellman with ML-KEM. In particular, OpenMLS now supports the ciphersuite MLS_256_XWING_CHACHA20POLY1305_SHA256_Ed25519 with ciphersuite 0x004D. There is no IANA code-point for this ciphersuite yet, such that interoperability may not be guaranteed. We work with other implementers towards interoperability of this ciphersuite.

The implementation uses Cryspen’s formally verified ML-KEM and x25519 implementations from libcrux. The implementations are not only formally verified for correctness, secret independence, and memory safety, but also amongst the fastest implementations. Users should not notice any significant performance differences when using this new ciphersuite. The threat of HNDL attackers requires applications to switch to post-quantum secure mechanisms now, just like Signal and iMessage did already. OpenMLS offers a simple way to achieve security against HNDL attackers and is ready to use.


While the new ML-KEM mechanism is very efficient, it requires larger messages and because the ciphersuite used is hybrid (i.e. a combination of ML-KEM the classical x25519 KEM), the workload increases.

The following tables give an overview of the performance and message sizes. One can clearly see an overhead from the post-quantum scheme. While the computation complexity is not too high, and more efficient implementations of ML-KEM may be used, the communication complexity increases significantly due to the larger key and message sizes in ML-KEM.

X-Wing + x25519 x25519
Create Key Package 273.39 µs 138.24 µs
Create Welcome 665.77 µs 366.23 µs
Join a group 733.22 µs 313.37 µs
Self update 650.77 µs 294.49 µs
X-Wing + x25519 x25519
Key package size 2669 Bytes 299 Bytes
Welcome size 5457 Bytes 716 Bytes
Ratchet tree size 4007 Bytes 408 Bytes
Self update size 3954 Bytes 495 Bytes

Next Steps

Using X-Wing as KEM in MLS is the easiest solution to achieve HNDL security for secure group messaging, or any use case that uses the state synchronization protocols specified in MLS.

However, X-Wing is designed as a drop-in KEM scheme with very conservative security guarantees. In the context of MLS, there may be more efficient ways to integrate HNDL protection, for example, by making use of more lightweight KEM combiners, or by other means specific to MLS. In the context of the MLS working group, we are actively discussing multiple proposals for improved HNDL protection. Once more promising candidates are available, we will publish a follow-up of this post.

A new version of OpenMLS will be released later this month, which will include this new, post-quantum secure, ciphersuite.