[cryptography] Asynchronous forward secrecy encryption

Trevor Perrin trevp at trevp.net
Thu Sep 19 20:55:42 EDT 2013

On Thu, Sep 19, 2013 at 1:20 PM, Michael Rogers
<michael at briarproject.org> wrote:
> We're not using time-based updates because of the storage reliability
> issue. We're using them because of two issues with message-based updates.
> First, if messages are lost, the sender and recipient can lose
> synchronisation: if the sender's sequence number moves beyond the
> recipient's window, the sender will start using tags that the
> recipient doesn't recognise. To re-synchronise they need to reset the
> sequence number periodically.
> Second, if a message is intercepted by the adversary and not received,
> the recipient will keep the corresponding key until it moves out of
> the sliding window. If the sender stops sending messages or the
> adversary keeps intercepting them, that may never happen, so there
> won't be forward secrecy for the intercepted message. With time-based
> updates, the recipient will delete the key regardless of whether the
> message is received.

Good points.

If you can do "encrypted metadata" instead of tags you can solve the
first issue.

The second seems more of a tradeoff:  Message-based updating is better
than time-based against a passive attacker.  But if the attacker is
blocking messages, time-based becomes better.

I'd still prefer message-based for most uses.  It avoids clock issues
and will be better unless the attacker blocks traffic flow, which will
often raise alarms.

You could also combine approaches, and update keys whenever a message
is sent or received, *or* whenever X (hours/days/whatever) have
elapsed since the key was last used.

> Briar's initial key agreement takes place face-to-face over a
> short-range transport such as Bluetooth. The key agreement protocol is
> weakly obfuscated using the invitation codes the parties verbally
> exchange to enable their devices to find each other.

Interesting, are the codes passwords?  Short Auth Strings?

(Elligator + DH-EKE makes a nice PAKE, fwiw.)

>> If you don't want recipients to have to check so many tags, you
>> could encrypt the metadata with longer-lived keys (trading off
>> forward-secrecy of metadata for easier processing).  For example,
>> each pair of users could have 2 symmetric keys they use to encrypt
>> metadata (one for each direction).  Perhaps they could even update
>> their sending key whenever the other party ACKs it?
> This is a possibility we've discussed. But if the recipient
> corresponds with several senders, she has to try decrypting the
> metadata with all their keys. Apart from being inefficient, the timing
> reveals how many senders she corresponds with.

It's not elegant.  But the inefficiency and timing leak might not be a
huge problem.

> * Each recipient has a long-term ECDH key pair
> * Each message starts with an ephemeral ECDH public key
> * The ephemeral public key is indistinguishable from random (Elligator)
> * The sender and recipient derive an ephemeral shared secret from the
> ephemeral key pair and the recipient's long-term key pair
> * A key derived from the ephemeral shared secret is used to obfuscate
> the metadata (sender's identity and sequence number)
> * The recipient uses the metadata to know which keys to use for
> authenticating and decrypting the message

Seems fine, with a couple caveats:
 - You're giving up forward-secrecy for metadata.  If a user's
long-term key is compromised, the metadata of her inbound messages can
be revealed.
  - Handling key rollover could be tricky (ie transitions from one
long-term key to another).

There's also some crypto costs (asymmetrics ops on every message,
message expansion).

But there could be side benefits.  For example, you could use the
ephemeral-static ECDH for encrypting the message as well as the
metadata.  Then, even if all the sender's keys have been stolen
earlier, new messages from her would not be decryptable by an


More information about the cryptography mailing list