Encrypted Messaging and Ratcheting

If Alice and Bob share a secret key and want to communicate securely, they simply need to use authenticated encryption. Is there anything else to say?

Authenticated encryption ultimately derives all of its security guarantees from the secrecy of its key. A rational adversary will not waste their effort on cryptographic attacks against a secure AE scheme; a much smarter strategy would be to simply try to steal the key. These days, we store our lives—including our keys—on small portable devices that are easy to lose and easy to steal. If Alice and Bob's shared key is successfully stolen, then all security properties evaporate: The adversary can read all their correspondence, past or future, and can also impersonate Alice and Bob to each other! In short, this key is a single point of failure for all their security properties.

Of course we can't expect security if the adversary obtains Alice and Bob's secret key. But do the consequences really need to be quite so severe? This chapter addresses the question:

17.1. Forward secrecy and the symmetric ratchet

Forward secrecy means, informally, that an adversary who learns a user's secrets at time $t$ learns nothing about things that happened before time $t$. For example, if Alice and Bob's secrets get stolen today, the adversary should not be able to decrypt the ciphertexts they exchanged yesterday, or last year.

Forward secrecy requires users to continuously evolve their secret key material over time. If Alice could decrypt Bob's message at time $t$, but an adversary who steals Alice's secrets at time $t+1$ cannot, then Alice's secrets must have changed in the meantime.

The simplest way to achieve forward secrecy is called the symmetric ratchet. It is based on the idea of iterating a PRG, similar to the way construction 5.4.2 increases the stretch of a PRG. A ratchet allows users to generate a sequence of keys, each of which is meant to be used for a short period of time—say, to encrypt or decrypt just a single ciphertext. The lifespan of each key is called an epoch, and these short-term keys are called epoch keys. The name “ratchet” suggests that the sequence of keys can be advanced only forward in time, and not reversed.

You can imagine this ratchet mechanism being used in the following way. Alice and Bob agree on an initial secret ratchet key $R$. Each time they want to exchange a message, they advance the ratchet to obtain the next epoch key, which they use to encrypt/decrypt the message. Since the symmetric ratchet is deterministic and both users start with the same initial value, they produce the same sequence of epoch keys.

It is important that users discard epoch keys as soon as they are used, and discard old ratchet keys as soon as they are advanced. Only the current ratchet key should be stored, and thus our attack scenario considers the effects of an adversary stealing the ratchet key. Such an adversary can inevitably compute all future epoch keys, but we can argue that all previous epoch keys appear pseudorandom.

Discussion: The symmetric ratchet is a general-purpose technique. It produces a sequence of epoch keys that can be used for anything, not just encryption. It is noninteractive, meaning that in principle two users don't need to communicate anything extra to use the technique. However, synchronization can be lost and problems can arise if messages between the users are lost or arrive out of order.

Remember: The security proof assumes that when the adversary steals a victim's secrets, it learns only the current ratchet key and nothing else. Thus, a symmetric ratchet is only as good as a user's ability to effectively erase old keys.

17.2. Post-compromise secrecy and the asymmetric ratchet

Forward secrecy makes a compromise powerless against the past. The complementary property is called post-compromise secrecy: An adversary who learns a user's secrets at time $t$, learns nothing about things that happen after time $t$ (or, more generally, after time $t+w$ for some small fixed constant $w$). In other words, the system quickly “heals itself” from the effects of a compromised secret.

The symmetric ratchet does not provide post-compromise secrecy, because anyone who holds the current ratchet key can compute the entire sequence of all future epoch keys. Post-compromise secrecy demands an interactive method, where the users continuously inject new randomness into the system.

The asymmetric ratchet, sometimes called continuous key agreement, is a simple variant of Diffie-Hellman key exchange in which the two users continuously renegotiate the current key. In basic Diffie-Hellman, one user sends $g^a$, the other sends $g^b$, and they take $g^{ab}$ to be the shared key. In the asymmetric ratchet, they take turns sending $g^{a_1}, g^{a_2}, g^{a_3}$, etc. When the most recent message sent was $g^{a_t}$, the current epoch key is $g^{a_{t-1}\cdot a_t}$.

