Double Ratchet Algorithm

Last updated
Full ratchet step in the double ratchet algorithm. The Key Derivation Function (KDF) provides the ratcheting mechanism. The first "ratchet" is applied to the symmetric root key, the second ratchet to the asymmetric Diffie Hellman (DH) key. Double Ratchet Algorithm.png
Full ratchet step in the double ratchet algorithm. The Key Derivation Function (KDF) provides the ratcheting mechanism. The first "ratchet" is applied to the symmetric root key, the second ratchet to the asymmetric Diffie Hellman (DH) key.

In cryptography, the Double Ratchet Algorithm (previously referred to as the Axolotl Ratchet [2] [3] ) 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), such as a hash function, and is therefore called a double ratchet.

Contents

The algorithm provides forward secrecy for messages, and implicit renegotiation of forward keys; properties for which the protocol is named. [4]

History

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. [5] In March 2016, the developers renamed the Axolotl Ratchet as the Double Ratchet Algorithm to better differentiate between the ratchet and the full protocol, [3] because some had used the name Axolotl when referring to the Signal Protocol. [6] [3]

Overview

A mechanical ratchet Ratchet example.gif
A mechanical ratchet

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 against passive eavesdropping 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. [7] 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. [8] It does not provide anonymity preservation, and requires servers for the relaying of messages and storing of public key material. [8]

Functioning

Axolotl ratchet scheme, legend.svg
Axolotl ratchet scheme.svg
Diagram of the working principle

A client attempts to renew session key material interactively with the remote peer using a Diffie-Hellman (DH) ratchet. If this is impossible, the clients renew the session key independently using a hash ratchet. With every message, a client advances one of two hash ratchets—one for sending and one for receiving. These two hash ratchets 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. [9]

Applications

The following is a list of applications that use the Double Ratchet Algorithm or a custom implementation of it:

Notes

  1. 1 2 3 4 Via the OMEMO protocol
  2. ↑ Only in "secret conversations"
  3. 1 2 3 4 5 6 7 8 Via the Signal Protocol
  4. 1 2 Via the Matrix protocol
  5. ↑ Only in "incognito mode"
  6. ↑ Only in one-to-one RCS chats
  7. ↑ Via the Zina protocol
  8. ↑ Only in "private conversations"
  9. ↑ Viber "uses the same concepts of the "double ratchet" protocol used in Open Whisper Systems Signal application"
  10. ↑ Via the Proteus protocol

Related Research Articles

<span class="mw-page-title-main">Diffie–Hellman key exchange</span> Method of exchanging cryptographic keys

Diffie–Hellman (DH) key exchange is a mathematical method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as conceived by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography. Published in 1976 by Diffie and Hellman, this is the earliest publicly known work that proposed the idea of a private key and a corresponding public key.

<span class="mw-page-title-main">Public-key cryptography</span> Cryptographic system with public and private keys

Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security.

A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key can be different sizes and varieties, but in all cases, the strength of the encryption relies on the security of the key being maintained. A key's security strength is dependent on its algorithm, the size of the key, the generation of the key, and the process of key exchange.

Transport Layer Security (TLS) is a cryptographic protocol designed to provide communications security over a computer network. The protocol is widely used in applications such as email, instant messaging, and voice over IP, but its use in securing HTTPS remains the most publicly visible.

Articles related to cryptography include:

<span class="mw-page-title-main">Key exchange</span> Cryptographic method

Key exchange is a method in cryptography by which cryptographic keys are exchanged between two parties, allowing use of a cryptographic algorithm.

Off-the-record Messaging (OTR) is a cryptographic protocol that provides encryption for instant messaging conversations. OTR uses a combination of AES symmetric-key algorithm with 128 bits key length, the Diffie–Hellman key exchange with 1536 bits group size, and the SHA-1 hash function. In addition to authentication and encryption, OTR provides forward secrecy and malleable encryption.

<span class="mw-page-title-main">Forward secrecy</span> Practice in cryptography

