The Double Ratchet Algorithm

From CryptoWiki
Jump to: navigation, search

The Double Ratchet algorithm is a session key management algorithm to provide end-to-end encryption for instant messaging, that was developed in 2013 by Trevor Perrin and Moxie Marlinspike.

Contents

Introduction

The exchange of confidential messages (in case of symmetric cryptosystems) requires that two parties of communication have some shared secret key. Usually the parties use some key agreement protocol (such as Extended Triple Diffie-Hellman) in order to agree on the shared secret key. The participants of the secret communication can use the generated key for further confidential messaging, but in this case the compromise of this key will allow the attacker to gain access to all messages sent before and after the compromise.

The Double Ratchet algorithm was designed to provide perfect forward secrecy and post-compromise security. These properties are ensured by the fact that the parties of communication generate new keys for each message using a cryptographic one-way function which prevents an attacker from calculating earlier keys using later ones. Besides, the parties re-negotiate keys after each sent or received message (using a new pair of keys unknown to the attacker) which makes it impossible to calculate later keys from earlier ones.

Thus, the Double Ratchet algorithm combines the ideas and properties of a symmetric-key ratchet and Diffie-Hellman ratchet.

Back to Table of Contents

The history of development

The Double Ratchet algorithm was designed in 2013 by Trevor Perrin and Moxie Marlinspike, the creator of the non-profit organization of open software developers called Open Whisper Systems. The goal of this organization is to develop an easy-to-use set of mobile applications for secure communication. In February 2014, Trevor Perrin and Moxie Marlinspike introduced the algorithm as part of the Signal Protocol. The purpose of the Double Ratchet algorithm is to combine the Diffie-Hellman ratchet, first introduced in the Off-The-Record Messaging (OTR), and the symmetric-key ratchet presented in the Silent Circle Instant Messaging Protocol (SCIMP). The algorithm was originally named after the endangered animal of the axolotl, which has exceptional self-healing abilities. In March 2016, the developers renamed Axolotl Ratchet to Double Ratchet Algorithm.

Mechanism description

KDF chains

