[cryptography] Asynchronous forward secrecy encryption

Trevor Perrin trevp at trevp.net
Thu Sep 19 03:04:40 EDT 2013

On Wed, Sep 18, 2013 at 1:36 PM, Michael Rogers
<michael at briarproject.org> wrote:
> Yup, that's the fragile current design I mentioned. :-) The new design
> still depends on persistent storage, but it avoids the risk of key
> reuse if the persistent storage is unreliable.

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

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.

>> The per-message symmetric-key update that Adam and I sketched
>> doesn't require a 2-way exchange of messages.  Even a one-way
>> stream of message would receive good forward secrecy.
> Ah, sorry, I was thinking of OTR's per-message update rather than
> yours! The method you and Adam suggested would be suitable for our use
> case, and much more elegant than what we're using now, except that it
> requires a plaintext sequence number.

I think that can be avoided, more below.

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

> So we rely on the
> pseudo-random tag to tell the recipient (a) which sender the message
> comes from, (b) which rotation period the sender was in when the
> message was sent, and (c) the sequence number.

You could use "tags" with either time-based or message-based key
update, right?  In either case you need to somehow indicate the
metadata for a message (sender; sequence number or rotation period).
This seems orthogonal to when you perform updates.

> The recipient precalculates a limited number of tags in a sliding
> window, which allows a limited amount of message loss or reordering -
> but if too many messages are lost, the sender's sequence number will
> move beyond the recipient's window, and they'll have to wait until the
> next rotation period to resynchronise (the sequence number is reset at
> the start of each rotation period).

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?


More information about the cryptography mailing list