It's easy to see that each $a_i$ exponent is used for two epoch keys: $g^{a_{i-1} a_i}$ and $g^{a_i a_{i+1}}$. The user who sends $g^{a_i}$ will need to store $a_i$ until it receives $g^{a_{i+1}}$, so that it can compute the next epoch key $g^{a_i a_{i+1}}$ as $(g^{a_{i+1}})^{a_i}$. After that, it is safe to erase $a_i$.

So an adversary who steals secrets from a user in epoch $t$ will learn only their most recent exponent $a_t$. This is enough information to compute the current epoch key (because $g^{a_{t-1}}$ has already been published) as well as the next one (when $g^{a_{t+1}}$ is published). However, these are the only epoch keys that are affected by the leakage of $a_t$; all other epoch keys will remain pseudorandom. The adversary cannot “fast-forward” the asymmetric ratchet like the symmetric ratchet, because the next epoch keys depend on randomness that has not yet been sampled. Hence, the asymmetric ratchet heals itself from compromise after two epochs.

Fine print: The attack scenario for continuous key exchange is complicated and subtle, primarily due to the highly interactive nature of these protocols, and the fact that the adversary can adaptively reveal secret information. Our simple overview of the asymmetric ratchet has also glossed over the possibility of an adversary tampering with or replaying the users' protocol messages. For these reasons, a full and proper treatment of the asymmetric ratchet's provable security is a research-level task far beyond the scope of this book.

17.3. The double ratchet and the Signal protocol

The Signal protocol for secure messaging was developed for the Signal encrypted messaging application, and later adopted by WhatsApp, Facebook Messenger, and other popular messaging applications. These mobile applications are used for long-term conversations, often years in length, on devices that can be easily lost, stolen, or cloned. As such, the goal of the Signal protocol is to provide the strongest possible forward secrecy and post-compromise secrecy guarantees.

This section explores how Signal uses ratcheting techniques in real-world messaging. We will assume that the two users start with an initial shared secret key; later, in chapter 18 we will discuss the problem of how they first obtain that key while authenticating each other's identities.

Why not use the asymmetric ratchet? The asymmetric ratchet of section 17.2 provides both forward secrecy and post-compromise security. However, so far we have considered an attack scenario in which an adversary merely observes network traffic passively. In the real world, we are also interested in protecting users from a more active adversary.

To be more specific, an active adversary who can manipulate network traffic can hijack an asymmetric ratchet session from a victim, with very low effort. Assume Alice has just sent a DH message $g^{a_i}$ to Bob.

• The adversary, posing as Bob on the network, responds with its own $g^{a_{i+1}}$, for an exponent $a_{i+1}$ that it chooses.

• Alice will treat $g^{a_i \cdot a_{i+1}}$ as the next epoch key, but the adversary can compute this key as well. Hence, the adversary can read any messages encrypted with this epoch key.

The adversary can continue to take control over the session, as long as it is able to impersonate Bob on the network.

The Signal protocol makes the adversary's task harder by using what it calls a double ratchet. The first step is to extend the usual symmetric ratchet to take two inputs at each step: the ratchet key and an new auxiliary input.

The idea of having two inputs is that an adversary cannot predict the next epoch key unless it knows both of these inputs. Knowing just one of them is not enough.

The double ratchet is a combination of the asymmetric ratchet and this augmented symmetric ratchet. The DH keys generated by the asymmetric ratchet are used as the additional inputs to the symmetric ratchet:

A double ratchet makes it harder to hijack a session. Even if an adversary impersonates a victim on the network and injects their own $g^{a_i}$ message, they can learn only one of the two ratchet inputs. If an adversary wants to take over the session, they must both steal Alice's current ratchet key (leftmost vertical arrow) and actively inject their own DH protocol message.

Non-alternating messages: The picture of the double ratchet assumes that the users strictly alternate sending messages. But most online chats do not work that way: Alice might send a few messages while Bob is offline, and she should not have to wait for his response. The most obvious way to support consecutive messages from Alice is to have her encrypt them under the same epoch key:

