With multiple post-quantum cryptographic algorithms (ML-KEM, ML-DSA) nearing standardization, enterprises, research groups, and standards bodies have started investigating what post-quantum secure protocols should look like and what properties they should satisfy.
In this post, we discuss a few new post-quantum protocol designs being proposed for use in end-to-end encrypted messaging protocols like Signal and MLS.
Secure Two-Party Messaging
At Real World Crypto 2024, Rolfe Schmidt and I presented our work (slides, video, blog post), a collaboration between Cryspen, Inria, and Signal, on analyzing the PQXDH protocol which is currently being deployed in the Signal app. In the same session, Apple presented its own PQ3 protocol which is being deployed in iMessage.
PQXDH and PQ3 make some different design choices but both seek to protect two-party conversations from harvest-now-decrypt-later (HNDL) quantum adversaries, who may store messages sent today and decrypt them when a quantum computer becomes available. To this end, they use post-quantum KEMs (specifically ML-KEM or Kyber) in combination with a Diffie-Hellman construction to obtain security against both classical and future quantum adversaries.
The main performance concern in adding a post-quantum KEM to Diffie-Hellman-oriented protocols is that the size of each ciphertext now has an overhead of roughly 1KB. This cost is incurred whenever a new conversation is created in PQXDH or PQ3, and whenever KEM keys are updated in the subsequent ratcheting protocol, which is currently only enabled in PQ3.
Although the change in the protocol may appear small (just throw in some PQ crypto), it has subtle ramifications to the security guarantees. One would expect that the new post-quantum protocol must be strictly stronger than the classical protocol it extends, but this may not be the case if the changes introduce new cross-protocol attacks between the classical and post-quantum protocol. Furthermore, one would expect that the new protocol provides new security guarantees against HNDL adversaries, but this may not be the case if it is vulnerable to key confusion or key re-encapsulation attacks, as we found in PQXDH.
Secure Group Messaging
PQXDH and PQ3 provide compelling designs for secure two-party conversations. But what about group conversations? Do they need new designs and new security analyses?
Signal and iMessage build their group chat features over two-party channels. So, in a group of N=10 members who all actively send messages, we need to set up and maintain 45 (i.e. N*(N-1)/2) two-party channels. Each member sets up and maintains 9 channels. WhatsApp uses Sender Keys, which lowers the overhead for individual chat messages, but still needs 45 channels to set up the group and communicate modifications to the group membership.
These quadratic-cost protocols work fine for small groups but do not scale so well as group sizes grow, both in terms of bandwidth and computational cost. Consider, for example, the overhead of creating and sending N*(N-1)/2 PQ-KEM ciphertexts to create short-lived groups for an event with hundreds or thousands of attendees.
Enter Messaging Layer Security (MLS), a protocol designed to be efficient for large messaging groups. The initial design for MLS relied on an ingenious design called Asynchronous Ratcheting Trees (ART), which uses a tree of Diffie-Hellman operations to derive and distribute group keys, in a way that group creation requires 2N Diffie-Hellman operations, but modifications can be performed with log(N) operations at the sender and at each recipient. This yields a group key agreement protocol that is significantly more efficient and scalable than protocols based on a quadratic number of two-party channels.
In 2018, some colleagues and I proposed TreeKEM, a protocol that uses a tree of KEM and KDF operations to derive group keys, so that the member proposing a group change computes log(N) KEM encapsulations but all other members only need to download and decrypt 1 KEM ciphertext. Due to its improved efficiency at recipients, TreeKEM was adopted by the MLS working group. TreeKEM and its variants, including the version used in the published MLS RFC, have undergone multiple security analyses, yielding both pen-and-paper proofs and machine-checked symbolic security proofs.
Notably, TreeKEM’s reliance on a generic IND-CCA KEM construction makes it trivial to update with a post-quantum KEM. All the security proofs published for TreeKEM continue to hold against classical adversaries when using an IND-CCA PQ-KEM. This, of course, does not mean that TreeKEM with a PQ-KEM provides HNDL security. That requires further security analysis.
More Efficient PQ Group Messaging
TreeKEM as used in the MLS RFC may not be the most efficient construction for post-quantum group messaging. In particular, MLS assumes that all group members receive, verify, and maintain the full membership tree, which can requires large messages to be sent to each member, which can be particularly prohibitive in the PQ setting.
In 2019, my co-authors and I explored a series of group messaging protocol designs, including Chained mKEM: a protocol that uses a multi-recipent KEM (or mKEM) to distribute group keys. In this protocol, creating or updating a N-member group costs N-1 KEM encapsulations at the sender and a single decapsulation at the receiver. So, it is more efficient than quadratic two-party channels but less efficient than TreeKEM.
However, it turns out that in the post-quantum setting, it is possible to design efficient mKEM constructions that make Chained mKEM a compelling design for small to medium groups. In our session at RWC 2024, Thomas Prest from PQShield presented a PQ group messaging protocol based on Chained mKEM that uses clever ciphertext compression techniques. It still scales linearly with the number of group members, but with a significantly smaller coefficient.
Following a different approach, we at Cryspen have been working, in collaboration with Cisco and Wickr, on a backwards-compatible variant of MLS called Light MLS, where the cost of bandwidth, storage, and processing at passive or light clients is always log N. This protocol has currently been proposed for discussion in the MLS working group.
Summary
The post-quantum transition has started already, but it is important that the new protocols are formally assessed both against classical as well quantum adversaries. Or else we may end up in the unfortunate situation of deploying a protocol that weakens security in both settings.
MLS is designed to efficiently operate with KEMs and is proven to be secure in the classical setting when using any IND-CCA KEM, including ML-KEM. Indeed, you can use MLS with ML-KEM or your favourite hybrid-KEM construction today. Several groups are investigating even more efficient group messaging protocols in the post-quantum settings. However, all of these group protocols require more security analyses against quantum adversaries.
To learn how Cryspen can help you with the post-quantum transition, or to understand what post-quantum guarantees protocols like PQXDH or MLS can give you, contact us at info@cryspen.com