Signal Protocol

The Signal Protocol is the foundation of Zentalk's end-to-end encryption. It provides forward secrecy, post-compromise recovery, and deniability through a combination of the Extended Triple Diffie-Hellman (X3DH) key agreement protocol and the Double Ratchet algorithm. This chapter describes the conceptual design of both components as deployed in Zentalk, along with security analysis and operational parameters.

Key Types and Lifecycle

Before describing the protocols, we define the key types involved and their lifecycles:

Identity Key Pair (IK)

Each user generates a long-term identity key pair when creating their account. This key pair persists across all conversations and device sessions. A cryptographically secure random seed produces both an Ed25519 signing key pair (for signatures) and an X25519 Diffie-Hellman key pair (for key agreement). The two key pairs are derived from the same seed but operate on different curves, with standard Curve25519 clamping applied to the DH private key.

Lifecycle: Created once. Never rotated unless account is reset. Published as part of the key bundle on the mesh DHT. Loss of the identity key means loss of all encrypted conversations.

Signed Prekey (SPK)

A medium-term X25519 key pair rotated periodically (every 7-30 days) to provide additional forward secrecy. The public key is signed with the user's Ed25519 identity key (covering the key ID, public key bytes, and a timestamp), producing a 64-byte Ed25519 signature that binds the prekey to the user's identity.

Lifecycle: Rotated every 7-30 days. Old signed prekeys are retained for a grace period (90 days) to allow decryption of messages sent with the old key. The signature binds the prekey to the identity, preventing a MITM attacker from substituting their own prekey.

One-Time Prekeys (OPK)

Ephemeral X25519 keys used exactly once to provide additional forward secrecy in the initial key exchange. Each key is consumed after a single X3DH session. Keys are generated in batches, each with a unique identifier.

Lifecycle: Each OPK is used exactly once during X3DH and then permanently deleted. If no OPKs are available, X3DH falls back to 3-DH (without $\text{DH}_4$), providing slightly weaker forward secrecy but still functional encryption. The client periodically replenishes the OPK pool by generating and publishing new batches.

Ephemeral Key (EK)

A fresh X25519 key pair generated for each X3DH key agreement. Never stored or published.

Lifecycle: Generated at the moment of initiating a conversation. Used for $\text{DH}_2$, $\text{DH}_3$, and $\text{DH}_4$ computations. Discarded immediately after the shared secret is derived. The ephemeral nature of this key is critical for forward secrecy -- even if the identity key is later compromised, past ephemeral keys cannot be recovered.

Key Bundle Publication

Before communication can begin, each user publishes a key bundle to the mesh DHT containing all public keys needed for X3DH: their X25519 identity key, Ed25519 signing key, current signed prekey (with signature), available one-time prekeys, a device registration ID, and optionally a Kyber-768 public key for post-quantum hybrid mode.

The bundle is stored on the mesh with a 30-day TTL and re-published periodically. Any user wishing to initiate a conversation fetches the recipient's key bundle from the DHT, verifies the signed prekey signature, and proceeds with X3DH.

X3DH Key Agreement — Detailed Protocol

Initiator Protocol (Alice $\rightarrow$ Bob)

Alice wants to send an initial message to Bob. She fetches Bob's key bundle from the mesh and proceeds as follows.

First, Alice verifies Bob's signed prekey by checking the Ed25519 signature against Bob's identity key and confirming the prekey timestamp is within the 90-day validity window. This prevents a man-in-the-middle attacker from substituting their own prekey. Alice then generates a fresh ephemeral key pair and selects one of Bob's available one-time prekeys (if any remain). She performs four Diffie-Hellman computations, each serving a distinct security purpose:

Computation	Keys Involved	Security Property
$\text{DH}_1 = \text{X25519}(\text{IK}_A, \text{SPK}_B)$	Alice's long-term, Bob's medium-term	Authenticates Alice to Bob (only Alice has $\text{IK}_A$ private)
$\text{DH}_2 = \text{X25519}(\text{EK}_A, \text{IK}_B)$	Alice's ephemeral, Bob's long-term	Authenticates Bob to Alice (only Bob has $\text{IK}_B$ private)
$\text{DH}_3 = \text{X25519}(\text{EK}_A, \text{SPK}_B)$	Alice's ephemeral, Bob's medium-term	Forward secrecy (ephemeral key provides fresh entropy)
$\text{DH}_4 = \text{X25519}(\text{EK}_A, \text{OPK}_B)$	Alice's ephemeral, Bob's one-time	One-time forward secrecy (key deleted after single use)

The combination of all four DH values ensures that compromising any single key type does not break the protocol. An attacker would need to compromise Alice's identity key AND Bob's identity key AND the ephemeral key (which is never stored) to derive the shared secret. If no one-time prekey is available, the protocol falls back to three DH computations (omitting $\text{DH}_4$).

