The Signal Protocol and the Double Ratchet algorithm
Introduction
Despite the fact that communication has become much easier these days, privacy and trust has been ignored for years by several industry powerhouses. During the last few years, revelations about mass surveillance have made consumers more privacy aware, thus the necessity of developing a security protocol that provides end to end encryption for instant messaging is now most imperative.
The Signal Protocol, described as an “end-to-end ratcheting forward secrecy protocol that works in synchronous and asynchronous messaging environments” [1] has recently been adopted by most of the messaging applications, including WhatsApp, Facebook Messenger etc.
The specific document focuses on the Ratchet Algorithm, which is one of the main concepts of the signal protocol.
End to End encryption
There are two main approaches for message encryption in chat applications: Peer-to-Peer (P2P) and End-to-End (E2E). The last which is used by the Signal Protocol, is the one that we will be focusing in the next sections.
End-to-end encryption is a method of secure communication that prevents third-parties from accessing data while it’s transferred from one end system or device to another.
In E2E encryption, the data is encrypted on the sender’s system or device and only the recipient is able to decrypt it, which is a fact that guaranties the confidentiality and integrity of the exchanged data.
Forward secrecy and Double Ratchet Algorithm
The Signal Protocol (formerly known as the TextSecure Protocol) is a non-federated cryptographic protocol that can be used to provide end-to-end encryption for voice calls, video calls and instant messaging conversations. Besides some standard security properties e.g. confidentiality, integrity and authenticity, signal includes some uncommon security properties such as forward secrecy and post compromise security:
Forward Secrecy: is a feature of specific key agreement protocols that gives assurances that session keys will not be compromised even if long-term secrets used in the session key exchange are compromised
The goal of the Double-Ratchet algorithm is to provide Forward Secrecy: compromise of long term keys or current session key must not compromise past communications.
Ratcheting
Why Ratchet ?
A ratchet is a mechanical device that allows continuous linear or rotary motion in only one direction while preventing motion in the opposite direction. We can imagine the ratchet as jagged wheel that can only move to one direction (e.g. clockwise) while moving backwards is mechanically prevented:
Transferring the construction described above to the Signal’s Protocol Cryptographic mechanism, we define a Key Derivation Function which takes a secret and random KDF key and a constant value and produces a “chain key” as well as a “message Key”[10]:
Every message sent or received is encrypted with a unique message key. This message key can only be used to decrypt one message, while the Chain key is immediately replaced with a new one. Similar to the ratchet wheel, suppose that an adversary compromises the Chain key at some time point t, then according to the cryptographic properties of the KDF, it is not possible to calculate the chain key for n < t.
A critical assumption at this point, is that the chosen KDF satisfies the requirements of a cryptographic Pseudo-Random Function. In simple words a pseudo random function is defined as bellow:
which means that given an s-Size Key K and and an n-Size random input X, there should be a sufficient algorithm (from the point of computing effort), that can compute
Where the F(X,K) (or else the output of the function) should not be distinguished when comparing to random data. Given that the KDF satisfies the specific assumption we can then define the following cryptographic properties for the signal protocol [10]:
- Resilience: The output keys appear random to an adversary without knowledge of the KDF keys. This is true even if the adversary can control the KDF inputs.
- Forward security: Output keys from the past appear random to an adversary who learns the KDF key at some point in time.
- Break-in recovery: Future output keys appear random to an adversary who learns the KDF key at some point in time, provided that future inputs have added sufficient entropy.
The KDF Ratchet
Using the metaphor described in the previous paragraph, we may now describe the Signal’s Ratchet mechanism, as follows:
By the time that two clients (Alice and Bob) establish a session between them, in order to communicate, they create two jagged wheels [11]:
We will call them Send-Ratchet-Wheel (or SRW from now on) and Receive-Ratchet-Wheel (or RRW from now on).
These wheels are synchronised in the same position during the initial setup which we define as time point 1 (or ​ from now on) and for reasons of simplicity we may equalise the value of the time point with the value of the wheel position:
- At T1, Alice sends a message to Bob encrypted by using the output key of
and moves the wheel one position forward. Alice may continue sending messages to Bob until he replies forwarding the wheel one position at a time.
- At T2, assuming that Alice sent ν+1 messages, in order for Bob to decrypt the so far messages he may produce ν+1 next keys, starting from the current position. Bob knows the value of ν since it is included at the messages metadata. He then may send (or not) a message to Alice following the same procedure that Alice did.
- In order for the mechanism to work, the following assumption should stand: At a given time point n+1 Alice’s SSW should be synchronised with Bob’s RRW and Bob’s SSW should be synchronised with Alice’s RRW.
Relying on KDF’s cryptographic properties, we may now assume the following:
Given a Time Point n and assuming that the sender’s or receiver’s chain key have been compromised by a malicious third party, not any known efficient algorithm can be used in order to compute the Chain Keys used at a time point p < n.
The assumption above can be mathematically proved using the KDF properties, assuming of course the case that the KDF satisfies the properties of a Secure PRF function. In simple words, what an attacker will succeed by compromising a chain key is for him to be possible to decrypt a message sent at a specific time point. The problem that arises now is the following:
Suppose that at a given time point n, the input of the SRW or RRW function is compromised for either the sender or receiver. This may allow an unauthorised third party to produce all the cryptographic keys needed in order to decrypt the messages sent at the time point n+k.
The specific problem can be solved by using the Diffie-Hellman Ratchet Mechanism described in the next paragraph.
The Diffie-Hellman Ratchet
Given the problem described in the previous paragraph, If an attacker steals one party’s sending and receiving chain keys, the attacker can compute all future message keys and decrypt all future messages. To prevent this, the Double Ratchet combines the symmetric-key ratchet with a DH ratchet which updates chain keys based on Diffie-Hellman outputs.
To implement the DH ratchet, each party generates a DH key pair (a Diffie-Hellman public key and private key) which becomes their current ratchet key pair. Every message from either party begins with a header which contains the sender’s current ratchet public key. When a new ratchet public key is received from the remote party, a DH ratchet step is performed which replaces the local party’s current ratchet key pair with a new key pair [10]. The specific procedure might have every n time points but in most cases happens in every message exchange, in order to achieve maximum future secrecy.
Using the Ratchet Mechanism Metaphor, the Double Ratchet Procedure is resumed in the following figure [11]:
Given a time point n, Bob sends a new Diffie-Hellman Ephemeral public key and reset’s his wheels to a new starting position. By the time that Alice receives the key, resets her send and recv wheels in order to synchronise with Bob. The inner KDF ratchet takes place and the procedure goes on, until the next DF-Ratchet.
We may now depict the DH-Ratchet procedure as follows:
Messages sent by Alice advertise her new public key. Eventually, Bob will receive one of these messages and perform a second DH ratchet step, and so on. The DH outputs generated during each DH ratchet step are used to derive new sending and receiving chain keys. The below diagram revisits Bob’s first ratchet step. Bob uses his first DH output to derive a receiving chain that matches Alice’s sending chain. Bob uses the second DH output to derive a new sending chain:
The above representation is a simplification of the actual procedure, since the DH output is used as an input to the KDF function discussed above, which also uses the ratcheting mechanism. The specific observation leads us to define the concept of Double Ratchet used by the Signal Protocol.
The Double Ratchet
Combining the symmetric-key and DH ratchets gives the Double Ratchet:
- When a message is sent or received, a symmetric-key ratchet step is applied to the sending or receiving chain to derive the message key.
- When a new ratchet public key is received, a DH ratchet step is performed prior to the symmetric-key ratchet to replace the chain keys.
Someone now may ask, since the Root keys of the KDF function get reset after each DH Ratchet, what is the reason to perform an additional KDF Ratchet. The KDF Ratchet usability evinces in the following cases:
Case 1: Suppose that the sender sends a message to the receiver who replies attaching the old DH public key. In this case the sender applies the KDF-Ratchet in order to create a new message key.
Case 2: Suppose that the sender sends a chain of messages without getting an answer from the receiver. In this case, the sender applies the KDF-Ratchet as many times as the number of the outgoing messages.
Out of order messages
The Double Ratchet handles lost or out-of-order messages by including in each message header the message’s number in the sending chain (N=0,1,2,…) and the length (number of message keys) in the previous sending chain (PN). This enables the recipient to advance to the relevant message key while storing skipped message keys in case the skipped messages arrive later.
On receiving a message, if a DH ratchet step is triggered then the received PN minus the length of the current receiving chain is the number of skipped messages in that receiving chain. The received N is the number of skipped messages in the new receiving chain (i.e. the chain after the DH ratchet).
If a DH ratchet step isn’t triggered, then the received N minus the length of the receiving chain is the number of skipped messages in that chain [10].
Header Encryption
In cases where it is desirable not for a third party to tell the ordering of the messages in a session or which messages belong to which session, the proposed measure according to the signal protocol is header encryption. Using header encryption premises the usage of two header key pairs for each party at a specific time point t. We call these header pair keys:
and
for sending and receiving operations respectively.
When one party wishes to send a message with encrypted header, uses the ​ key to encrypt and upon receiving the other party decrypts the message after finding the associated session (in case there are many sessions) with the corresponding private key. Successful decryption with the next header key indicates the recipient must perform a DH ratchet step. During a DH ratchet step the next header keys replace the current header keys, and new next header keys are taken as additional output from the root KDF. In a typical session, using header encryption the sender (Alice) performs the following tasks:
- Using Bob’s DH-Ratchet public key, generates the following keys: (Initial Root key, Sending Header key and Receiving Header Key)
- Creates a new DH-Ratchet key pair for her and updates the Root key, the Sending chain Key and the Receiving Header key
According to what is mentioned above, when Alice sends a message A1 to Bob, she encrypts the header with the Sending Header Key that she initialise on step 1. In case Bob replies to her message B1, Alice can decrypt this message using the Receiving Header Key. Then Alice will apply the DH Ratchet in order to create a new Sending and Receiving Key pair and so on.
Bibliography
[1] Cohn-Gordon K. et. al, November 2017, “A formal Security Analysis of the Signal Messaging Protocol”, University of Oxford, UK
[2] https://searchsecurity.techtarget.com/definition/end-to-end-encryption-E2EE
[4] December 2017, WhatsApp Encryption overview, Technical white paper
[5] https://en.wikipedia.org/wiki/Signal_Protocol
[6] Rubin Jan, January 2018, “Security Analysis of the Signal Protocol”, Faculty of information technology CTU, Prague
[7] https://en.wikipedia.org/wiki/Digital_Signature_Algorithm
[8] https://en.wikipedia.org/wiki/Montgomery_curve
[9] https://en.wikipedia.org/wiki/Edwards_curve
[10] https://signal.org/
[11] https://www.youtube.com/watch?v=9sO2qdTci-s
[12] https://www.rdocumentation.org/packages/sodium/versions/1.0/topics/Diffie-Hellman
[13] Guan L. et. al, 2015, “Protecting Private Keys against Memory Disclosure Attacks using Hardware Transactional Memory”, IEEE Symposium on Security and Privacy.
[14] B.P.F. Jacobs et. al, April 2015, “The (in)security of proprietary cryptography”, Radboud Universiteit Nijmegen