In any good encryption scheme, it is safe to encrypt multiple messages under a single key. However, reusing the key erodes forward secrecy. Suppose Bob has temporarily gone offline, and Alice has sent ten messages under the same epoch key $\key_i$. An adversary who steals Alice's secrets after this point would be able to decrypt all ten of these messages. Ideally, stealing Alice's secrets shouldn't help the adversary read any past messages.

A better approach would be to continue advancing the symmetric ratchet upon every message, even without receiving anything from Bob. Since there will be no new DH messages, Alice can use a fixed value $\bit0^\secpar$ as the extra ratchet input, and the ratchet will collapse to the simple (single-input) ratchet from section 17.1. After each message, Alice advances the ratchet and erases the previous epoch key.

Now if Alice sends many messages in a row, an adversary who steals her secret state will be unable to read the past messages. In the picture above, an adversary who steals $\key_4$ is not able to learn any previous keys.

Losing synchronization: Suppose Alice and Bob each send a message simultaneously. Having different perspectives on the “correct” order of messages, they will update their ratchets in different ways. Once the ratchets have lost synchronization, it becomes very hard for them to resynchronize. After all, it is by design that the ratchet cannot be reversed back to the last known “safe” value.

Signal handles this case by branching into a secondary ratchet. Whenever a user sends a new DH message in the asymmetric ratchet, they start a new branch from the primary ratchet. The secondary ratchet is just a simple symmetric ratchet that does not use the extra input.

Each secondary branch is used by one user for sending/encryption and by the other for receiving/decryption. When Alice advances the asymmetric ratchet, she starts a new sending branch and can close her previous sending branch. But she can keep her latest receiving branch active, in case Bob has sent messages that have not yet arrived.

Fine print: The Signal protocol is intricate and complicated. There are many details that have been omitted from this high-level overview: how to deal with messages received out of order, how to confirm receipt of messages, and so on. We also have not discussed security properties in a formal way. Due to the complexity of the protocol and its attack scenario, formal proofs of security are a research-level task.

17.4. Group messaging and MLS

Messaging Layer Security (MLS) is a protocol for encrypted group messaging, recently standardized by the Internet Engineering Task Force (IETF) in July 2023. The techniques in the previous sections are specialized for two users, and there is no obvious way to generalize them to larger groups, mainly because there is no obvious way to generalize DHKE to more than two users. Thus, the heart of the MLS standard is a ratcheting technique for groups, which is significantly different from the techniques we've seen so far. Because the multi-user setting is significantly more complicated than the two-user setting, even more details are omitted and simplified in this section.

The design goals for MLS are:

• A group of (two or more) users should agree on a common key, known only to them.

• The group key should evolve/ratchet in a series of epochs to provide forward secrecy and post-compromise security: If an adversary steals the secrets of a group member, ideally only the current epoch should be compromised. Group keys from future and past epochs should remain pseudorandom to the adversary. (As we shall see, there are limits on how well this can be achieved.)

• Finally, the cost to advance the ratchet in a group of $n$ members should be much less than $n$.

As in the previous sections, our focus is on how the group members maintain an evolving key, which we assume can be used for encryption or anything else.

Ratchet trees: The MLS protocol uses a concept called a ratchet tree:

• The members of the group are arranged as the leaves of a balanced binary tree. To keep things simple, let's assume that the number of group members is a power of 2, so that the tree is complete. With $n$ users, the tree has height $\log n$.

• Every node in the tree, including each leaf, is associated with a keypair for a PKE scheme.

• Every group member knows all the public keys in the tree.

• Every group member knows the private keys along the entire path from its leaf to the root.

• The private key at the root is the group key. According to the previous invariant, all group members know this group key. (Technically speaking, the root node does not need a public key, but the examples in this section include one for consistency.)

Below is an example ratchet tree for eight users, numbered 1 through 8, each associated with a leaf. Each node is associated with a keypair $(\pk_{[i:j]}, \sk_{[i:j]})$, for the subtree covering users $i$ through $j$. The leaf nodes correspond to a single user, and we write those keypairs as simply $(\pk_i,\sk_i)$.

