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.