Subject: [MLS] Unpredictable epochs?

From: Richard Barnes <[email-masked]>
Date: Mon, 22 Apr 2019 18:11:00 -0400

Hey all,

As I've been working with Benjamin on updating and landing the common
framing PR, I noticed that the epoch is still exposing more information to
the DS than it needs to.

Right now, the epoch just increments by one every time the epoch changes.
This lets the DS track epochs statelessly -- it can take any two messages
and see which was before the other, without the need for any ongoing
tracking.

However, the epoch only needs to be intelligible to members of the group,
so we could generate epoch values in a way that would only be intelligible
to members.  For example [1]:

epoch_[n] = HKDF-Expand-Label(some_secret_for_epoch_[n], epoch_[n-1],
"epoch", 4)

That way, the DS could observe epoch changes, and observe how many messages
were sent within each epoch.  But it wouldn't be able to understand the
sequence unless it tracked things all along.

A side benefit of this is that it allows the group to have forks in its
history more cleanly, since different forks will have different epoch
numbers.  That could allow some softness in the ordering requirement, as
long as the group can eventually figure out which branch is the right one
[2].

Does this seem worthwhile to people?  The cost is a few extra hashes.  To
me, the completeness/consistency seems like a marginal benefit, but the
clean forking seems pretty convincing.  If folks think this worthwhile, I'm
happy to write up a PR.

Thanks,
--Richard

[1] I would probably keep epochs at 4 bytes, because any more seems
wasteful.
[2]
http://mycours.es/gamedesign2012/files/2012/08/The-Garden-of-Forking-Paths-Jorge-Luis-Borges-1941.pdf

---

From: Benjamin Beurdouche <[email-masked]>
Date: Tue, 23 Apr 2019 00:42:03 +0200

Side note before I forget. After merging the common framing, the only two things potentially remaining in the clear will be the group identifier and the epoch number (because we need those to pick the group key necessary to decrypt the sender info). Raphael and I talked about adopting a similar approach but generating an ephemeral Group Id at the same time. That could help a bit on the meta data protection side by making it harder for an adversarial DS to be able to correlate messages in delivery queues across groups and across epochs. The fact that this might be useful or not depends a lot on architecture assumptions though....

B.

> On Apr 23, 2019, at 12:11 AM, Richard Barnes <[email-masked]> wrote:
> 
> Hey all,
> 
> As I've been working with Benjamin on updating and landing the common framing PR, I noticed that the epoch is still exposing more information to the DS than it needs to.  
> 
> Right now, the epoch just increments by one every time the epoch changes.  This lets the DS track epochs statelessly -- it can take any two messages and see which was before the other, without the need for any ongoing tracking.
> 
> However, the epoch only needs to be intelligible to members of the group, so we could generate epoch values in a way that would only be intelligible to members.  For example [1]:
> 
> epoch_[n] = HKDF-Expand-Label(some_secret_for_epoch_[n], epoch_[n-1], "epoch", 4)
> 
> That way, the DS could observe epoch changes, and observe how many messages were sent within each epoch.  But it wouldn't be able to understand the sequence unless it tracked things all along.
> 
> A side benefit of this is that it allows the group to have forks in its history more cleanly, since different forks will have different epoch numbers.  That could allow some softness in the ordering requirement, as long as the group can eventually figure out which branch is the right one [2].
> 
> Does this seem worthwhile to people?  The cost is a few extra hashes.  To me, the completeness/consistency seems like a marginal benefit, but the clean forking seems pretty convincing.  If folks think this worthwhile, I'm happy to write up a PR.
> 
> Thanks,
> --Richard
> 
> 
> [1] I would probably keep epochs at 4 bytes, because any more seems wasteful.
> [2] http://mycours.es/gamedesign2012/files/2012/08/The-Garden-of-Forking-Paths-Jorge-Luis-Borges-1941.pdf
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Richard Barnes <[email-masked]>
Date: Mon, 22 Apr 2019 18:49:46 -0400

True, you could have one unpredictable identifier that identifies both the
group ID and the epoch.  I like how that looks on the wire, but would
require a bit more bookkeeping in clients.  I might be inclined to go ahead
and land an unpredictable-epoch PR in -05 (since that's a pretty small
change), then look at folding in the group ID later.
--RLB

On Mon, Apr 22, 2019 at 6:42 PM Benjamin Beurdouche <
[email-masked]> wrote:

