View source for Signal Protocol Post Quantum Security

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==
For the protocol, each participant requires two and a set of key-pairs. The public keys are uploaded to the server.
* Identity Key <math>^{\mathrm{pre}}\mathrm{IK}_{\mathrm{X}}</math>
** Used for authentication, can be checked before or after handshake
* (Signed) Prekey <math>^{\mathrm{pre}}\mathrm{SPK}_{\mathrm{X}}</math>
** Used for forward secrecy
* Set of one-time pre-keys <math>^{\mathrm{pre}}\mathrm{OPK}_{\mathrm{X}}</math>
** Used for (better) forward secrecy

==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 <math>\big[</math>four<math>\big]</math> DH calculations:

<math>
^{\mathrm{pre}}k_\mathrm{1} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{IK}_{\mathrm{A;priv}}, ^{\mathrm{pre}}\mathrm{SPK}_{\mathrm{B;pub}}) 
</math>

<math>
^{\mathrm{pre}}k_\mathrm{2} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{pre}}\mathrm{IK}_{\mathrm{B; pub}})
</math>

<math>
^{\mathrm{pre}}k_\mathrm{3} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{pre}}\mathrm{SPK}_{\mathrm{B; pub}})
</math>

<math>
\big[^{\mathrm{pre}}k_\mathrm{4} = \mathrm{DH}(^{\mathrm{pre}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{pre}}\mathrm{OPK}_{\mathrm{B; pub}})\big]
</math>

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.

===SI-X3DH===
The proposed protocol is a slight modification of standard X3DH. Instead of Diffie-Hellman SIDH is employed. At the time of publishing it was known, that SIDH was susceptible to adaptive key attacks. Thus the protocol applies methods of ensuring honest key generation. The ephemeral key used is generated through the Fujisaki-Okamoto (FO) transformation. <math>\pi</math> can be used by the recipient for an FO-proof. For each identity the owner uploads a non-interactive zero-knowledge proof to the server, ensuring the owner is in possession of the private key. Since this proof is apparently resource intensive, this proof is omitted for <math>^{\mathrm{post}}\mathrm{SPK}_{\mathrm{X}}</math>. Thus the <math>k_1</math> calculation needs to be modified, replacing <math>^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B;pub}}</math> with <math>^{\mathrm{post}}\mathrm{IPK}_{\mathrm{B;pub}}</math>. This change slightly weakens forward security, since now <math>k_1</math> is static between two users and a breach of an identity key would be more severe. The protocol relied solely on SIDH, without any classical security.

<math>^{\mathrm{post}}k_\mathrm{1} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{IK}_{\mathrm{A;priv}}, ^{\mathrm{post}}\mathrm{IK}_{\mathrm{B;pub}})</math>

<math>^{\mathrm{post}}k_\mathrm{2} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{IK}_{\mathrm{B; pub}})</math>

<math>^{\mathrm{post}}k_\mathrm{3} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B; pub}})</math>

<math>\big[^{\mathrm{post}}k_\mathrm{4} = \mathrm{SIDH}(^{\mathrm{post}}\mathrm{EK}_{\mathrm{A; priv}}, ^{\mathrm{post}}\mathrm{OPK}_{\mathrm{B; pub}})\big]</math>

<math>\mathrm{SK} = \mathrm{KDF}\left(^{\mathrm{post}}k_1 \mathbin{\Vert} ^{\mathrm{post}}k_2 \mathbin{\Vert} ^{\mathrm{post}}k_3 \big[\mathbin{\Vert} ^{\mathrm{post}}k_4\big]\right) </math>

<math>\pi = s \oplus H_2(^{\mathrm{post}}k_1) \oplus H_2(^{\mathrm{post}}k_2) \oplus H_2(^{\mathrm{post}}k_3) \big[\oplus H_2(^{\mathrm{post}}k_4)\big]</math>

==KEM-based approaches==
KEMs seem to be the most promising path for creating a PQ-secure Signal protocol. NIST already announced a winning KEM from their competition: CRYSTALS-Kyber. The algorithm uses lattices as its security anchor. For a great explanation of Kyber see the following video: https://media.ccc.de/v/rc3-2021-cwtv-230-kyber-and-post-quantum

