Double Ratchet Algorithm

6. The Triple Ratchet: combining Secure Messaging protocols for hybrid security 6.1 Overview The Double Ratchet algorithm is used by two parties to exchange encrypted messages based on a shared secret key. Typically the parties will use some key agreement protocol (such as PQXDH [[1]]( ) to agree on the shared secret key. Following this, the parties will use the Double Ratchet to send and receive encrypted messages. The parties derive new keys for every Double Ratchet message so that earlier keys cannot be calculated from later ones. The parties also send Diffie-Hellman public values attached to their messages. The results of Diffie-Hellman calculations are mixed into the derived keys so that later keys cannot be calculated from earlier ones. These properties gives some protection to earlier or later encrypted messages in case of a compromise of a party’s keys. The Double Ratchet and its header encryption variant are presented below, and their security properties are discussed. We define a KDF as a cryptographic function that takes a secret and random KDF key and some input data and returns output data. The output data is indistinguishable from random provided the key isn’t known (i.e. a KDF satisfies the requirements of a cryptographic “PRF”). If the key is not secret and random, the KDF should still provide a secure cryptographic hash of its key and input data. The HMAC and HKDF constructions, when instantiated with a secure hash algorithm, meet the KDF definition [[2]]( , [[3]]( . We use the term KDF chain when some of the output from a KDF is used as an output key and some is used to replace the KDF key, which can then be used with another input. The below diagram represents a KDF chain processing three inputs and producing three output keys: 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. In a Double Ratchet session between Alice and Bob each party stores a KDF key for three chains: a root chain , a sending chain , and a receiving chain (Alice’s sending chain matches Bob’s receiving chain, and vice versa). As Alice and Bob exchange messages they also exchange new Diffie-Hellman public keys, and the Diffie-Hellman output secrets become the inputs to the root chain. The output keys from the root chain become new KDF keys for the sending and receiving chains. This is called the Diffie-Hellman ratchet . The sending and receiving chains advance as each message is sent and received. Their output keys are used to encrypt and decrypt messages. This is called the symmetric-key ratchet The next sections explain the symmetric-key and Diffie-Hellman ratchets in more detail, then show how they are combined into the Double Ratchet. Every message sent or received is encrypted with a unique message key . The message keys are output keys from the sending and receiving KDF chains. The KDF keys for these chains will be called chain keys . The KDF inputs for the sending and receiving chains are constant, so these chains don’t provide break-in recovery. The sending and receiving chains just ensure that each message is encrypted with a unique key that can be deleted after encryption or decryption. Calculating the next chain key and message key from a given chain key is a single ratchet step in the symmetric-key ratchet . The below diagram shows two steps: Because message keys aren’t used to derive any other keys, message keys may be stored without affecting the security of other message keys. This is useful for handling lost or out-of-order messages (see Section 2.6 ). If an attacker steals one party’s sending and receiving chain keys