After doing a handshake using X3DH, Both users can authenticate each other and agree on a shared master secret.

So what’s next?

The easiest solution is do as TLS: client and server share client_write_{key, iv} and server_write_{key, iv} and use a per-record sequence number to encrypt and decrypt messages in the session. However, as said in the previous post, in the situation of instant messaging software, one side of client may be offline for a long time. As a result , there exist some risk that once the client_write_{key, iv} and server_write_{key, iv} are compromised (though it’s kind of hard by brute forcing), all the future messages will be transparent to Mallory.

Thus, it’s very important to introduce an algorithm that add extra entropy while don’t have handshake again to generate a new master secret (which is quite expensive). This is why Double Ratchet was designed.

Here I am using Double Ratchet without header encrypted as example.

The Key Chain

The most important thing in Double Ratchet is maintaining key chains with three properties:

• 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.

And each user will need to maintain three key chains similar to TLS except the root key chain:

1. Root chain: generate new root key for new write/read key and iv once receiving some new messages;

2. Writing chain: generate new write key and iv so user can encrypt messages with different key and iv while no new responses back;

3. Reading chain: generate new read key and iv to corresponding to the write keys and ivs in sequences for decryption.

Here writing chain and reading chain are very similar. They are both symmetric chains as their value only depends on the output value from root chain and previous write/read key.

The reason to introduce root chain is that writing chain and reading chain are both symmetric, once Mallory managed to steal some KDF output, this is no forward secrecy. However, The root chain’s key value depends on the previous root key and a new key generated by DH exchange (e.g. X22519). This will ensure that there won’t be a too long writing chain or reading chain.

As shown in the picture above, the new root key and new write/read key will be generated once Bob send a new X25519 Public key in the header of a new message.

State Storing

It’s very important to keep track of chains so the program can tell use which key to encrypt or decrypt:

For each user we need keep a record like this:

{
    "bob": {
      "RK": "The latest rook key input material",
      "DH_pair": ["Alice's current private key", "Alice's current public key"],
      "DH_p": "Current DH remote public key(Bob)",
      "CKs": ["list of the latest write chain key in each round"],
      "CKr": ["list of the latest read chain key in each round"],
      "PN": "# of DH process to generate new root key"
    }
}

It’s update to you decide, the max number of write key and read key to keep in the list

Note: we just need save the latest root key as for previous rounds write key or read key has been generated. So does DH_pair.

Then in code:

# Continue in Class Client from previous

    def dr_state_initialize(self, user_name, RK, DH_pair, DH_p):
    self.dr_keys[user_name] = {
        "RK": RK,
        "DH_pair": DH_pair,
        "DH_p": DH_p,
        "CKs": [],
        "CKr": [],
        "Ns": 0,
        "Nr": 0,
        "PN": 0
    }

Integration with X3DH

Double Ratchet is usually integrated with X3DH. We can initialize user state with the result from X3DH.

• Alice (X3DH Sender):

  • DH_pair: The EK, ephemeral key pair;
  • DH_p: remain blank, waiting for Bob’s first response in DR format.

• Bob (X3DH Receiver):

  • DH_pair: remain blank, generate when send first message in DR format;
  • DH_p: The EK_pa from X3DH Hello message.

Core Functions

Following are the core functions implemented following the recommendations from Signal.

Key Generation functions

The KDF in the chains create new keys and iv to move the ratchet.

• Root Key KDF:

  Create rk_input_material for next round root key ratchet and ck for this round.

  Both 32 bytes long

from Crypto.Protocol.KDF import HKDF

def KDF_RK(rk, dh_out):
    out = HKDF(dh_out, 64, rk, SHA256, 1)

    rk_input_material = out[:32]
    ck = out[32:]
    return rk_input_material, ck

• Write/Read Chain Key KDF:

  Create ck_input_material for next round and mk to encrypt/decrypt this round’s message.

  Both are 32 bytes long.

  ck_input_material: use constant b'\x01' as message input;

  mk: use constant b'\x02' as message input.

from Crypto.Protocol.KDF import HKDF

def KDF_CK(ck):
    ck_input_material = HMAC.new(ck, digestmod=SHA256).update(b'\x01').digest()
    mk = HMAC.new(ck, digestmod=SHA256).update(b'\x02').digest()
    return ck_input_material, mk

Data Encryption

To generate the ciphertext in ENCRYPT() we need use mk to create keys K by:

K = HKDF(mk, 80, b'\0' * 80, SHA256, 1)

then sign header||plaintext||dh_pub_b using HMAC.new(K[32:64], digestmod=SHA256)

then pad signature||plaintext with empty bytes to make it fit AES Block Size,

then encrypt padded signature||plaintext using AES.new(K[:32], AES.MODE_CBC, iv=K[64:])

Finally concat ciphertext as:

iv||AES(K[:32], Sig(K[32:64], header||plaintext||dh_pub_b), plaintext).

Payload Format

We can use JSON to separate header and ciphertext:

{
    "header": {
        "dh_p": "<New DH public key>",
        "pn": "<# of DH process to generate new root key(Including generating this message)>",
        "n": "<# of Message sent (Including this)>"
    },
    "ciphertext": "<output of ENCRYPT(mk, plaintext, header)>"
}

Ratchet Update

For each user, the key chains updated in the conditions below:

• Sending:

  • Generate a new root key as send chain root key:

    1. At the initial state, there is no DH_pair to use;
    2. After receiving a new DH_p in the message header.

  • Use the existing send chain key:

    1. Try to send a message when not receive a new DH_p yet.

• Receiving:

  • Generate a new root key as read chain root key:

    1. When there is a different DH_p in message header and having a bigger PN

  • Use existing read chain key:

    1. When message header has a smaller PN than the local one

Fin

Though Double Ratchet is quite complicated. But keep in mind that, this is like playing a ping-pong game, update the root key and stop using the latest write key chain only when the ‘ball’ is back.

Certainly, the double ratchet and X3DH can be more secure, compared to TLS. However, this still only protects the application layer. But it’s still a very good solution since almost every key is dynamic in a long term session.