===Tutanota's Proposal===
Tutanota is a German open-source email service offering E2EE emails between customers. To be protected against future quantum adversaries, they proposed an updated hybrid Signal protocol. The handshake protocol is built on top of classical X3DH. The scheme uses Kyber-786 as KEM and Dilithium 1280x1024 as a quantum-secure signature scheme. Each classic key pair gets a PQ-secure pendant. After verification of the downloaded key bundle, Alice additionally performs the following encapsulations:

<math>(c_\mathrm{2}, ^{\mathrm{post}}k_\mathrm{2}) = \mathrm{encaps}(^{\mathrm{post}}\mathrm{IK}_{\mathrm{B; pub}})</math>

<math>(c_\mathrm{3}, ^{\mathrm{post}}k_\mathrm{3}) = \mathrm{encaps}(^{\mathrm{post}}\mathrm{SPK}_{\mathrm{B; pub}})</math>

<math>\big[(c_\mathrm{4}, ^{\mathrm{post}}k_\mathrm{4}) = \mathrm{encaps}(^{\mathrm{post}}\mathrm{OPK}^i_{\mathrm{B; pub}})\big]</math>

All resulting keys are then combined using the KDF. Since it is not possible to calculate a PQ-secure pendant to ^{\mathrm{pre}}k_\mathrm{1}, the authentication of Alice is missing. To overcome this the authors proposed for Alice to sign the handshake message to Bob. While this enables mutual authentication, the deniability is weakened. It can be cryptographically proven, that Alice sent the handshake message to Bob. To improve deniability, Hashimoto et al proposed ring signatures to be used, enabling anonymous signing of the data. However, a PQ-secure instantiation appears to be very complex and needs more research.

===PQXDH===
In May 2023 Signal published the first revision of the PQXDH protocol, intended to replace X3DH. Similar to Tutanota's proposal it's a hybrid protocol. Currently, it is only a slight modification of X3DH. As of September 2023, Signal added PQXDH to all Signal apps, enabling some quantum secure handshakes. As KEM Kyber-1024 is used. Each user generates a set of one-time PQ-secure keys <math>^{\mathrm{post}}\textrm{PQOPK}_{X}^i</math> including signatures and a last resort (semi-)static <math>^{\mathrm{post}}\textrm{PQSPK}_{X}</math>. The server hands out one-time keys until they are exhausted. During the handshake, Alice encapsulates a secret using Bob's public key:

<math>(c_\textrm{pq}, ^{\mathrm{post}}k_\textrm{pq}) = \textrm{encaps}(^{\mathrm{post}}\textrm{PQPK}_{B; pub})</math>

The additional key is added to the KDF. This construction enables protection against passive quantum adversaries and prevents "harvest-now-decrypt-later" approaches. However, the protocol adds no PQ-secure mutual authentication, and thus would be susceptible to an active quantum adversary. This decision is very deliberate since this simple construction keeps a high level of deniability.

==References==
# Ermoshina, K., Musiani, F. & Halpin, H. End-to-end encrypted messaging protocols: An overview in International Conference on Internet Science (2016), 244–254.
# Marlinspike, M. WhatsApp’s Signal Protocol integration is now complete Signal Technology Foundation. https://signal.org/blog/whatsapp-complete/ (2022).
# Unger, N. et al. SoK: Secure Messaging in 2015 IEEE Symposium on Security and Privacy (2015), 232–249.
# 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.
# Dobson, S., & Galbraith, S. D. (2021). "Post-Quantum Signal Key Agreement with SIDH." Cryptology ePrint Archive, Paper 2021/1187. Retrieved from https://eprint.iacr.org/2021/1187.
# Stadler, S., Sakaguti, V., Kaur, H., & Fehlhaber, A. L. (2021). "Hybrid Signal protocol for post-quantum email encryption." Cryptology ePrint Archive, Paper 2021/875. Retrieved from https://eprint.iacr.org/2021/875.
# Hashimoto, K., Katsumata, S., Kwiatkowski, K., & Prest, T. (2021). "An Efficient and Generic Construction for Signal's Handshake (X3DH): Post-Quantum, State Leakage Secure, and Deniable." Cryptology ePrint Archive, Paper 2021/616. DOI: 10.1007/s00145-022-09427-1. Retrieved from https://eprint.iacr.org/2021/616.
# Kret, Ehren, and Rolfe Schmidt. "The PQXDH Key Agreement Protocol." Retrieved from https://signal.org/docs/specifications/pqxdh/pqxdh.pdf