4
$\begingroup$

One of the basic ideas of the Double Ratchet algorithm is that it performs DH exchanges in-band using a clever “half-DH” trick.

For some reason, instead of directly deriving the Chain Key from the DH exchange, it adds another layer: the Root Key. The Root Key is stored by both parties and is updated on every “half-DH” using the DH result and the previous Root Key. In the same way a new Chain Key is derived from the DH result and the previous Root Key.

Why is this Root Key needed? What would go wrong if we used solely DH to derive Chain Keys?


I went through the original description of the algorithm and a number of papers that study the security of Signal and WhatsApp implementations, but no one mentions Root Keys.

The only plausible explanation I found is in this blogpost. Basically it says that if we are so unlucky that the attacker is capable of breaking DH, deriving the Chain Key from DH is completely insecure. The fact that the Root Key is also mixed in means that the attacker will have to intercept and break every single prior “half-DH”-exchange. That makes perfect sense, but is that the only benefit?

$\endgroup$
  • $\begingroup$ " What was the original motivation of the designers of the protocol?" How are we supposed to answer that part of the question? Why don't you ask them? $\endgroup$ – Maarten Bodewes Sep 11 '16 at 14:10
  • $\begingroup$ @MaartenBodewes Well, that’s the less interesting part of the question, I can remove it if you insist. I was hoping that the answer to this part might have been spelled out somewhere, where I couldn’t find it. Or that someone’s answer to the other part will show a benefit I missed which is obviously what that extra layer was added for originally. $\endgroup$ – kirelagin Sep 11 '16 at 14:14
  • $\begingroup$ Usually these kind of things are used to cryptographically bind the new root key with the old key, maintaining a single session instead of starting a new one. Sometimes it is also easier to couple the keys cryptographically to be able to prove the protocol to be secure using just the mathematical definitions. About the motivation: you can leave it in, but please make it at least an optional part for the question, and explicitly ask for a reference. Note that, when written well, a polite message to the original authors is pretty likely to be answered. $\endgroup$ – Maarten Bodewes Sep 11 '16 at 14:18
1
$\begingroup$

Introduction of Root key is a critical element in ensuring Break-in recovery. Below is my dig at explaining its necessity -

Why is DH ratchet used: For argument's sake, if an attacker was able to compromise a given message key, he/she would be able to compute future chain keys and message keys if only Symmetric-key ratchet were used. DH ratchet is hence introduced to prevent this and ensure Break-in recovery.

Now to answer your question:

In DH ratchet, each party generates a new DH key pair and forwards the public key component over to the other party.

Let us go by the assumption that an attacker was able to compromise the chain key at a given point when party A is sending a new DH public key to the party B. Provided that the attacker has the ability to intercept the channel, it would be trivial for him to replace A's DH public key with self generated public DH key and forward the message over to B. In doing so, the attacker can conveniently remain to be an MITM between A and B even with the DH ratchet, unless ---- the DH ratchet were to use an additional secret known only to A and B to derive the chain keys. No points for guessing what the secret is - root key.

Recall that the Root key was bootstrapped at the beginning of establishing the communication between A and B. Since this initialization used pure DH mechanism using Identity keys, there is really no way the attacker could have compromised the root key.

Continuing the narrative - So, when B makes use of attacker introduced public DH key in combination with the root key, B generates a "receiving chain key" and sends along a new public DH key. Our attacker who is intercepting the channel, now attempts to replace B's public DH key with a new self-generated DH public key and sends to A.

The attacker's intention being to to build the corresponding chains to match up to A's sending chain and B' receiving chain to successfully establish a working MITM.

But due to the introduction of 'root key' (or an updated version of it) in the DH ratchet, the attacker will not be able to generate corresponding chain that can quite match up to B's sending chain. The same holds true on the other side with A's receiving chain.

Hence, at this point when B sends a message encrypted using 'message key' derived from B's "sending chain key", the attacker would not be able to make sense of it. Note also that, at this point A and B would have to re-establish trust because the message keys/chain keys don't match up at either ends.

This way, an attacker's window of interception after a chance compromise of a 'message key' is limited until the next opportunistic 'DH ratchet' cycle.

Note that the root key also gets updated with each DH ratchet but there is no way the attacker can influence the root key or glean its contents.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.