Forward secrecy for offline messages in Bleep

Steven —  August 6, 2015 — Leave a comment

Our initial implementation of asynchronous offline messaging in Bleep[1] used an encryption scheme which provided authentication and confidentiality, but not forward secrecy[2]. This meant that if the private key of Alice or Bob was compromised, Eve could use the key to decrypt any of their offline messages she had previously captured.

Providing forward secrecy for offline messages is not as straightforward as it is for messages sent when both Alice and Bob are online. For the latter, forward secrecy is provided as part of our encrypted tunnel protocol. If either Alice or Bob is offline a tunnel cannot be established. Thus for offline messages we must find an alternative method of providing forward secrecy.

A key element of forward secrecy is the use of ephemeral keys. Ephemeral keys are used for some short period of time then discarded. Once a key is discarded any data encrypted with it cannot be decrypted ever again. Our encrypted tunnel protocol generates new ephemeral keypairs for every connection and exchanges the public component of them as part of the handshake used to establish the connection. Of course this handshaking only works if Alice and Bob are both online, so how can they exchange ephemeral keys when one of them is offline?

Happily, the same DHT facility we use to exchange offline messages can also be used to exchange ephemeral keys. When Alice and Bob first add each other as contacts they generate ephemeral keypairs and publish the keys’ public components in the DHT, just as they would an offline message. Alice and Bob save each other’s offline ephemeral keys for future use. When Alice wants to send an offline message to Bob she uses their saved ephemeral keys to encrypt the message. When Bob receives the message he uses his copy of the ephemeral keys to decrypt it. After decrypting the message, Bob discards his ephemeral key and publishes a new one in the DHT. Once Alice sees Bob’s new ephemeral key she replaces the one she has stored for him.

One downside of this scheme is that the granularity with which messages are rendered indecipherable is larger than when using our encrypted tunnels. There are multiple factors which make this reduced granularity unavoidable. The structure of data stored in the DHT means that messages can only be received in last-in-first-out order. This means that if we were to ratchet the key between each message, as we do for encrypted tunnels, a recipient would not be able to decrypt a list of messages until the entire list was received. This would defeat the point of ratcheting so we do not use it for offline messages. Of course, the asynchronous nature of offline messages requires allowing Alice to encrypt any number of messages without receiving a new ephemeral key from Bob. For lack of a better option we simply reuse the same key for every message until a new ephemeral key is received. Thus forward secrecy is only maintained up to the last time Alice and Bob managed to exchange ephemeral keys via the DHT.




Steven Siloti is a senior software engineer and DHT specialist on the Bleep development team.