X3DH Key Agreement

Alice

IK_A (Identity Key)

EK_A (Ephemeral Key)

Bob

IK_B (Identity Key)

SPK_B (Signed Prekey)

OPK_B (One-Time Prekey)

DH1: X25519(IK_A, SPK_B)

DH2: X25519(EK_A, IK_B)

DH3: X25519(EK_A, SPK_B)

DH4: X25519(EK_A, OPK_B)

SK = HKDF(DH1 || DH2 || DH3 || DH4)

Press enter or space to select a node. You can then use the arrow keys to move the node around. Press delete to remove it and escape to cancel.

Press enter or space to select an edge. You can then press delete to remove it or escape to cancel.

The Extended Triple Diffie-Hellman protocol combines four independent DH computations to establish a shared secret with mutual authentication, forward secrecy, and one-time key freshness.

The shared secret is derived by concatenating all DH outputs and passing them through HKDF-SHA256 with a Zentalk-specific salt and info string, producing a 32-byte session key $\text{SK}$. Using a protocol-specific salt prevents cross-protocol key derivation attacks where an attacker tricks a user into using their Zentalk keys in a different (potentially weaker) protocol.

Alice then uses $\text{SK}$ as the initial root key for the Double Ratchet and performs an initial DH ratchet step to derive her first sending chain key. She sends an initial message containing her identity key, ephemeral key, the IDs of the signed prekey and one-time prekey she used, and (optionally) a Kyber-768 ciphertext for hybrid post-quantum mode. This initial message is sent alongside the first encrypted payload and contains all information Bob needs to compute the same shared secret.

Responder Protocol

Upon receiving the initial message, Bob validates Alice's identity key, looks up the referenced signed prekey and one-time prekey by their IDs, and performs the same four DH computations with the roles swapped. The commutative property of X25519 ensures both parties derive identical DH values:

$$\text{X25519}(a, b \cdot G) = \text{X25519}(b, a \cdot G) = (a \cdot b) \cdot G$$

Bob derives the same shared secret $\text{SK}$ via HKDF and then permanently deletes the consumed one-time prekey. This deletion is critical: once the OPK is deleted, even if all of Bob's long-term keys are later compromised, the attacker cannot recompute $\text{DH}_4$ and therefore cannot derive the shared secret. Bob initializes his Double Ratchet state, generates a fresh DH ratchet key pair for his reply, and derives both receiving and sending chain keys.

The complete X3DH specification is provided in [Marlinspike and Perrin, 2016].

The Double Ratchet Algorithm

Ratchet State

Each party maintains per-conversation state comprising: a 32-byte root key that evolves with each DH ratchet step; separate sending and receiving chain keys with their message counters; the current DH ratchet key pair (private and public) and the peer's latest DH public key; and bookkeeping structures for the previous chain length, skipped message keys, and used IVs for replay detection.

Symmetric Ratchet (Sending and Receiving)

When sending a message, the sender derives a unique 32-byte message key $\text{MK}$ from the current sending chain key via $\text{HMAC-SHA256}(\text{CK}, \texttt{0x01})$, then advances the chain key by computing $\text{HMAC-SHA256}(\text{CK}, \texttt{0x02})$. The message key is used exactly once to encrypt the plaintext with AES-256-GCM, where the Additional Authenticated Data (AAD) covers the sender's current DH public key and the message number. After encryption, $\text{MK}$ is securely zeroed. The random 96-bit IV is recorded for replay detection.

On the receiving side, the same derivation is performed in reverse: the receiver computes $\text{MK}$ from the receiving chain key, checks the IV against both in-memory and persisted IV stores to detect replay attacks, decrypts via AES-256-GCM (which verifies the authentication tag), and then securely deletes the message key.

Because $\text{HMAC-SHA256}$ is a one-way function in the key direction, even if the chain key at position $i+1$ is compromised, the message key at position $i$ cannot be recovered. This provides per-message forward secrecy.

DH Ratchet Step

The DH ratchet is triggered whenever a message arrives containing a new DH public key from the peer, introducing fresh entropy into the root key. The receiver performs a Diffie-Hellman computation between their current DH private key and the peer's new public key, then passes the result through HKDF (keyed by the current root key) to derive both a new root key and a new receiving chain key. A fresh DH key pair is then generated, and a second HKDF round derives the new sending chain key. This ensures that after one message round-trip, the root key depends on entropy that an attacker who previously compromised the state cannot predict, providing post-compromise recovery.

Double Ratchet Algorithm

Shared Secret (SK from X3DH)

DH Ratchet Step

New DH Key Pair

Generate ephemeral keys

DH Output

ECDH(dh_priv, dh_pub_remote)

DH Ratchet Step

New DH Key Pair

Fresh ephemeral keys

