[cryptography] Asynchronous forward secrecy encryption

Michael Rogers michael at briarproject.org
Thu Sep 19 16:20:04 EDT 2013

Hash: SHA1

On 19/09/13 08:04, Trevor Perrin wrote:
> I'd have to see a writeup to have real comments.  But to address
> the issue of "fragility":
> It seems you're worried about per-message key updates because in
> the (infrequent?) case that a sender's write to storage fails, an
> old key would be reused for the next message.
> What happens in that case?  You mentioned random IVs, so I assume
> the only problem is that the recipient can't decrypt it (as she's
> already deleted the old key on receipt of the previous message).

The key reuse issue isn't related to the choice between time-based and
message-based updates. It's caused by keys and IVs in the current
design being derived deterministically from the shared secret and the
sequence number. If an endpoint crashes and restarts, it may reuse a
key and IV with new plaintext. Not good.

In the new design, the temporary keys are still derived
deterministically from the shared secret, but the IVs and ephemeral
keys are random. The sequence number's only used for generating tags.
So if an endpoint crashes and restarts, it may reuse a tag, but it
will use a fresh IV and ephemeral key, so confidentiality and
integrity won't be lost.

> That's not great, but again this should be rare.  I think you're 
> trying to make decryption failures even rarer by performing less 
> frequent time-based updates (instead of message-based).  But that 
> introduces time-sync and latency failure cases that didn't exist 
> before.  So I'm skeptical it's a reliability win.

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.

>> We've tried to avoid plaintext fields in BTP to make it harder
>> to design filter rules to detect or block the protocol.
> Makes me curious to see your key agreement.  Elligator?

I hadn't heard of Elligator - thanks for the tip!

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.

> 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.

The recipient could have a long-term public key that senders would use
for encrypting metadata. Until now I didn't know of any public key
cryptosystems with ciphertexts that were indistinguishable from random
strings - but maybe Elligator can serve that purpose:

* 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

This would work with time-based or message-based updates, and would
allow us to get rid of tags and sliding windows, which would be
fantastic. Any thoughts?


Version: GnuPG v1.4.10 (GNU/Linux)


More information about the cryptography mailing list