Signal

---

An informal introduction to the Signal protocol

References:

• [X3DH] The X3DH Key Agreement Protocol, Marlinspike and Perrin, 2016.
• [Double Ratchet] The Double Ratchet Algorithm, Perrin and Marlinspike, 2016.
• [Sesam] The Sesame Algorithm: Session Management for Asynchronous Message Encryption, Marlinspike and Perrin. 2017.
• [PQXDH The PQXDH Key Agreement Protocol, Kret and Schmidt, 2023
• [WhatsApp] WhatsApp Encryption Overview: Technical white paper, 2023.
• [CDGS] A Formal Security Analysis of the Signal Messaging Protocol, Cohn-Gordon et al. 2020
• [CCG] On Post-compromise Security, Cohn-Gorden et al. 2016
• [CPZ] The Signal Private Group System and Anonymous Credentials Supporting Efficient Verifiable Encryption, Chase et al. 2020
• [VGIK] On the Cryptographic Deniability of the Signal Protocol, Vantandas et al. 2021
• [BFGJS] Post-quantum Asynchronous Deniable Key Exchange and the Signal Handshake, Brendel et al. 2022

Signal Protocol

• Origins date back to TextSecure App started in 2010
  • TextSecure used a double ratchet construction referred to as Axolotl Ratchet to highlight ''self-healing properties''

• Later TextSecure was merged with RedPhone into Signal in 2015
  • maintained by a non-profit organization called Open Whisper Systems
• 2018 Open Whisper Systems was transformed into Signal Foundation
  • recent podcast with CEO Meredith Whittaker LNP504

Signal Protocol Usage

• Integrated into WhatsApp since 2016
• Also used by Wire, Facebook Messenger, Silent Circle, Pond, XMPP via OMEMO, ChatSecure, ...

Messanger	Installations	Estimated Users
WhatsApp	9.64 Billion	2 Billion [ref.]
Facebook Messenger	5.89 Billion	?
...
Signal	136 Million	?

Signal Protocol Design Goals

Aims to provide end-to-end encrypted (E2EE) conversations for asynchronous (mobile) messaging, as well as a series of other (informally stated) security properties, such as the following three:

1. Perfect Forward Secrecy (PFS): After a session has been established, this property ensures that an attacker that compromises one device (and thus has access to the long- and medium-term secrets) is not able to learn anything about the keys derived in previous sessions. In other words, the attacker is not able to decrypt previously sent messages he might have recorded in transit.

2. Post Compromise Security (PCS): This property is also referred to as healing or future secrecy and was first formally described in [CCG]. It refers to the property that even if an attacker is able to compromise one device during a conversation for a limited amount of time, not content of future conversations might still regain some protection.

3. (Offline) Deniability: Refers to the ability that a party can deny having participated in a particular communication session in retrospect. Assuming a communication session between Alice and Bob. Given a transcript of the communication it should not be possible for Bob to convince a third party that Alice has participated knowingly in the session.

Signal Protocol Overview

The Signal Protocol can be further devided into the following parts:

• X3DH (extended triple Diffie-Hellman) key agreement
  • since late 2023 replaced by PQXDH, which is coceptually close but adds an additional post-quantum secure key encapsulation mechanism (KEM) into the key derivation function (KDF)
• Double ratchet algorithm
• Sesam session management for multi-device support, e.g., phone and desktop
• Group chats and private groups where the server has no record of group membership
• The underlying library libsignal is written in rust and can be found on github

Signal Protocol Overview

It uses the following cryptographic primitives:

• unkeyed primitives:
  • SHA256 hashfunction
• symmetric primitives:
  • HMAC-SHA256
  • HKDF with SHA256
  • Authenticated encryption with associated data (AEAD) using AES256 in CBC mode with PKCS#5 padding and HMAC-SHA256 as MAC
• asymmetric primitives:
  • DH over curve X25519, or curve X448
  • Ed25519 as signature scheme
  • ML-KEM from FIPS-203 (variant of CRYSTALS-Kyber PQ-KEM)
  • Keyed-Verification Anonymous Credential (KVAC)

X3DH and the Double ratchet

(excalidraw) (image)

Sesam for Multi Device Support

Modern messengers thrive to support the usage of multiple devices by the same user, e.g., a mobile app and a desktop client.

1. leader based: The primary device -- typically a smart phone -- acts as a leader and serves as the EE2E endpoint pretending that there is only a single device per user. The leader device then distributes the messages, also in an encrypted way, to the other devices of the user, also referred to as companion devices [B].

2. client fan-out: All devices of the user maintain their own key pair. For messaging, the sender creates an individual E2EE channel with each device of the receiver as if messaging multiple recipients [Sesam].

(image source)

Current Preprint Paper

• Careless Whisper: Exploiting Stealthy End-to-End Leakage in Mobile Instant Messengers
• Use delivery receipts to gather information about clients, or exhaust their resources

EOF