In cryptography, forward secrecy (FS), also known as perfect forward secrecy (PFS), 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, limiting damage. For HTTPS, the long-term secret is typically the private key of the server. Forward secrecy protects past sessions against future compromises of keys or passwords. By generating a unique session key for every session a user initiates, the compromise of a single session key will not affect any data other than that exchanged in the specific session protected by that particular key. This by itself is not sufficient for forward secrecy which additionally requires that a long-term secret compromise does not affect the security of past session keys.

Multimedia Internet KEYing (MIKEY) is a key management protocol that is intended for use with real-time applications. It can specifically be used to set up encryption keys for multimedia sessions that are secured using SRTP, the security protocol commonly used for securing real-time communications such as VoIP.

ZRTP is a cryptographic key-agreement protocol to negotiate the keys for encryption between two end points in a Voice over IP (VoIP) phone telephony call based on the Real-time Transport Protocol. It uses Diffie–Hellman key exchange and the Secure Real-time Transport Protocol (SRTP) for encryption. ZRTP was developed by Phil Zimmermann, with help from Bryce Wilcox-O'Hearn, Colin Plumb, Jon Callas and Alan Johnston and was submitted to the Internet Engineering Task Force (IETF) by Zimmermann, Callas and Johnston on March 5, 2006 and published on April 11, 2011 as RFC 6189.

This is a comparison of voice over IP (VoIP) software used to conduct telephone-like voice conversations across Internet Protocol (IP) based networks. For residential markets, voice over IP phone service is often cheaper than traditional public switched telephone network (PSTN) service and can remove geographic restrictions to telephone numbers, e.g., have a PSTN phone number in a New York area code ring in Tokyo.

In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security and designed for use with the Elliptic-curve Diffie–Hellman (ECDH) key agreement scheme. It is one of the fastest curves in ECC, and is not covered by any known patents. The reference implementation is public domain software.

<span class="mw-page-title-main">Moxie Marlinspike</span> American entrepreneur

Matthew Rosenfeld, better known by the pseudonym Moxie Marlinspike, is an American entrepreneur, cryptographer, and computer security researcher. Marlinspike is the creator of Signal, co-founder of the Signal Technology Foundation, and served as the first CEO of Signal Messenger LLC. He is also a co-author of the Signal Protocol encryption used by Signal, WhatsApp, Google Messages, Facebook Messenger, and Skype.

Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe, or quantum-resistant, is the development of cryptographic algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. Most widely-used public-key algorithms rely on the difficulty of one of three mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm or even faster and less demanding alternatives.

<span class="mw-page-title-main">Cryptocat</span> Open source encrypted chat application

Cryptocat is a discontinued open-source desktop application intended to allow encrypted online chatting available for Windows, OS X, and Linux. It uses end-to-end encryption to secure all communications to other Cryptocat users. Users are given the option of independently verifying their buddies' device lists and are notified when a buddy's device list is modified and all updates are verified through the built-in update downloader.

TextSecure was an encrypted messaging application for Android that was developed from 2010 to 2015. It was a predecessor to Signal and the first application to use the Signal Protocol, which has since been implemented into WhatsApp and other applications. TextSecure used end-to-end encryption to secure the transmission of text messages, group messages, attachments and media messages to other TextSecure users.

<span class="mw-page-title-main">Open Whisper Systems</span> Open source software organization

Open Whisper Systems was a software development group that was founded by Moxie Marlinspike in 2013. The group picked up the open source development of TextSecure and RedPhone, and was later responsible for starting the development of the Signal Protocol and the Signal messaging app. In 2018, Signal Messenger was incorporated as an LLC by Moxie Marlinspike and Brian Acton and then rolled under the independent 501c3 non-profit Signal Technology Foundation. Today, the Signal app is developed by Signal Messenger LLC, which is funded by the Signal Technology Foundation.

<span class="mw-page-title-main">Signal (messaging app)</span> Privacy-focused encrypted messaging app

Signal is an encrypted messaging service for instant messaging, voice calls, and video calls. The instant messaging function includes sending text, voice notes, images, videos, and other files. Communication may be one-to-one between users or may involve group messaging.

<span class="mw-page-title-main">Signal Protocol</span> Non-federated cryptographic protocol

