Double Ratchet Algorithm

Key Exchange and Key Generation Mechanism in the Double Ratchet Protocol

Once the initial key exchange using X3DH is completed, subsequent communications are managed by the Double Ratchet Protocol. The Double Ratchet Protocol generates new keys for each message, providing higher security.

The session key established by X3DH serves as the root key for the Double Ratchet Protocol and forms the basis for all subsequent key exchanges and message encryption processes. The chain key derived from the root key generates the encryption keys used for each message, ensuring secure communication.

The Double Ratchet Algorithm

DH Ratchet

1. DH Key Exchange (Diffie-Hellman)

The two key pairs (Private Key and Public Key) on the left side of the diagram are used for the Diffie-Hellman (DH) key exchange. Participants in the communication generate a shared key using each other’s public keys and their own private keys. This shared key is securely shared without being known to third parties.

Private Key: The member’s secret key, updated at each ratchet step to generate new key pairs.
Public Key: The key published to the other party, used to generate the shared key.
DH: The shared key is generated using the other party’s public key and your own private key. This shared key is used as input for the KDF.

2. KDF (Key Derivation Function)

The KDF in the middle of the diagram is a function that generates new keys from the shared key and other keys (like the root key).

Key, In: The input consists of the shared key (result of the DH key exchange) and the existing root key.
Out: The KDF outputs new keys for use. Here, new root keys and either the sending or receiving chain keys are generated. Using the KDF ensures that keys are updated each time, providing “forward secrecy,” which guarantees that even if an attacker obtains past keys, future messages remain protected.

3. Root Key

The root keys at the top and bottom of the diagram are updated by the KDF and will be used again in the next ratchet step. The root key is the fundamental key that continues from the beginning of the encrypted communication, constantly updated through KDF calculations.

4. Sending Chain Key and Receiving Chain Key

The sending chain key and receiving chain key shown on the right side of the diagram are the keys used for encrypting the messages.

Sending Chain Key: The key used when sending messages.
Receiving Chain Key: The key used when receiving messages. The generation of different chain keys for sending and receiving ensures that the security of sending and receiving remains independent.

Double Ratchet Protocol

The “double” in Double Ratchet refers to two different ratchet mechanisms. This protocol combines two types of key generation mechanisms (ratchets) to enhance the security of communication.

Each Ratchet

1. Symmetric-Key Ratchet

Symmetric-Key (Send/Receive) Ratchet is a mechanism for generating new keys based on an existing symmetric key (session key). Each time a new message is sent, the next key is generated from the previous one. This ensures “forward secrecy,” protecting new keys even if past keys are leaked.

Keys are updated for each message.
By updating keys with each message sent or received, each message is protected individually.

2. Public-Key Ratchet

Public-Key (DH) Ratchet is used for performing new key exchanges during the session. This key exchange occurs asynchronously, where one user generates a new key pair and sends the public key to the other. This enables long-term key updates, further reducing the impact of past key leaks.

A new public key pair is exchanged during the communication session.
Based on the new public key, both parties generate a new session key.

The Public-Key (DH) Ratchet consists of updating the root KDF chain twice and using the KDF output key as the new sending and receiving chain keys.

The “Double Ratchet” protocol is designed to guarantee both forward secrecy and post-compromise security.

Forward Secrecy: Different keys are used for each new message, so even if past keys are leaked, new messages remain protected.
Post-Compromise Security: If a secret key is leaked during a session, future messages remain securely protected due to the public-key ratchet.

Alice’s Ratchet Flow

Double Ratchet Flow

Image of Alice and Bob’s Ratchet Flow

Double Ratchet

The send/receive ratchet A1 was generated previously.
Alice encrypts the message using the message sending key generated by ratchet A1.
Bob, upon receiving it, decrypts the message using the message receiving key generated by ratchet A1.

Bob performs ratchet DH1 to send a message in a new session and sends the public key to Alice.
Alice executes ratchet DH1 with Bob’s new public key and her new and old private keys, generating the necessary chain keys (two types: sending and receiving) for generating the message sending and receiving keys.
Ratchet DH1 executes to generate the message sending and receiving keys for sending ratchets A2, A3, A4, B1, and B2.

After Bob receives message A4, he again performs ratchet DH2 and sends the public key to Alice.
Alice executes ratchet DH2 with Bob’s new public key and her new and old private keys, generating the necessary chain keys (two types: sending and receiving) for generating the message sending and receiving keys.
Ratchet DH2 executes to generate the message sending and receiving keys for sending ratchets A5, B3, and B4.

HKDF (HMAC-based Key Derivation Function)

HKDF is a Key Derivation Function based on HMAC (Hash-based Message Authentication Code), which generates keys used for encryption and authentication from existing secret information (e.g., shared keys or random values).

HKDF consists of the following two main steps.

Extract Phase:

From the input secret information (random values or shared keys), a consistent length of “Pseudo-Random Key (PRK)” is generated. This process uses HMAC, compressing the input data with the HMAC hash function.

Expand Phase:

Based on the PRK obtained in the extract phase, key material of the required length is generated. The expansion process also uses HMAC.

In Linphone’s LIME, SHA512 is introduced as the HMAC hash function (HKDF_RK, HKDF_CK) for generating root keys and chain keys.

HKDF_RK

function KDF_RK(RK<32bytes>, DH_out<32, 56bytes>)
	info ← "DR Root Chain Key Derivation"
	RK<32bytes> || CK<32bytes> ← HKDFSha512(RK, DH_out, info)
	return RK<32bytes>, CK<32bytes>
end function

salt: RK (Root Key)
ikm: the output of ECDH (DH_out)
info: “DR Root Chain Key Derivation”
CK: Chain Key Note: DH_out: X25519 >>> 32 bytes output, X448 >>> 56 bytes output, || means concatenation

function HKDFSha512(salt, ikm, info)
	return okm
end function

salt: optional
ikm: input key material
info: string
okm: output key material

HKDF_CK

function KDF_CK(CK<32bytes>)
	MK || IV ← HmacSha512(ChainKey, 0x01)
	CK ← HmacSha512(ChainKey, 0x02)
	return CK<32bytes>, MK<32bytes>, IV<16bytes>
end function

MK: Message Key
IV: Initialization Vector Note) || means concatenation

Message Encryption and Decryption

In the Double Ratchet Protocol, each message is encrypted with a new symmetric key. AES-256-GCM is used to encrypt the message itself.

Encryption: The sender encrypts the message using the generated symmetric key with AES-256-GCM. During this process, the GCM mode generates an authentication tag. A random value called a nonce (or Initialization Vector, IV) is required for encryption.

Decryption: The recipient generates the symmetric key corresponding to the received message through the ratchet process, using AES-256-GCM to decrypt the message and check the authentication tag to ensure it has not been tampered with.

Message Authentication

AES-256-GCM not only encrypts but also provides authentication features to prevent message tampering. GCM (Galois/Counter Mode) generates an authentication tag to verify the integrity of the encrypted data.

Tampering: If an attacker modifies the encrypted data, the authentication check will fail upon decryption, allowing the recipient to detect tampering.