In this example, the path from user #3 to the root is highlighted to indicate that user #3 knows private keys $\sk_3$, $\sk_{[3:4]}$, $\sk_{[1:4]}$, and the group key $\sk_{[1:8]}$.

Advancing the ratchet: Any user can advance the ratchet tree to the next epoch by unilaterally choosing new keypairs along its path from leaf to root. Continuing with our eight-user example tree, user #3 could update the tree by sampling new keypairs in the highlighted path:

Then, user #3 must distribute information about these new keypairs to the group members, to maintain the ratchet tree's invariants. First, they can broadcast the new public keys to the group, because all members must know the public keys of all nodes. Next, they must ensure that all members know the private keys along their own path to the root. For example, user #2 must learn the updated keys $\sk'_{[1:4]}$ and $\sk'_{[1:8]}$.

This is the step where the tree structure is useful. Many users need to learn the same new private keys, and what's more, the users that need to learn the same new keys comprise an entire subtree. For example, users 1 and 2 both need to learn the same new keys, and they are the leaves of a single subtree. Users 5 through 8 also need to learn the same new keys, and they are the leaves of a different, single subtree.

Each subtree has its own keypair, so we can send new information to an entire subtree by broadcasting one ciphertext addressed to that keypair. In the illustration below, a dashed line from node $X$ to node $Y$ means that the private key at node $X$ is encrypted to the public key at node $Y$.

The general rule is that if $X$ is a node on the update path, then the new private key $\sk'_{X}$ is encrypted under the public keys of $X$'s children. One of its children is also on the update path, and it is important to encrypt using that child's new keypair. The only exception is for the leaf node corresponding to the user initiating the update; this user already knows all the new key material (having chosen it), so no ciphertext is needed.

Given these ciphertexts, every user can now compute the new root group secret. Along that user's path from leaf to root, all new key material is encrypted under a key that the user knows (or will learn). If the tree has height $h$, then the updating user needs to publish fewer than $2h$ ciphertexts. The total cost is therefore logarithmic in the number of users.

Post-compromise security: Suppose user #$i$'s secrets are stolen by the adversary, then the adversary can certainly compute the current value of the group key. Does the system heal itself, preventing the adversary from computing group keys in future epochs? Yes, but not immediately. Post-compromise healing is not possible until the affected user #$i$ initiates an update.

To understand why healing doesn't happen faster, consider the moment that the user's secrets are stolen. At that moment, the victim (user #$i$) and the adversary know the same information. They can both perform identical updates based on information that they receive. The victim will be able to learn the new group keys, and so will the adversary. The system can heal only when user #$i$ injects new randomness into the system that the adversary doesn't know. This happens only when user #$i$ initiates a ratchet update.

Forward secrecy: Forward secrecy also requires some time to take effect. To understand why, consider the scenario shown in the diagram above, in which user #3 has just updated the tree. At the time of this update—let's call it time $t$—user #4's private key $\sk_4$ can decrypt enough ciphertexts to learn the new group key. Furthermore, user #4 will continue to hold $\sk_4$ until they themselves initiate an update. If the adversary steals their secrets anytime between time $t$ and user #4's next update, then the adversary will learn the group key from epoch $t$, breaking forward secrecy.

17.4.1. Updatable PKE

The forward secrecy of ratchet trees can be improved, so that it takes effect immediately. In the previous example, forward secrecy takes effect slowly because user #4 holds a private key $\sk_4$ that can unlock the current epoch key, and she continues to hold the key until initiating an update. We can fix the problem by providing a mechanism where she updates her key by simply receiving an update. This mechanism is called an updatable PKE (UPKE) scheme. It is not currently part of the MLS standard, but has been proposed as an extension.

Suppose Alice has a keypair in a UPKE scheme. Any sender can publish an update ciphertext, which has the following effects:

• Based on this ciphertext, Alice can replace her old keypair $(\pk,\sk)$ with a new one $(\pk',\sk')$.

• Anyone who sees this update ciphertext and knows Alice's old public key $\pk$ can compute her new public key $\pk'$.

Importantly, the sender who generated the update ciphertext cannot compute Alice's new private key. In other words, the sender does not simply choose Alice's new key for her; the mechanism must be more sophisticated than that.

El Gamal UPKE: Rather than discuss a general-purpose security definition for UPKE, we will instead discuss a specific construction based on El Gamal. An El Gamal keypair $(\pk,\sk)$ has the form $\sk=a$, $\pk=g^a$. The idea behind an update feature for El Gamal is that the sender can choose a translation of the keypair. More specifically, a sender chooses an exponent $r$ such that the updated key will have the form $\sk' = a + r$ and $\pk' = g^{a+r}$.

• The update ciphertext will contain an encryption of $r$ that only the receiver can open. The receiver can decrypt this ciphertext and compute its new private key $\sk' = a +r$.

• The update ciphertext will contain the public value $g^r$. Now anyone who sees the ciphertext can compute the new public key $\pk' = \pk \cdot g^r = g^a \cdot g^r = g^{a+r}$.

Even the sender who chose $r$ will not know the receiver's new private key $\sk'$, because it did not know the original key $\sk=a$.

UPKE security: We will not formally establish a security guarantee for UPKE, but the basic idea is that:

Think about what this means in the context of forward secrecy. If the updated keypair is completely independent of the original keypair, then stealing the updated private key cannot help to decrypt ciphertexts encrypted under the original public key.

One aspect that makes the security analysis of UPKE tricky is that there will be an intermediate hybrid that needs to encrypt a value related to the scheme's private key. The usual CPA security definition for El Gamal does not allow this: A CPA adversary cannot choose a plaintext that depends on the private key. One must instead use an El Gamal variant that incorporates a random oracle, and then apply some delicate, ad hoc reasoning about ciphertexts that encrypt values related to the private key.

Returning to the ratchet tree: Equipped with a UPKE scheme, we can improve the forward secrecy of the ratchet tree. The main idea is that each time the updater encrypts a sensitive value to some $\pk$, it also generates an update ciphertext so that the receiver[s] can update that keypair to a new value. The receiver[s] will replace their private key with the updated one.

In other words, whenever a user decrypts a ciphertext, it immediately replaces its private key with a new one that is not able to decrypt any past ciphertexts. At any given moment, no user ever holds a secret value that is helpful for learning past epoch keys. Thus, UPKE allows the ratchet tree to achieve forward secrecy instantly.

Other fine print: The MLS standard must account for many real-world complications which we have not discussed here. We have assumed that the group has an unchanging membership, but the MLS protocol must support safely adding and removing users from the group. We have assumed that ratchet updates happen in the same order for all group members, but in a real-world messaging app two users may initiate simultaneous updates that reach different group members in a different order. Each of these real-world complications adds considerable complexity to the MLS standard and its security analysis.

Exercises

1. Let $\G$ be a cyclic group with order $\nmod$ and generator $g$. The asymmetric ratchet produces a sequence Diffie-Hellman keys where each exponent is reused in two keys; for example, $g^{a_1 \hl{\scriptsize a_2}}, g^{\hl{\scriptsize a_2} a_3}, \ldots$. Prove that reusing exponents in this way results in pseudorandom output keys. That is, if the DDH assumption is true in this group, then the following two libraries are indistinguishable.

   $\subname{advance}(\,)$:

   $i := i+1$

   // global array

   $a[i] \gets \Z_\nmod$

   $A := g^{a[i]}$

   if $i == 1$:

   $\key := \myundef$

   else:

   $\key := g^{ a[i-1] \cdot a[i] }$

   return $(A, \key)$

   $\indist$

   $\subname{advance}(\,)$:

   $i := i+1$

   $A \gets \G$

   if $i == 1$:

   $\key := \myundef$

   else:

   $\key \gets \G$

   return $(A, \key)$

2. Suppose two users execute an asymmetric ratchet, exchanging five DH messages and computing four epoch keys. Prove that if the DDH assumption holds in $\G$, then the first and last epoch keys are pseudorandom, even to an adversary who steals the exponent $a_3$. In other words, prove that the following two libraries are indistinguishable:

   $\subname{pcs}(\,)$:

   for $i=1$ to 5:

   $a_i \gets \Z_\nmod$

   $A_i := g^{a_i}$

   for $1=2$ to 5:

   $\key_i := g^{a_i \cdot a_{i-1}}$

   return $(A_1, \ldots, A_5, a_3, \key_2, \ldots, \key_5)$

   $\indist$

   $\subname{pcs}(\,)$:

   // exclude 3:

   for $i \in \{1,2,4,5\}$:

   $A_i \gets \G$

   $a_3 \gets \Z_\nmod$

   $A_3 := g^{a_3}$

   $\hl{\key_2 \gets \G}$

   $\key_3 := A_2^{a_3}$

   $\key_4 := A_4^{a_3}$

   $\hl{\key_5 \gets \G}$

   return $(A_1, \ldots, A_5, a_3, \key_2, \ldots, \key_5)$

3. A function $F : \bits^\secpar \times \bits^\secpar \to \bits^n$ is a secure dual PRF if it is a secure PRF and so is the function

   $F_{\text{swap}}(\key,X) = F(X,\key).$

   In other words, either of its two argument can be considered the key. The update function in an augmented symmetric ratchet (section 17.3) should be a secure dual PRF.

   Propose a dual PRF in the random oracle model and prove that it is secure.

4. The rule for updates in an MLS ratchet tree is that the new private key $\sk'_X$ is encrypted under the public keys of $X$'s children, unless that child is the leaf node representing the user who initiates this update. What security property (forward secrecy, post-compromise security) would be affected if this exception was removed? Assume that $\sk'_X$ would be encrypted under the updating user's old public key.

5. Consider the following simpler variant of the ratchet tree construction (section 17.4), which avoids updatable PKE. A user updates the tree by choosing new keypairs on its path to the root, just as before. But now the user has a different rule for generating the ciphertexts that distribute the private keys:

   Encrypt the new $\sk'_{[i:j]}$ under the old $\pk_{[i:j]}$.

   The idea behind this rule is the users who can decrypt under $\pk_{[i:j]}$ are exactly the users that need to know the new $\sk'_{[i:j]}$.

   Argue that this modification results in suboptimal post-compromise security. Since we have not introduced a formal definition of this security property, you should describe an attack informally (but clearly).

Chapter Notes

Forward secrecy was first introduced by Gunther [119].

The first formal study of post-compromise security is due to Cohn-Gordon, Cremers, and Garratt [71]. Asymmetric ratcheting first appeared in the Off-The-Record (OTR) messaging protocol of Borisov, Goldberg, and Brewer [51]. The first formal security analysis of asymmetric ratcheting was given by Bellare, Singh, Jaeger, Nyayapati, and Stepanovs [31]. They attribute the term ratchet to Langley.

Double ratcheting was first used in the TextSecure app [152]. The Signal double ratchet is due to Marlinspike and Perrin [180]. The first formal analysis of the Signal protocol's security is due to Cohn-Gordon, Cremers, Dowling, Garratt, and Stebila [68,69]. Further analyses were contributed by Alwen, Coretti, and Dodis [3], and by Bienstock, Fairoze, Garg, Mukherjee, and Raghuraman [41]. These security models are subtle and complex, capturing an adversary's ability to reorder messages, tamper with messages, inject messages, impersonate victims, and so on.

Ratchet trees were proposed by Cohn-Gordon, Cremers, Garratt, Millican, and Milner [70]. Bhargavan, Barnes, and Rescorla later adapted their construction to TreeKEM, which forms the key exchange mechanism of MLS [40].

El Gamal UPKE (construction 17.4.2) is due to Jost, Maurer, and Mularczyk [127]. Its use in the MLS group messaging protocol was first suggested within the MLS working group by Kohbrok [136], and then formally analyzed by Alwen, Coretti, Dodis, and Tselekounis [4]. The same set of authors provide further security analyses of the MLS protocol in [5].

1. Previous Chapter16. Digital Signatures
2. Next Chapter18. Authenticated Key Exchange