Signal Protocol Post Quantum Security

Signal Protocol

In a world where smartphones are ubiquitous, it is important to have a way to securely and conveniently communicate with one another asynchronously without anybody else being able to spy on the messages. The Signal Protocol is an End-to-End Encrypted (E2EE) messaging protocol. At its core, it uses the Extended Triple Diffie-Hellman key exchange (X3DH) and the Double Ratchet algorithm to provide encrypted communication. It was initially developed by Trevor Perrin and Maxie Marlinspike of Open Whisper Systems in 2013 under the name TextSecure. Since then it has undergone multiple revisions with additions such as voice and video calling. It is used in a variety of apps such as Signal, WhatsApp, and more. In this article, I'll focus on X3DH. Unfortunately, the protocol is not post-quantum secure (PQ-secure), which can be attributed to its heavy reliance on Diffie-Hellman. This text gives a broad overview of the solutions presented so far on how to secure the handshake against a quantum adversary.

Properties of the Signal Protocol

The Signal Protocol has all the properties one would expect from an E2EE messaging protocol, but also some, which make it quite unique. As the source for the properties and their respective definitions, I will directly use Unger et al's definitions.

• Confidentiality: Only the intended recipients are able to read a message. Specifically, the message must not be readable by a server operator that is not a conversation participant.
• Integrity: No honest party will accept a message that has been modified in transit.
• Authentication: Each participant in the conversation receives proof of possession of a known long-term secret from all other participants that they believe to be participating in the conversation. In addition, each participant is able to verify that a message was sent from the claimed source.
• Forward Secrecy: Compromising all key material does not enable the decryption of previously encrypted data.
• Backward / Future / Post-compromise Secrecy: Compromising all key material does not enable the decryption of succeeding encrypted data.
• Plausible Deniability
  • Message Repudiation: Given a conversation transcript and all cryptographic keys, there is no evidence that a given message was authored by any particular user. [...]
  • Message Unlinkability: If a judge is convinced that a participant authored one message in the conversation, this does not provide evidence that they authored other messages.
• Asynchronicity: Messages can be sent securely to disconnected recipients and received upon their next connection.

There are some other properties of the Signal Protocol, however, these are less noteworthy compared to the ones mentioned above.

Extended Tripple Diffie-Hellman Handshake (X3DH)

The handshake protocol consists of three phases. First keys are created and then uploaded to the server. To perform a handshake, the interested party downloads the respective key bundle from the communication partner stored on the server and calculates their shared secret. They then send the first encrypted messages with the required key material attached. When the other user receives the message, they can perform the shared secret calculation and decrypt the first message.

Required Keys

The public key of each pair is uploaded to the server.

Intiate Handshake

Assuming Alice wants to write Bob. She first downloads a key bundle including, if available, a one-time key as well. She verifies the signature of SPK and then generates an ephemeral key pair EK. With these keys, she performs three or four DH calculations:

Alice then concatenates the keys and inputs them into a Key Derivation Function (KDF) to get the Shared Key (SK) she can use for encrypting her message. Besides the ciphertext, she includes identifiers for the SPK and OPK she used as well as her identity and ephemeral public key.

Receive Handshake

When Bob comes online and receives the message, he extracts Alice's keys and loads his own. With these, he performs the DH calculations ending up with the same SK to decrypt the ciphertext.

Quantum Secure X3DH

Since the original implementation uses elliptic curve DH, which can be efficiently broken using Shor's quantum algorithm, it is important to upgrade the protocol to a PQ-secure version. In 2017 NIST started a Post-Quantum Cryptography Standardization program for KEMs and Signature Schemes. One very interesting candidate SIKE / SIDH had the possibility of being a great replacement for DH. Research into making Signal quantum secure was oftentimes built on top of SIDH. However, it was broken in 2022 on a classical computer. Now research focuses on using Key Encapsulation Mechanisms (KEMs).

===Using SIDH===/ SIDH allows the creation of a shared secret similar to DH. It is based on Supersingular Isogeny. Even though SIDH is not secure, looking into possible implementations can give insight into quantum secure protocol design. Consider one of the last Signal SIDH publications “Post-Quantum Signal Key Agreement with SIDH” by Samuel Dobson and Steven D. Galbraith which was published in March 2022. It employs a Zero Knowledge Proof to prevent then already known adaptive attacks against SIDH.

References

1. Ermoshina, K., Musiani, F. & Halpin, H. End-to-end encrypted messaging protocols: An overview in International Conference on Internet Science (2016), 244–254.
2. Marlinspike, M. WhatsApp’s Signal Protocol integration is now complete Signal Technology Foundation. https://signal.org/blog/whatsapp-complete/ (2022).
3. Unger, N. et al. SoK: Secure Messaging in 2015 IEEE Symposium on Security and Privacy (2015), 232–249.
4. Marlinspike, M. The X3DH Key Agreement Protocol tech. rep. (Nov. 2016). https://signal.org/docs/specifications/x3dh/x3dh.pdf, archived at https://web.archive.org/web/20221205210600/https://signal.org/docs/specifications/x3dh/x3dh.pdf on Dec. 5, 2022.