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.

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.

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:

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:

  • 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:

  • 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.

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.

The Double Ratchet

Combining the symmetric-key and DH ratchets gives the Double Ratchet:

  • 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.

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.

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:

  • Creates a new DH-Ratchet key pair for her and updates the Root key, the Sending chain Key and the Receiving Header key

Bibliography

[1] Cohn-Gordon K. et. al, November 2017, “A formal Security Analysis of the Signal Messaging Protocol”, University of Oxford, UK

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store