The Signal Protocol is a non-federated cryptographic protocol that provides end-to-end encryption for voice and instant messaging conversations. The protocol was developed by Open Whisper Systems in 2013 and was introduced in the open-source TextSecure app, which later became Signal. Several closed-source applications have implemented the protocol, such as WhatsApp, which is said to encrypt the conversations of "more than a billion people worldwide" or Google who provides end-to-end encryption by default to all RCS-based conversations between users of their Google Messages app for one-to-one conversations. Facebook Messenger also say they offer the protocol for optional Secret Conversations, as does Skype for its Private Conversations.

Application Layer Transport Security (ALTS) is a Google-developed authentication and transport encryption system used for securing Remote Procedure Call (RPC) within Google machines. Google started its development in 2023, as a tailored modification of TLS.

References

  1. ↑ Trevor Perrin (editor), Moxie Marlinspike, "The Double Ratchet Algorithm. Revision 1, 2016-11-20
  2. ↑ Perrin, Trevor (30 March 2016). "Compare Revisions". GitHub. Retrieved 9 April 2016.
  3. 1 2 3 Marlinspike, Moxie (30 March 2016). "Signal on the outside, Signal on the inside". Open Whisper Systems. Retrieved 31 March 2016.
  4. ↑ Cohn-Gordon, K.; Cremers, C.; Garratt, L. (2016). "On Post-compromise Security". 2016 IEEE 29th Computer Security Foundations Symposium (CSF). pp. 164–178. doi:10.1109/CSF.2016.19. ISBN   978-1-5090-2607-4. S2CID   5703986.
  5. ↑ Ksenia Ermoshina, Francesca Musiani. "Standardising by running code": the Signal protocol and de facto standardisation in end-to-end encrypted messaging. Internet histories, 2019, pp.1-21. �10.1080/24701475.2019.1654697�. �halshs-02319701�
  6. ↑ Cohn-Gordon et al. 2016 , p. 1
  7. ↑ Unger et al. 2015 , p. 241
  8. 1 2 Unger et al. 2015 , p. 239
  9. ↑ Frosch et al. 2014
  10. ↑ "Security". Cryptocat. Archived from the original on 7 April 2016. Retrieved 14 July 2016.
  11. ↑ Greenberg, Andy (4 October 2016). "You Can All Finally Encrypt Facebook Messenger, So Do It". Wired. Condé Nast. Retrieved 5 October 2016.
  12. ↑ Seals, Tara (17 September 2015). "G DATA Adds Encryption for Secure Mobile Chat". Infosecurity Magazine. Reed Exhibitions Ltd. Retrieved 16 January 2016.
  13. ↑ "SecureChat". GitHub. G Data. Retrieved 14 July 2016.
  14. ↑ Greenberg, Andy (18 May 2016). "With Allo and Duo, Google Finally Encrypts Conversations End-to-End". Wired. Condé Nast. Retrieved 14 July 2016.
  15. ↑ Amadeo, Ron (2021-06-16). "Google enables end-to-end encryption for Android's default SMS/RCS app". Ars Technica. Retrieved 2022-03-03.
  16. ↑ "Haven Attributions". GitHub. Guardian Project. Retrieved 22 December 2017.
  17. ↑ 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.
  18. ↑ Langley, Adam (9 November 2013). "Wire in new ratchet system". GitHub (GitHub contribution). Retrieved 16 January 2016.
  19. ↑ 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.
  20. ↑ "Silent Circle/libzina". Github. Silent Circle. Retrieved 19 December 2017.
  21. ↑ Lund, Joshua (11 January 2018). "Signal partners with Microsoft to bring end-to-end encryption to Skype". Open Whisper Systems. Retrieved 11 January 2018.
  22. ↑ "Viber Encryption Overview" (PDF). Viber. 25 July 2018. Retrieved 26 October 2018.
  23. ↑ 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.
  24. ↑ "Wire Security Whitepaper" (PDF). Wire Swiss GmbH. 17 August 2018. Retrieved 28 August 2020.

Literature

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.