> Side note before I forget. After merging the common framing, the only two
> things potentially remaining in the clear will be the group identifier and
> the epoch number (because we need those to pick the group key necessary to
> decrypt the sender info). Raphael and I talked about adopting a similar
> approach but generating an ephemeral Group Id at the same time. That could
> help a bit on the meta data protection side by making it harder for an
> adversarial DS to be able to correlate messages in delivery queues across
> groups and across epochs. The fact that this might be useful or not depends
> a lot on architecture assumptions though....
>
> B.
>
> That way, the DS could observe epoch changes, and observe how many
> messages were sent within each epoch.  But it wouldn't be able to
> understand the sequence unless it tracked things all along.
>

---

From: Benjamin Beurdouche <[email-masked]>
Date: Tue, 23 Apr 2019 00:52:24 +0200

+1

> On Apr 23, 2019, at 12:49 AM, Richard Barnes <[email-masked]> wrote:
> 
> True, you could have one unpredictable identifier that identifies both the group ID and the epoch.  I like how that looks on the wire, but would require a bit more bookkeeping in clients.  I might be inclined to go ahead and land an unpredictable-epoch PR in -05 (since that's a pretty small change), then look at folding in the group ID later.
> --RLB
> 
> 
>> On Mon, Apr 22, 2019 at 6:42 PM Benjamin Beurdouche <[email-masked]> wrote:

---

From: Richard Barnes <[email-masked]>
Date: Tue, 23 Apr 2019 11:03:20 -0400

Here's a PR:

https://github.com/mlswg/mls-protocol/pull/152/files

On Mon, Apr 22, 2019 at 6:52 PM Benjamin Beurdouche <
[email-masked]> wrote:

>> Right now, the epoch just increments by one every time the epoch
>> changes.  This lets the DS track epochs statelessly -- it can take any two
>> messages and see which was before the other, without the need for any
>> ongoing tracking.
>>

---

From: Michael Rosenberg <[email-masked]>
Date: Fri, 26 Apr 2019 02:22:56 -0400

I like this idea, especially because it allows for partial ordering of GroupStates. One question: could the tree_hash be used instead of an epoch? The tree_hash...
  * ...is not "predictable" in that it would require the DS to maintain state in order to establish an ordering on GroupStates
  * ...necessarily changes after any GroupOperation is applied to a GroupState
  * ...is already built into the GroupState

So why not remove epoch entirely?

Also, side note: given that the tree hash necessarily changes upon each update of the transcript, why is transcript_hash necessary anymore?

-Michael

> On Apr 23, 2019, at 11:03 AM, Richard Barnes <[email-masked]> wrote:
> 
> Here's a PR:
> 
> On Mon, Apr 22, 2019 at 6:52 PM Benjamin Beurdouche <[email-masked]> wrote:
> +1
>

---

From: Richard Barnes <[email-masked]>
Date: Fri, 26 Apr 2019 08:28:50 -0400

Well, I don't think we can get rid of the epoch entirely.  For handshake
messages, you could maybe get by with the theory that if a message doesn't
apply to the single most recent state, then it's no good, so you don't need
to explicitly say which state it applies to.  But that seems painful,
especially if you want to tolerate a degree of partial order / forking
history.  For application messages, you definitely need it, otherwise you
have an issue with application messages being out of order with handshake
messages.

That said, it does seem like we could maybe steal the epoch from elsewhere
and save a few hash invocations.  The question is what value we could
re-use that wouldn't be leaking information.  The tree hash seems bad from
that perspective, because it is never transmitted in the clear otherwise.
Another option I had pondered was re-using the confirmation MAC value.  In
any case, as a first effort, it seemed simpler to derive a value for the
purpose.

W.r.t. the transcript hash - I have the same suspicion you do, but I am
waiting for someone with a security proof in hand to tell me it's OK to
remove :)

On Fri, Apr 26, 2019 at 2:22 AM Michael Rosenberg <[email-masked]>
wrote:

> I like this idea, especially because it allows for partial ordering of
> GroupStates. One question: could the tree_hash be used instead of an epoch?
> The tree_hash...
>   * ...is not "predictable" in that it would require the DS to maintain
> state in order to establish an ordering on GroupStates
> Also, side note: given that the tree hash necessarily changes upon each
> update of the transcript, why is transcript_hash necessary anymore?
>
> -Michael
>
> >> True, you could have one unpredictable identifier that identifies both
> the group ID and the epoch.  I like how that looks on the wire, but would
> >> Side note before I forget. After merging the common framing, the only
> two things potentially remaining in the clear will be the group identifier
> and the epoch number (because we need those to pick the group key necessary
> to decrypt the sender info). Raphael and I talked about adopting a similar
> >>> However, the epoch only needs to be intelligible to members of the
> group, so we could generate epoch values in a way that would only be
> intelligible to members.  For example [1]:
> >>>
> >>> A side benefit of this is that it allows the group to have forks in
> its history more cleanly, since different forks will have different epoch
> >>> Does this seem worthwhile to people?  The cost is a few extra hashes.
> To me, the completeness/consistency seems like a marginal benefit, but the