DH Output

ECDH(dh_priv, dh_pub_remote)

Root Key (RK₀)

HKDF

RK + DH Output → new RK + CK

Root Key (RK₁)

HKDF

RK + DH Output → new RK + CK

Root Key (RK₂)

Chain Key (CK₀)

HMAC

CK₁

Message Key (MK₀)

AES-256-GCM Encrypt

Unique key per message

Message Key (MK₁)

AES-256-GCM Encrypt

Unique key per message

Chain Key (CK₀)

HMAC

CK₁

Message Key (MK₀)

AES-256-GCM Encrypt

Unique key per message

Message Key (MK₁)

AES-256-GCM Encrypt

Unique key per message

Press enter or space to select a node. You can then use the arrow keys to move the node around. Press delete to remove it and escape to cancel.

Press enter or space to select an edge. You can then press delete to remove it or escape to cancel.

The Double Ratchet interleaves a DH ratchet (left, providing forward secrecy) with symmetric-key chains (right, deriving unique per-message keys). Each HKDF step consumes the previous root key and a fresh DH output, producing a new root key and chain key. Message keys are derived from chain keys via HMAC and immediately deleted after use.

Skipped Message Key Management

Messages may arrive out of order due to network delays. When a gap in message numbers is detected, the protocol pre-derives and stores the intermediate message keys so that delayed messages can still be decrypted when they arrive. These skipped keys are indexed by the sender's DH public key and message number, and are subject to strict security bounds:

Strict bounds prevent memory exhaustion attacks (capped gap size per conversation, global limit across all conversations), and aged keys are securely zeroed upon eviction.

The complete Double Ratchet specification is provided in [Marlinspike and Perrin, 2016].

Security Analysis

Forward Secrecy

Claim: Compromise of any key at time $t$ does not reveal plaintext of messages sent before time $t$.

Proof sketch:

Message Keys

$\text{MK}_i$ is derived from $\text{CK}_i$ via one-way HMAC. Given $\text{MK}_i$, an attacker cannot recover $\text{CK}_i$.

Chain Keys

$\text{CK}_{i+1}$ is derived from $\text{CK}_i$ via one-way HMAC. Given $\text{CK}_{i+1}$, an attacker cannot recover $\text{CK}_i$.

Root Keys

Derived via $\text{HKDF}$ with fresh DH entropy. The DH ratchet incorporates irreversible randomness, preventing recovery of previous root keys.

Therefore, compromise of any state at time $t$ cannot reveal message keys used before $t$. Each message key exists only briefly in memory, is used once, and is then securely zeroed.

Post-Compromise Recovery

Claim: If an attacker compromises the full ratchet state at time $t$, they lose access to messages after at most one additional DH ratchet step.

Proof sketch:

Fresh Randomness

The DH ratchet generates a new random keypair via the system CSPRNG.

New Root Key

Derived as $\text{HKDF}(\text{X25519}(k_{\text{new}}, P_{\text{peer}}),\; \text{RK}_{\text{compromised}},\; \ldots)$.

Unpredictable

The attacker cannot predict the CSPRNG output, cannot derive the new private key, and therefore cannot compute the new root key.

Recovery occurs after at most one message round-trip (Alice sends with new DH key, Bob responds with new DH key), after which the attacker's knowledge is completely invalidated.

Message Authentication

Claim: A message can only have been sent by the party who possesses the corresponding chain key.

Proof: AES-256-GCM provides authenticated encryption. The authentication tag is computed over both the ciphertext and the Additional Authenticated Data (AAD), which includes the DH public key and message number. An attacker who does not possess the message key $\text{MK}$ cannot produce a valid authentication tag, and any tampering with the ciphertext or AAD will be detected during decryption (the AES-GCM decryption function returns an error rather than potentially incorrect plaintext).

Replay Protection

Zentalk implements three layers of replay protection:

Message Numbers

Each message has a unique, monotonically increasing number. Duplicates are rejected.

IV Uniqueness

Each encryption uses a random $96$-bit IV. Duplicate IVs are tracked and rejected.

Constant-Time Comparison

IV checks use constant-time comparison to prevent timing side-channels.

Operational Limits

Parameter	Value	Security Rationale
MAX_SKIP	1,000	Prevents memory exhaustion attack via gap inflation
MAX_TOTAL_SKIPPED_KEYS	10,000	Global memory bound across all conversations
MAX_MESSAGE_NUMBER	$2^{31} - 1$	Prevents integer overflow; session should be re-established before reaching this
MAX_PREKEY_AGE	90 days	Limits window for signed prekey compromise
SESSION_TIMEOUT	7 days	Forces periodic re-keying
IV_EXPIRATION	7 days	Limits IV storage; aligned with session timeout
SKIPPED_KEY_TTL	30 days	Garbage-collects old skipped keys