HNDL Quantum Protection

[neekolas]

The Problem

In XMTP, all ciphertext is public. Messages are encrypted using well established algorithms:

• ED25519 for signatures
• X25519 for key agreement via DHKEM
• CHACHA20POLY1305 for symmetric encrypted using AEAD

While these algorithms protect against threats from conventional computers, the DHKEM is vulnerable to attack from future quantum computers. Adversaries may keep copies of messages on the XMTP network until the day where a sufficiently powerful quantum computer is available to decrypt them. This is often referred to as Harvest Now Decrypt Later.

Post Quantum MLS

Our partners at Cryspen have been working on a complete solution for quantum resistant MLS, which would replace the ciphersuite used in groups with the XWING KEM.

XWING is a hybrid KEM, which combines both post-quantum algorithms with battle-tested conventional cryptography. This hybrid approach ensures that protecting against the threats of tomorrow doesn't inadvertently expose users to threats today.

The performance section of this document is what has given us pause on implementing their proposal. In particular, the size of the ratchet tree can grow dramatically. Each leaf would be ~10X larger. As XMTP decentralizes, the cost and performance of such large payloads would have been prohibitive.

Solving HNDL More Efficiently

Thanks to the design of MLS, we do not need to replace our traditional cryptography everywhere to protect against the Harvest Now Decrypt Later threat.

Quantum computers do not give the same advantages to decrypting symmetrically encrypted payloads as they do to asymmetric encryption.

With a quantum computer private keys can be derived from public keys by taking advantage of Shor's Algorithm, but the only known attack against symmetric keys in 30+ years of research is Grover's Algorithm. Shor's algorithm provides an exponential speed-up, whereas Grover's provides a quadratic speed-up.

That makes Shor's algorithm devastating to 256 bit public keys, while our symmetric encryption keys remain safe against Grover's algorithm. In some cases, a quantum computer using Grover's algorithm may actually be slower than a conventional computer using more modern algorithms.

This difference greatly limits the scope of what is required to get XMTP post quantum protection.

The entry-point for all conversations is the Welcome message. In XMTP this message is encrypted twice using HPKE and X25519. The inner encrypted payload contains all of the group secrets for the current epoch, which can then be used to join the ratchet.

If a quantum computer can decrypt a Welcome, they have access to the full set of leaf nodes for conversation participants. They can then decrypt all messages in the current epoch, and evade forward secrecy and post compromise security by breaking other participant's public keys as the ratchet moves forward.

But if the quantum computer cannot read Welcomes, the rest of the payloads on the XMTP network are useless. They don't have access to the leaf node public keys to break.

So, if we can appropriately secure our Welcome messages against quantum computers the rest of the network is safe.

Proposed solution

The public keys used to encrypt Welcome messages come from Key Packages, which are regularly rotated by clients.

We would amend our format for Key Packages to include both a 25519 public key, and a quantum resistant public key to be used with the XWING KEM (or any other quantum resistant KEM).

Instead of using X25519 for the outer layer of encryption, we would use the post-quantum KEM.

This can be introduced as a non-breaking change. For Key Packages that include an additional post-quantum public key, Welcomes would be sent using post-quantum encryption. For older Key Packages, conventional encryption would be used. As users upgrade to SDK versions that support post-quantum encryption, they will naturally rotate out older Key Packages and replace them with post-quantum ones.

The cost of this change is only the addition of the post-quantum public key in the Key Package, and a greater size of the ciphertext for Welcome messages. Once inside the group, all messages remain the same size.

[neekolas]

Action plan:

1. Switch libxmtp from OpenMLSRustCrypto to libcrux as the crypto provider. This isn't strictly necessary, but the hybrid ciphersuites are only available in libcrux and it probably doesn't make sense to depend on two different crypto libraries. libcrux is formally verified and claims better performance.
2. Create a new Extension type, that is a Key Package Extension, which stores the post_quantum_public_key. Generate a random public key and include it in every key package. Store the corresponding private key in the MLS key/value table when creating Key Packages.
3. When post_quantum_public_key is present in a recipient's Key Package, replace the hpke_encrypt step with a post-quantum HPKE alternative using the XWING/ML-KEM ciphersuite.
4. Add a field to the Welcome envelope payload that indicates which ciphersuite was used for the outer encryption
5. When receiving a Welcome message, use the appropriate ciphersuite to decode the outer envelope based on the field in the Welcome. This will require retrieving the private key from the database, which should have been saved in Step 2
6. Ensure that rotating Key Packages also rotates the post quantum keys and deletes older keys