First Impressions Matter: On Signal's Initial Handshake

Nowadays, people rely on smartphones and messaging apps for private communication. Several of these messaging apps use the Signal protocol, giving it a combined userbase of billions of users. The Signal protocol aims to achieve confidentiality and deniability of the communication, among other properties. In this thesis I focus on the first part of the protocol, the initial handshake, which is used to establish a shared key between two users.

Originally, Signal used X3DH, which is based on the Diffie–Hellman key exchange, as the initial handshake protocol. In this thesis, I introduce two replacement protocols for the initial handshake, both of which achieve better security guarantees than X3DH in different aspects: On the one hand, we introduce XHMQV, which extends Krawczyk's HMQV protocol (CRYPTO '05) to the setting of Signal. XHMQV achieves better maximal-exposure security, i.e., it resists more compromise scenarios, than X3DH. On the other hand, our protocol SPQR is a generic construction based on Key Encapsulation Mechanisms (KEMs) and a Designated Verifier Signature (DVS). Hence, SPQR can be instantiated with post-quantum primitives and thereby avoid the vulnerability against quantum adversaries that X3DH suffers from. We prove confidentiality and a flavor of deniability for both protocols.

Since 2023, Signal uses PQXDH as initial handshake protocol, which extends X3DH with a KEM to protect against attackers that monitor all communication today to decrypt with a future quantum computer (called harvest now decrypt later (HNDL) attack). In this thesis I further analyze PQXDH in three different aspects. First, we show that it achieves confidentiality against both classical and quantum adversaries. Second, we prove that PQXDH mostly keeps the deniability guarantees of X3DH with an extra assumption on the KEM and subject to modeling choices wrt. a signature that is only used once. Third, we study deniability against malicious verifiers: We give a definition for DVS, a construction achieving this definition in the random oracle model (ROM), and a proof that a DVS cannot achieve this definition without sacrificing unforgeability in the standard model. Furthermore, we disprove deniability of X3DH and PQXDH against malicious adversaries in its full generality.

Heutzutage nutzen Menschen Smartphones und Messaging Apps für private Kommunikation. Mehrere dieser Messaging Apps nutzen das Signal-Protokoll, wodurch es von Milliarden Menschen weltweit verwendet wird. Das Signal-Protokoll hat zum Ziel unter anderem Vertraulichkeit und Abstreitbarkeit der Kommunikation sicherzustellen. Diese Thesis konzentriert sich auf den ersten Teil des Protokolls, den initialen Handshake, der benutzt wird um einen gemeinsamen Schlüssel zwischen zwei Nutzer:innen zu etablieren.

Ursprünglich hat Signal X3DH, das auf dem Diffie–Hellman-Schlüsselaustausch basiert, für den initialen Handshake verwendet. Diese Thesis stellt zwei Ersatzprotokolle für den initialen Handshake vor, die beide in verschiedenen Aspekten bessere Sicherheitsgarantien erreichen als X3DH: Einerseits präsentieren wir XHMQV, das Krawczyk's HMQV Protokoll (CRYPTO '05) auf die Rahmenbedingungen von Signal erweitert. XHMQV erreicht bessere maximal-exposure security als X3DH, d.h. es gibt mehr Kombinationen von kompromittierten Schlüsseln denen das Protokoll standhält. Andererseits stellen wir unser Protokoll SPQR vor: eine generische Konstruktion basierend auf Key Encapsulation Mechanisms (KEMs) und einer Designated Verifier Signature (DVS). Somit lässt sich SPQR mit post-quantum Primitiven instanziieren, womit es im Gegensatz zu X3DH die Verwundbarkeit gegen Quantenangreifer meidet. Wir zeigen für beide Protokolle, dass sie Vertraulichkeit und eine Variante von Abstreitbarkeit garantieren.

Seit 2023 benutzt Signal PQXDH für den initialen Handshake, welches X3DH um eine KEM erweitert. Damit schützt PQXDH gegen Angreifer, die heute sämtliche Kommunikation überwachen und mit einem künftigen Quantencomputer entschlüsseln (genannt harvest now decrypt later (HNDL) Angriff). Diese Thesis analysiert weiterhin PQXDH hinsichtlich drei verschiedener Aspekte. Erstens zeigen wir, dass PQXDH Vertraulichkeit gegen klassische Angreifer und Quantenangreifer erreicht. Zweitens beweisen wir, dass PQXDH größtenteils die Abstreitbarkeitsgarantien von X3DH behält, sofern die KEM eine zusätzliche Annahme erfüllt und vorbehaltlich einer Modellierungsfrage zu einer Signatur, die nur ein mal verwendet wird. Drittens untersuchen wir Abstreitbarkeit gegen bösartige Verifizierer: Wir geben eine Definition für DVS, eine Konstruktion, die diese Definition im Random Oracle Model (ROM) erfüllt, und einen Beweis, dass keine DVS diese Definition im Standardmodell erfüllen kann ohne Unfälschbarkeit aufzugeben. Weiterhin widerlegen wir die Abstreitbarkeit von X3DH und PQXDH gegen bösartige Angreifer im Allgemeinen.