The key concept of the Double Ratchet algorithm is a KDF chain. A key derivation function is a cryptographic function that converts a secret and random KDF key and some input data into output data that is indistinguishable from random (provided that the key isn't known). In other words, a KDF is a pseudo-random function (PRF). If the key is not secret and random, the KDF must still be a secure cryptographic hash function. The use of HMAC and HKDF constructions in conjunction with a secure cryptographic hash function provides all the necessary requirements for a KDF.

A KDF chain is the composition of functions, in which a part of the one function’s output is used as the key of another KDF. The picture below clearly demonstrates the functioning of the described chain.


Picture 1 – A KDF chain

A KDF chain has the following properties:

  • resilience - output keys are indistinguishable from random ones even in case of the adversary’s control over the output, provided that the KDF key is unknown to him;
  • forward security - output keys that were formed before the compromise are indistinguishable from random ones for an adversary who compromised the KDF key at some point in time;
  • break-in recovery - output keys formed after compromise are indistinguishable from random ones for an adversary who has compromised the KDF key at some point in time, provided that future input data have sufficient entropy.

In the Alice and Bob’s Double Ratchet session each side stores keys for three chains: a root chain, a sending chain, and a receiving chain. At the same time, Alice's sending chain corresponds to Bob's receiving chain, and vice versa.

When Alice and Bob exchange messages, they also exchange new Diffie-Hellman public keys, and the Diffie-Hellman output secrets are used as the root chain inputs. The output keys from the root chain become new keys for the chain of sending and receiving messages. The described algorithm is called the Diffie-Hellman ratchet. The sending and receiving chains are advanced when each message is sent and received. The output keys of these chains are directly used to encrypt and decrypt messages. Such algorithm is called the symmetric-key ratchet.

Symmetric-key ratchet

The basic idea of the symmetric-key ratchet is that every received or sent message is encrypted with a unique message key. The message keys are obtained using receiving and sending KDF chains. The KDF keys for these chains are called chain keys. The KDF inputs are constants which is the reason for the violation of security after the key has been compromised. The only task of the sending and receiving chains is to ensure the uniqueness of the encryption key for each message, which allows you to delete this key after encryption or decryption. The ratchet step in the considered mechanism is the calculation of the next chain key and message key from a given chain key. The picture below shows the two steps of the symmetric-key ratchet.


Picture 2 - The symmetric-key ratchet

Since message keys are not used to obtain the following keys, they can be stored without affecting the security of other message keys. This is useful for handling lost or out-of-order messages.

Diffie-Hellman ratchet

If an attacker gets access to the sending and receiving chain keys from one of the parties at some point in time, he will be able to calculate all future message keys, and, consequently, will get access to further messages. To prevent this the Double Ratchet algorithm combines the symmetric-key ratchet with a Diffie-Hellman ratchet which provides security after the compromise of the key.

To implement the Diffie-Hellman ratchet, each of the parties generates a Diffie-Hellman key pair which becomes their current ratchet key pair. Each message begins with a header containing the sender's current ratchet public key.

When a message is received, the sender’s public key is used to implement the Diffie-Hellman ratchet step, which generates a common key material and generates a new ratchet key pair. Thus, the communication parties continuously exchange public keys and update their key pairs.

An attacker who managed to acquire one party’s secret key at some point in time will not be able to take advantage of this in future, because when performing the next ratchet step, the secret key will be replaced with uncompromised one, and the attacker will not be able to calculate further Diffie-Hellman key material.

The pictures below show the process of obtaining a common key material using the Diffie-Hellman ratchet. Before the protocol starts, Alice receives Bob’s ratchet public key (Alice’s ratchet public key is not yet known to Bob). As part of initialization Alice calculates the Diffie-Hellman output based on Bob’s public key and her current secret key.


Picture 3 - Diffie-Hellman ratchet initialization

Alice's first message includes her ratchet public key. As soon as Bob receives the message, he performs the ratchet step:

  • Bob calculates the Diffie-Hellman output, which is equal to the value obtained by Alice, based on Alice’s public key and his ratchet private key;
  • Bob randomly generates a new key pair and calculates a new Diffie-Hellman output.

Diffie-Hellman ratchet step is shown in the picture below.

Picture 4 - Diffie-Hellman ratchet step

The message sent by Bob contains his new public key. After receiving a message from Bob, Alice performs a Diffie-Hellman ratchet step, thereby obtaining the Diffie-Hellman output, previously developed by Bob, generating a new key pair and generating a new Diffie-Hellman key agreement protocol value based on Bob’s public key and the new ratchet secret key. After receiving a message from Alice containing her new public key, Bob will perform the second Diffie-Hellman step and so on.

The Diffie-Hellman outputs generated during each Diffie-Hellman ratchet step are used to derive new sending and receiving chain keys. The picture below complements the Bob's first ratchet step. Bob uses the first Diffie-Hellman output to to derive a receiving chain, which corresponds to the Alice's sending chain. The second Diffie-Hellman output is used by Bob to form a new sending chain.

Рисунок 5 - KDF chains key generation

Further, Alice receives the receiving chain key, equal to the sending chain key generated by Bob, and forms a new sending chain.

However, the algorithm described above is a simplification. In reality, the Diffie-Hellman output is used as the input of the root chain, and the output of the root chain is used as the sending and receiving chain keys. The use of a KDF chain allows to increase stability and durability after the compromise of the key.

Thus, the full Diffie-Hellman ratchet step consists of double updating the KDF root chain and updating the sending and receiving chain keys based on the output of the root chain. This process is illustrated in the picture below.

Picture 6 - Full Diffie-Hellman ratchet step

Double Ratchet algorithm

Combining the ratchet with a symmetric-key and the Diffie-Hellman ratchet leads to the definition of the Double Ratchet algorithm:

  • when a message is received or sent, a symmetric-key ratchet step is applied to the sending or receiving chain to derive the message key;
  • when a new public key is received the Diffie-Hellman ratchet step is performed prior in order to update the sending and receiving chain keys.

At the initial moment of the protocol, Alice has Bob’s ratchet public key and a shared secret with Bob, which is the key of the root chain. As part of the initialization, Alice generates a new ratchet key pair and uses the Diffie-Hellman output to form a new root key (RK) and sending chain key (CK). The initialization is clearly illustrated in the picture below.

Picture 7 - The Double Ratchet algorithm initialization

When Alice sends her first message A1, she applies a symmetric key ratchet step to her sending chain key, thereby receiving a new message key. The new sending chain key must be stored, while the message key (after encryption) and the old chain key can be deleted. The steps described above are shown in the picture below.

Picture 8 - Sending the first message from Alice to Bob

Suppose that the response received from Bob B1 contains the new ratchet public key. Then Alice performs the Diffie-Hellman ratchet step in order to obtain new sending and receiving chain keys. Then she applies a symmetric key ratchet step chain to the receiving chain to get the decryption key for the received message. The described sequence is shown in the picture below.

Picture 9 - Getting the first message from Bob by Alice

Suppose Alice then sends a message A2, receives a message B2 from Bob with the old ratchet public key, and sends messages A3 and A4. Alice’s sending and receiving chains after these steps will look like the one shown in the picture below.

Changes in the chains after messages A2, B2, A3, A4

If we further suppose that Alice received messages B3 and B4 with the Bob's new ratchet public key and sends a message A5, then the final state of the Alice's KDF chains will correspond to the picture below.

Picture 11 - The final state of the Alice's KDF chains

Out-of-order messages Processing

The Double Ratchet algorithm processes lost and out-of-order messages by adding message's number in the sending chain and the length (number of message keys) in the previous sending chain to the current message’s header. This allows the recipient to advance to the relevant message key while storing the missed keys in case the missed messages arrive later.

Security Considerations

Secure deletion

The Double Ratchet algorithm was designed to protect against an attacker who is recording encrypted messages in order to compromise the recipient or sender later. Resilience of the mechanism can be compromised if deleted keys or plaintext (открытый текст) will be restored by an attacker with low-level access to the compromised device. Recovering deleted data from storage media is a complex topic that goes beyond the description of this mechanism.

Recovery from compromise

The Diffie-Hellman ratchet algorithm is designed to provide protection against a passive adversary who reads encrypted messages after one (or both) sides of a communication session has been compromised. However, compromising the keys or the integrity of the device can have dangerous consequences for the security of future communications sessions. For example:

  • the attacker could use compromised keys to replace the compromised side (for example, using the private key with Extended Triple Diffie-Hellman to create new communication sessions);
  • the attacker can replace the ratchet keys by conducting a man-in-the-middle attack in order to intercept further messages;
  • the attacker can influence (change / replace) the random number and sequences generator of the compromised side in order to achieve the predictability of future private keys.

In this regard, any suspicion of compromise should result in the replacement of the used keys.

Cryptanalysis and ratchet public keys

Since all Diffie-Hellman ratchet algorithm calculations use the root chain key, an attacker who can decrypt the session using passive cryptanalysis can lose this ability by skipping one of the ratchet public keys. Of course, this cannot be considered a reliable countermeasure against cryptanalysis. In this regard, when detecting any vulnerabilities in the used cryptographic primitives, the communication session should be interrupted and a new session should be established using secure cryptographic primitives.

Deletion of skipped message keys

Storing skipped keys entails certain risks:

  • a malicious sender may encourage recipients to store a large number of skipped keys, which may result in a denial-of-service due to lack of storage space;
  • lost messages can be viewed (and recorded) by the attacker, even if they have not reached the recipient. In the future, an attacker may compromise the intended recipient in order to obtain the missing keys and to read the corresponding messages.

In order to reduce the risk of the first scenario parties should establish reasonable limits on the number of skipped message keys that will be saved (for example, 1000). To reduce the risk of the second scenario it is recommended to delete the skipped message keys at a certain time interval or number of events (received messages, Diffie-Hellman ratchet steps, etc.).

New ratchet key generation

At each Diffie-Hellman ratchet step a new ratchet key pair and sending chain key are generated. Since the sending chain is not required immediately, this step can be postponed until the need arises. This can increase security by reducing the lifespan of the ratchet keys, due to the slight complexity of the implementation.

Truncating authentication tags

If the AEAD scheme is implemented using CBC and HMAC, then truncating the final HMAC output to 128 bits to reduce message size is acceptable. Truncating it further might be acceptable, though requires careful analysis. In no case should the final HMAC be truncated to less than 64 bits.

If the AEAD scheme is implemented differently, then truncation might require a more complicated analysis and is not recommended.

Implementation in case of parties’ anonymity

If the Double Ratchet algorithm is used in the conditions of parties’ anonymity, it is very important to ensure that the implementations of the mechanisms of each party are identical in all cases.

In order to ensure this, it is necessary to accurately follow the recommendations on the implementation, to use identical limitations on the number of skipped messages keys, and to apply identical policies for deleting skipped messages keys. In this case, deletion policy should be based on deterministic events (for example, received messages), rather than time.

Glossary

References

Go to list of references to the section "The Double Ratchet Algorithm"

Filippov A.I. 2019