[Cryptography] Ratcheting

[brennan.tobias at openmailbox.org]

Hello!

I'd like to open a thread about ratcheting in messaging between two 
parties. In particular the security it aims to provide and what threats 
it protects against.

# Background

It looks like any good encrypted messenger must include a cryptographic 
ratchet [1]: The part of a cryptographic protocol that constantly 
refreshes keys to reduce the impact of a key being leaked. A couple 
examples of this are the OTR ratchet [2] and Axolotl [3] (also used in 
Pond [4]).

I found these protocols a bit complicated and in the interest of 
designing something simple got thinking about the purpose of ratchets. 
Also correct me if I'm wrong but some of the complexity in the Axolotl 
is because it's designed to work over a lot of different transports 
including SMS? So if restricted to TCP, a slightly simpler protocol 
should be possible.

There seems to be 4 levels of security that are provided by increasingly 
strong ratchets:

* (A) None. Alice and Bob just use their public keys to exchange a 
secret upon which to build a secure channel.
* (B) Ephemeral key establishment. Alice and Bob generate and exchange 
ephemeral keys at the beginning and use those to establish a shared 
secret.
* (C) Consistent key update. Like B, but generating or deriving a new 
shared secret every few messages.
* (D) Consistent ephemeral key reestablishment. Doing a new ephemeral 
key establishment every few messages.

The problem with (A) is that a passive capture of the traffic can be 
decrypted if alice or bobs key is compromised in future, (B) fixes this. 
(B) should be secure against a man in the middle attack given that the 
public private key communication they use is authenticated.

The worry about (B) that demands stronger security is that entire 
conversations (that might last days) are encrypted using a single key, 
if that key were leaked the entire conversation could be decrypted. (C) 
attempts to fix this by "ratcheting" a key forwards (e.g. using a key 
derivation function), in that case a compromise at message 'm' only 
leads to decryption of later messages: m,m+1,m+2,.. The aim of (D) is to 
limit the extent of a compromise to only a short number of messages 
after the compromised one: m,m+1,m+2 (say).

# Threat Modelling

My understanding is that (A) is already secure against the Dolev-Yao 
model/semantic security, so we are looking for realistic threats outside 
of that model. The main one is conversations where Alice and Bob give up 
their keys after the conversation and (B) is secure against this.

What sorts of attacks exists that might be able to compromise temporary 
secret keys during a conversation? some ideas:

* (T1) someone could take the device Bob is using to talk to Alice.
* (T2) an active attacker might perform an exploit on the software and 
do a heartbleed style memory read to compromise the keys
* (T3) same as T2 but full remote code execution
* anything missing here?

Trying to judge the importance of the security of C and D relative to 
the cost of implementing them and what resources they require: I don't 
think anything cryptographic can protect against T1 so users should 
attempt to protect against it with physical security.

C is quite easy to achieve in a couple different ways, only requiring an 
erasing PRNG or key derivation function. That protects against T2 and T3 
since they older keys will have been erased from memory.

D is what things like OTR and ratchet do, one very heavyweight way to do 
it is perform the full ephemeral establishment every message. Or you 
could stagger it. This gets complicated and hard to get right. I think 
it only protects against T2 though, not T3 so I doubt this is worth it.

A much better way to protect against T2 and T3 would be to secure the 
implementation from vulnerabilities. Of course this is hard..

# Questions

What do you think? Is my analysis realistic? What important points am I 
missing? Do we know of many real-life examples of attacks that ratchets 
have or haven't protected against.

# Links

* [1] https://whispersystems.org/blog/advanced-ratcheting/
* [2] https://otr.cypherpunks.ca/Protocol-v3-4.0.0.html (No explicit 
mention of "ratchet" but the section about Exchanging data covers it)
* [3] https://github.com/trevp/axolotl/wiki
* [4] https://pond.imperialviolet.org/tech.html