Quantum Resistance and the Signal Protocol

ehrenkret on 19 Sep 2023

An abstract illustration of a Bloch Sphere

The Signal Protocol is a set of cryptographic specifications that provides end-to-end encryption for private communications exchanged daily by billions of people around the world. After its publication in 2013, the Signal Protocol was adopted not only by Signal but well beyond. Technical information on the Signal Protocol can be found in the specifications section of our docs site.

Today we are happy to announce the first step in advancing quantum resistance for the Signal Protocol: an upgrade to the X3DH specification which we are calling PQXDH. With this upgrade, we are adding a layer of protection against the threat of a quantum computer being built in the future that is powerful enough to break current encryption standards.

This post is written to introduce this work to non-experts, and will review what quantum computing is and the challenges it presents for current cryptographic algorithms, before providing a high level overview of how we are adapting our specifications to answer these challenges. If you would like to skip this summary and explore our PQXDH specification in depth, you can read our technical whitepaper here.

Public Key Cryptography Primer

In order to explain why quantum computers pose a risk to existing cryptographic algorithms, it is first necessary to understand some of the broad strokes of how these algorithms work. The most logical place to start is with the RSA Cryptosystem, because it provides an accessible example.

The RSA Cryptosystem is one element in a category of algorithms known as public key cryptosystems. Public key cryptosystems make it possible for someone to publish a public key that anyone can use to encrypt messages to that person. The person keeps a related private key which allows them to decrypt any message that has been encrypted with their published public key.

In order to make this work, RSA relies on a mathematical one-way function. A one-way function is easy to compute in one direction, but requires substantially more work to compute in reverse. The one-way function RSA relies upon is the multiplication and factorization of large prime numbers. It is computationally easy to multiply two large primes together to compute the product, but much more computationally intensive to find the original primes from their product.

The RSA cryptosystem works by first picking two large prime numbers at random and publishing the product of the two as one part of a public key. The selected prime numbers are kept private. This relies upon the difficulty of factoring this product to keep the two primes secret.

Although we have used RSA as an example to aid this primer, Signal does not use the RSA Cryptosystem in its protocols. Instead, Signal uses elliptic curve cryptography as the public key cryptosystem supporting many of its specifications. Instead of prime integer factorization, as in the RSA example above, elliptic curve cryptography relies upon the discrete logarithm problem as its one-way function. While these two problems are distinct, they are both instances of a mathematical problem known as the hidden subgroup problem.

Quantum Computing

Quantum computing represents a new type of computational system which leverages quantum mechanical properties to solve certain complex problems many orders of magnitude more quickly than modern classical computers. Instead of bits as in a classical computer, quantum computers operate on qubits. Rather than 0 or 1, qubits can exist in a superposition of states, in some sense allowing them to be both values at once. One place where quantum computers appear to have a significant advantage over classical computers is solving instances of the hidden subgroup problem.

Quantum computing is unlikely to replace or supplant classical computers for our day-to-day use for the foreseeable future because classical computers are often better at the typical use cases for our laptops, tablets, and phones. Quantum computing systems will likely be built to take alternate approaches to some of the problems we rely on supercomputers to tackle today, whether this is modeling protein folding, forecasting weather, or factoring large numbers. It’s important to understand that quantum computers are not “better” computers but rather different types of computers.

Although quantum computers already exist, the systems known to exist today do not yet have enough qubits to pose a threat to the public-key cryptography that Signal currently uses. However, if a sufficiently powerful quantum computer were built in the future, it could be used to compute a private key from a public key thereby breaking encrypted messages. This kind of threat is known as Harvest Now, Decrypt Later (HNDL).

The timeline for when a sufficiently powerful quantum computer may be created is a matter of great debate. On the low end, some argue it is only a couple of years away. On the high end some say 30+ years, and there are even those who assert that we may never solve the challenges necessary to make a quantum computer with enough coherent qubits to break the current public key cryptosystems. The middle ground seems to be around the 5 to 10 year time horizon. We are not in a position to judge which timeline is most likely, but we do see a real and growing risk which means we need to take steps today to address the future possibility of a large enough quantum computer being created.

Securing Signal Against a Future Quantum Computer

To address this problem, new post-quantum cryptosystems have been created to implement new one-way functions that cannot be advantageously reversed by a quantum computer. Thanks to innovation from cryptographic researchers and the NIST Standardization Process for Post-Quantum Cryptography we now have stable options that have been created and vetted by a large community of experts.

Even with the contributions of a community of experts, building and evaluating these new cryptosystems remains a challenging endeavor. During NIST’s standardization process, one of the post-quantum algorithm candidates was found to be attackable by a classical computer. While this shows that the scrutiny of the standardization process is working, it also suggests that one should integrate these new post-quantum options cautiously.

We believe that the key encapsulation mechanism we have selected, CRYSTALS-Kyber, is built on solid foundations, but to be safe we do not want to simply replace our existing elliptic curve cryptography foundations with a post-quantum public key cryptosystem. Instead, we are augmenting our existing cryptosystems such that an attacker must break both systems in order to compute the keys protecting people’s communications.

The essence of our protocol upgrade from X3DH to PQXDH is to compute a shared secret, data known only to the parties involved in a private communication session, using both the elliptic curve key agreement protocol X25519 and the post-quantum key encapsulation mechanism CRYSTALS-Kyber. We then combine these two shared secrets together so that any attacker must break both X25519 and CRYSTALS-Kyber to compute the same shared secret.

Our new protocol is already supported in the latest versions of Signal’s client applications and is in use for chats initiated after both sides of the chat are using the latest Signal software. In the coming months (after sufficient time has passed for everyone using Signal to update), we will disable X3DH for new chats and require PQXDH for all new chats. In parallel, we will roll out software updates to upgrade existing chats to this new protocol.

Future Work

PQXDH protects messages exchanged on Signal against the threat of a future quantum computer. We will need to make further upgrades to address the threat of an attacker with a contemporaneous quantum computer. Further research in the area of post-quantum cryptography will be needed to fill in the remaining gaps. We recommend reading the security considerations section of our PQXDH whitepaper for more information on the areas of open research.

Acknowledgements

We want to extend our sincerest thanks and appreciation to all the people who contributed to the development of this protocol upgrade. This includes the cryptographic research community, the Kyber team, and the following people who directly contributed to our whitepaper: