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 so-called ″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 under certain conditions, it disables an attacker from accessing the cleartext of messages ("the communication") after having compromised a session key.[3] This condition is that between the compromise of the key and the communication in question, there has been at least one message which was not tampered with by the attacker. This effectively forces the attacker to intercept all communication between the honest parties, since he loses access as soon as one uncompromised message is passed between them. This property was later named Future Secrecy, or Post-Compromise Security.[4]
Etymology
![A gif of a ratchet moving showing that the mechanism can only move in one direction](http://upload.wikimedia.org/wikipedia/commons/thumb/1/17/Ratchet_example.gif/125px-Ratchet_example.gif)
The term "ratchet" in cryptography is used similarly to a mechanical ratchet. In the mechanical sense, a ratchet only allows advancement in one direction; a cryptographic ratchet only allows keys to be generated from the previous key. However, unlike a mechanical ratchet, each state is unique.
Origin
The Double Ratchet Algorithm was developed by Trevor Perrin and Moxie Marlinspike (Open Whisper Systems) in 2013 and introduced as part of the Signal Protocol in February 2014. The Double Ratchet Algorithm's design is based on the DH ratchet that was introduced by Off-the-Record Messaging (OTR) and combines it with a symmetric-key ratchet modeled after the Silent Circle Instant Messaging Protocol (SCIMP). The ratchet was initially named after the critically endangered aquatic salamander axolotl, which has extraordinary self-healing capabilities. In March 2016, the developers renamed the Axolotl Ratchet as the Double Ratchet Algorithm to better differentiate between the ratchet and the full protocol,[2] because some had used the name Axolotl when referring to the Signal Protocol.[5][2]
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 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[by whom?] 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 (prekeys), 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 Algorithm, prekeys, and a 3-DH handshake.[6] 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.[7] It does not provide anonymity preservation, and requires servers for the relaying of messages and storing of public key material.[7]
Functioning
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.[8]
Applications
The following is a list of applications that use the Double Ratchet Algorithm or a custom implementation of it:
Notes
- ^ a b c d Via the OMEMO protocol
- ^ Only in "secret conversations"
- ^ a b c d e f g Via the Signal Protocol
- ^ A third-party plug-in must be installed separately
- ^ a b Via the Matrix protocol
- ^ Only in "incognito mode"
- ^ Via the Zina protocol
- ^ Only in "private conversations"
- ^ Viber "uses the same concepts of the "double ratchet" protocol used in Open Whisper Systems Signal application"
- ^ Via the Proteus protocol
References
- ^ Perrin, Trevor (30 March 2016). "Compare Revisions". GitHub. Retrieved 9 April 2016.
- ^ a b c 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.'
- ^ Cohn-Gordon, K.; Cremers, C.; Garratt, L. (2016). "On Post-compromise Security". 2016 IEEE 29th Computer Security Foundations Symposium (CSF): 164–178. doi:10.1109/CSF.2016.19. ISBN 978-1-5090-2607-4.
- ^ Cohn-Gordon et al. 2016, p. 1
- ^ Unger et al. 2015, p. 241
- ^ a b Unger et al. 2015, p. 239
- ^ Frosch et al. 2014
- ^ "Security". Cryptocat. Archived from the original on 7 April 2016. Retrieved 14 July 2016.
- ^ Greenberg, Andy (4 October 2016). "You Can All Finally Encrypt Facebook Messenger, So Do It". Wired. Condé Nast. Retrieved 5 October 2016.
- ^ Seals, Tara (17 September 2015). "G DATA Adds Encryption for Secure Mobile Chat". Infosecurity Magazine. Reed Exhibitions Ltd. Retrieved 16 January 2016.
- ^ "SecureChat". GitHub. G Data. Retrieved 14 July 2016.
- ^ Greenberg, Andy (18 May 2016). "With Allo and Duo, Google Finally Encrypts Conversations End-to-End". Wired. Condé Nast. Retrieved 14 July 2016.
- ^ "Haven Attributions". GitHub. Guardian Project. Retrieved 22 December 2017.
- ^ Lee, Micah (22 December 2017). "Snowden's New App Uses Your Smartphone To Physically Guard Your Laptop". The Intercept. First Look Media. Retrieved 22 December 2017.
- ^ Langley, Adam (9 November 2013). "Wire in new ratchet system". GitHub (GitHub contribution). Retrieved 16 January 2016.
- ^ Butcher, Mike (19 September 2016). "Riot wants to be like Slack, but with the flexibility of an underlying open source platform". TechCrunch. AOL Inc. Retrieved 20 September 2016.
- ^ "Silent Circle/libzina". Github. Silent Circle. Retrieved 19 December 2017.
- ^ Lund, Joshua (11 January 2018). "Signal partners with Microsoft to bring end-to-end encryption to Skype". Open Whisper Systems. Retrieved 11 January 2018.
- ^ "Viber Encryption Overview" (PDF). Viber. 25 July 2018. Retrieved 26 October 2018.
- ^ 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.
- ^ "Wire Security Whitepaper". Wire Swiss GmbH. Retrieved 15 July 2016.[permanent dead link]
Literature
- Cohn-Gordon, Katriel; Cremers, Cas; Dowling, Benjamin; Garratt, Luke; Stebila, Douglas (25 October 2016). "A Formal Security Analysis of the Signal Messaging Protocol" (PDF). Cryptology ePrint Archive. International Association for Cryptologic Research (IACR).
{{cite web}}
: CS1 maint: ref duplicates default (link) - Frosch, Tilman; Mainka, Christian; Bader, Christoph; Bergsma, Florian; Schwenk, Jörg; Holz, Thorsten (2014). "How Secure is TextSecure?" (PDF). Cryptology ePrint Archive. International Association for Cryptologic Research (IACR). Retrieved 16 January 2016.
{{cite web}}
: CS1 maint: ref duplicates default (link) - 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.
{{cite conference}}
: CS1 maint: ref duplicates default (link)
External links
- Specification by Open Whisper Systems
- "Advanced cryptographic ratcheting", abstract description by Moxie Marlinspike
- Olm: implementation in C++ under the Apache license