---

From: Benjamin Beurdouche <[email-masked]>
Date: Fri, 26 Apr 2019 15:08:14 +0200

> On Apr 26, 2019, at 2:28 PM, Richard Barnes <[email-masked]> wrote:
> 
> Well, I don't think we can get rid of the epoch entirely.  For handshake messages, you could maybe get by with the theory that if a message doesn't apply to the single most recent state, then it's no good, so you don't need to explicitly say which state it applies to.  But that seems painful, especially if you want to tolerate a degree of partial order / forking history.  For application messages, you definitely need it, otherwise you have an issue with application messages being out of order with handshake messages.
> 
> That said, it does seem like we could maybe steal the epoch from elsewhere and save a few hash invocations.  The question is what value we could re-use that wouldn't be leaking information.  The tree hash seems bad from that perspective, because it is never transmitted in the clear otherwise.  Another option I had pondered was re-using the confirmation MAC value.  In any case, as a first effort, it seemed simpler to derive a value for the purpose.
> 
> W.r.t. the transcript hash - I have the same suspicion you do, but I am waiting for someone with a security proof in hand to tell me it's OK to remove :)

I will do a round of review next week but *from what I remember* about the proposal,
I don’t think you can do that. The transcript hash contains strictly more information than
the tree hash anyway, especially for authentication. I’ll check when reviewing but if the tree hash
doesn’t cover the signatures, for example, then you can’t replace one by the other.

B.

---

From: Richard Barnes <[email-masked]>
Date: Fri, 26 Apr 2019 09:21:45 -0400

On Fri, Apr 26, 2019 at 9:08 AM Benjamin Beurdouche <
[email-masked]> wrote:

> > That said, it does seem like we could maybe steal the epoch from
> elsewhere and save a few hash invocations.  The question is what value we
> could re-use that wouldn't be leaking information.  The tree hash seems bad
> from that perspective, because it is never transmitted in the clear
> otherwise.  Another option I had pondered was re-using the confirmation MAC
> value.  In any case, as a first effort, it seemed simpler to derive a value
> for the purpose.
> >

We might have a problem in any case, then, since the transcript hash
doesn't cover the signatures either.

--Richard

---

From: Benjamin Beurdouche <[email-masked]>
Date: Fri, 26 Apr 2019 16:10:08 +0200

> On Apr 26, 2019, at 3:21 PM, Richard Barnes <[email-masked]> wrote:
> 
> We might have a problem in any case, then, since the transcript hash doesn't cover the signatures either.
> 

Ok, there might be an issue then, I am quite sure that it was covered at some
point, so it might have been lost. The slight difference with TLS is that some
messages can be discarded from processing (add_send/receive_current_member
or add_send/receive_new_member) while I expect that all of the messages must
somehow be contributed to the transcript-hash to provide the strongest authentication
properties. I’ll have a look into this...

B.

---

From: Jon Callas <[email-masked]>
Date: Fri, 26 Apr 2019 15:26:54 -0400

> On Apr 26, 2019, at 2:22 AM, Michael Rosenberg <[email-masked]> wrote:
> 

An epoch lets you deal with things happening neither too often nor not often enough. Presume there is a client that is either malicious or just stupid. You want to keep it from forcing a rekey every 100µs. You want to force a rekey every so often. Hence epochs. Yeah, picking the right epoch size is an exercise left to the reader.

	Jon

---

From: Benjamin Beurdouche <[email-masked]>
Date: Fri, 26 Apr 2019 22:18:10 +0200

> On Apr 26, 2019, at 9:26 PM, Jon Callas <[email-masked]> wrote:
> 

You can’t use the epoch number for that as it is just global counter for group operations, we will have to keep track of the latest group operation “timestamp” for each member within the group state to check “update frequency” and handle some of the situations you described.

Btw in the TreeKEM formal spec I use a 64 bit unsigned integer, and I feel like having more than 2^32 group operations over the lifetime of a group is not unrealistic in certain extreme use cases, especially with large groups forcing PCS for application messages by triggering an update after each app message...

We could remove the epoch number if we really want but it is necessary to give the Delivery Service some ordering information (unpredictable or not is an interesting question) to handle concurrent handshake messages which is, I believe, the main current goal of that information.

Benjamin