Questions regarding the double ratchet algorithm.

Question

I have two questions regarding the double ratchet algorithm, one for the symmetric- and asymmetric-ratchet, respectively.

The lecture slides explicitly state that ciphertext may get lost (I understand it that they are not received by the recipient). The message would have been with encrypted with message key mk1 and the sender increments the symmetric ratchet and sends a next message with message key mk2. The receiver did not receive the previous message and therefore tries to decrypt this message with key mk1. How is this case handled. Also, how is the sequential message key generation handled when messages arrive not in order?

For the asymmetric ratchet, how do the two parties know when to decrypt messages with a new key? Do they just try all previous keys until the decryption with some key succeeds? When do we know that no old messages (that took a long time to send) will arrive anymore and we can discard the key?

Thank you!

Answer 1

Hi,

A small addition to Niklas answer:

This explains it: https://signal.org/docs/specifications/doubleratchet/#out-of-order-messages

Signal stores a message id within the current chain in the message header.
Signal will then advance the ratchet and store the message keys for later use if a message is received out-of-order. For example, if message 2 arrives before message 1, the ratchet will be advanced by one step, the message key will be saved for later use and then it will be advanced again to decrypt message 2. Once message 1 arrives, the stored message key will be used to decrypt the message.

Signal also stores the number "PN" in the message header.
This number represents the amount of messages sent within the last chain.
If a new chain key is established and the symmetric ratchet starts at 0, PN keys will be stored for later use using the old chain key.

Cheers,
Sebastian

Answer 2

If messages get lost, the receiving side can simply ratchet again and try to decrypt the message with the next (in this case, correct) key

The second question is great and more nuanced. In theory, you could never be sure about potentially unreceived messages. In the end, implementing applications would have to make a decision about when to delete old keys and how many unreceived messages to anticipate.

Best,
Niklas