Double Ratchet Algorithm
In cryptography, the Double Ratchet Algorithm (previously referred to as the Axolotl Ratchet[1][2]) is a key management algorithm that was developed by Trevor Perrin and Moxie Marlinspike in 2013. It can be used as part of a cryptographic protocol to provide end-to-end encryption for instant messaging. After an initial key exchange it manages the ongoing renewal and maintenance of short-lived session keys. It combines a cryptographic ratchet based on the Diffie–Hellman key exchange (DH) and a ratchet based on a key derivation function (KDF) like e.g. a hash function and is therefore called a double ratchet.
The developers refer to the algorithm as self-healing because it automatically disables an attacker from accessing the cleartext of later messages after having compromised a session key.[3]
Origin
The Double Ratchet Algorithm was developed by Trevor Perrin and Moxie Marlinspike (Open Whisper Systems) and introduced in TextSecure (now Signal) in 2013. The design is based on the DH ratchet that was introduced by Off-the-Record Messaging and combines it with a symmetric-key ratchet modeled after the Silent Circle Instant Messaging Protocol (SCIMP). Up until March 2016, the Double Ratchet Algorithm was referred to as the Axolotl Ratchet[1][2] for being the ratcheting algorithm used in a protocol called Axolotl (now known as the Signal Protocol).[2] It was named after the critically endangered aquatic salamander Axolotl, which has extraordinary self-healing capabilities.
Properties
The Double Ratchet Algorithm features properties that have been commonly available in end-to-end encryption systems for a long time: encryption of contents on the entire way of transport as well as authentication of the remote peer and protection against manipulation of messages. As a hybrid of DH and KDF ratchets, it combines several desired features of both principles. From OTR messaging it takes the properties of forward secrecy and automatically reestablishing secrecy in case of compromise of a session key, forward secrecy with a compromise of the secret persistent main key, and plausible deniability for the authorship of messages. Additionally, it enables for session key renewal without interaction with the remote peer by using secondary KDF ratchets. An additional key-derivation step is taken to enable retaining session keys for out-of-order messages without endangering the following keys.
It is said to detect reordering, deletion and replay of sent messages and improve forward secrecy properties in comparison to OTR messaging.
Combined with public key infrastructure for the retention of pregenerated one-time keys, it allows for the initialization of messaging sessions without the presence of the remote peer (asynchronous communication). The usage of triple Diffie–Hellman key exchange (3-DH) as initial key exchange method improves the deniability properties. An example of this is the Signal Protocol, which combines the double ratchet, prekeys, and a 3-DH handshake.[4] The protocol provides confidentiality, integrity, authentication, participant consistency, destination validation, forward secrecy, backward secrecy (aka future secrecy), causality preservation, message unlinkability, message repudiation, participation repudiation, and asynchronicity.[5] It does not provide anonymity preservation, and requires servers for the relaying of messages and storing of public key material.[5]
Functioning
![](../I/m/Axolotl_ratchet_scheme%2C_legend.svg.png)
![](../I/m/Axolotl_ratchet_scheme.svg.png)
A client renews session key material in interaction with the remote peer using Diffie–Hellman ratchet whenever possible, otherwise independently by using a hash ratchet. Therefore, with every message a client using the double ratchet advances one of two hash ratchets (one for sending, one receiving) which get seeded with a common secret from a DH ratchet. At the same time it tries to use every opportunity to provide the remote peer with a new public DH value and advance the DH ratchet whenever a new DH value from the remote peer arrives. As soon as a new common secret is established, a new hash ratchet gets initialized.
As cryptographic primitives, the Double Ratchet Algorithm uses
- for the DH ratchet
- Elliptic curve Diffie–Hellman (ECDH) with Curve25519,
- for message authentication codes (MAC, authentication)
- Keyed-Hash Message Authentication Code (HMAC) based on SHA-256,
- for symmetric encryption
- the Advanced Encryption Standard (AES), partially in Cipher Block Chaining mode (CBC) with padding as per PKCS #5 and partially in Counter mode (CTR) without padding,
- for the hash ratchet
- HMAC.[6]
Usage
The Double Ratchet Algorithm is being used by hundreds of thousands of Signal users. The Signal Protocol combines the Double Ratchet Algorithm, prekeys, and a 3-DH handshake.[4]
In September 2014, an announcement to integrate the Signal Protocol into WhatsApp spawned some headlines in newspapers. As of April 5, 2016, the protocol is used across all of WhatsApp's platforms.[7]
In November 2013, the Double Ratchet Algorithm was integrated into an experimental asynchronous messaging system called Pond.[8] In the summer of 2015, an XMPP extension named OMEMO was developed as a Google Summer of Code project. OMEMO integrates the Double Ratchet Algorithm. It was introduced in an instant messaging app called Conversations and submitted to the XMPP Standards Foundation (XSF) in the autumn of 2015.[9][10]
In September 2015, G Data launched a new messaging app called Secure Chat which uses the Double Ratchet Algorithm.[11] On September 28, 2015, Silent Circle replaced their own SCIMP protocol with a protocol that uses the Double Ratchet Algorithm when they merged their Silent Text app into their Silent Phone app.[12][13]
In the last quarter of 2013, the Signal Protocol was integrated into the Android-based open-source operating system CyanogenMod, which counted over 10 million users at that time.[14][15][16] In February 2016, however, the CyanogenMod team discontinued their WhisperPush feature that used the Signal Protocol and recommended that its users switch to Signal.[17]
In March 2016, a company called Wire Swiss said that they used the Double Ratchet Algorithm.[18]
Literature
- Unger, Nik; Dechand, Sergej; Bonneau, Joseph; Fahl, Sascha; Perl, Henning; Goldberg, Ian Avrum; Smith, Matthew (2015). SoK: Secure Messaging (PDF). Proceedings of the 2015 IEEE Symposium on Security and Privacy. IEEE Computer Society's Technical Committee on Security and Privacy. pp. 232–249. doi:10.1109/SP.2015.22.
References
- 1 2 Perrin, Trevor (30 March 2016). "Compare Revisions". GitHub. Retrieved 9 April 2016.
- 1 2 3 Marlinspike, Moxie (30 March 2016). "Signal on the outside, Signal on the inside". Open Whisper Systems. Retrieved 31 March 2016.
- ↑ Marlinspike, Moxie (26 November 2013). "Advanced cryptographic ratcheting". whispersystems.org. Open Whisper Systems. Retrieved 16 January 2016.
The OTR style ratchet has the nice property of being 'self healing.'
- 1 2 Unger et al. 2015, p. 241
- 1 2 Unger et al. 2015, p. 239
- ↑ Frosch, Tilman; Mainka, Christian; Bader, Christoph; Bergsma, Florian; Schwenk, Jörg; Holz, Thorsten. "How Secure is TextSecure?" (PDF). Horst Görtz Institute for IT Security, Ruhr University Bochum. Retrieved 16 January 2016.
- ↑ Metz, Cade (5 April 2016). "Forget Apple vs. the FBI: WhatsApp Just Switched on Encryption for a Billion People". Wired. Condé Nast. Retrieved 5 April 2016.
- ↑ Langley, Adam (9 November 2013). "Wire in new ratchet system". GitHub (GitHub contribution). Retrieved 16 January 2016.
- ↑ Straub, Andreas (25 October 2015). "OMEMO Encryption". XMPP Standards Foundation website. Retrieved 16 January 2016.
- ↑ Gultsch, Daniel (2 September 2015). "OMEMO Encrypted Jingle File Transfer". XMPP Standards Foundation website. Retrieved 16 January 2016.
- ↑ Seals, Tara (17 September 2015). "G DATA Adds Encryption for Secure Mobile Chat". Infosecurity Magazine. Reed Exhibitions Ltd. Retrieved 16 January 2016.
- ↑ "What is Silent Phone?". Support.silentcircle.com. Silent Circle. 17 September 2015. Archived from the original on 4 March 2016. Retrieved 8 March 2016.
- ↑ Armasu, Lucian (3 November 2015). "TextSecure, RedPhone Private Communications Apps Now Combined Into 'Signal' App". Tom's Hardware. Purch Group, Inc. Retrieved 8 March 2016.
- ↑ Greenberg, Andy (9 December 2013). "Ten Million More Android Users' Text Messages Will Soon Be Encrypted By Default". Forbes. Retrieved 16 January 2016.
- ↑ Seth Schoen (28 December 2013). "2013 in Review: Encrypting the Web Takes A Huge Leap Forward". Electronic Frontier Foundation. Retrieved 16 January 2016.
- ↑ Marlinspike, Moxie (9 December 2013). "TextSecure, Now With 10 Million More Users". Open Whisper Systems. Retrieved 16 January 2016.
- ↑ Sinha, Robin (20 January 2016). "CyanogenMod to Shutter WhisperPush Messaging Service on February 1". Gadgets360. NDTV. Retrieved 10 March 2016.
- ↑ Kahn, Jeremy (10 March 2016). "Amid Apple's FBI fight, app developers are ramping up encryption". Chicago Tribune. Tribune Publishing. Retrieved 11 March 2016.
External links
- Specification
- "Advanced cryptographic ratcheting", abstract description by Moxie Marlinspike
|
|