Re: [MLS] Unpredictable epochs?

Richard Barnes <rlb@ipv.sx> Fri, 03 January 2020 16:55 UTC

Return-Path: <rlb@ipv.sx>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D006D1200DE for <mls@ietfa.amsl.com>; Fri, 3 Jan 2020 08:55:42 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Level:
X-Spam-Status: No, score=-1.897 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=ipv-sx.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id CS16P7quYKv1 for <mls@ietfa.amsl.com>; Fri, 3 Jan 2020 08:55:39 -0800 (PST)
Received: from mail-qt1-x831.google.com (mail-qt1-x831.google.com [IPv6:2607:f8b0:4864:20::831]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6680C120091 for <mls@ietf.org>; Fri, 3 Jan 2020 08:55:39 -0800 (PST)
Received: by mail-qt1-x831.google.com with SMTP id d18so34578632qtj.10 for <mls@ietf.org>; Fri, 03 Jan 2020 08:55:39 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=c/4I4qO/Z813fL3KErDp7bYME9KlGvjDeTN43qpqLtc=; b=f4EsCMOcSDQV/I43e5NcfyfTgTz1PWCjkCOBZFihn8aKvFk5xb8aCtgeDzZ362tpam VLQFQKugD5O9JxB6n1wyqTiYfHBZx/zS/A4ShTzChnv0Wp8KIh3sHUOVXcWMd4FHRd/S MtgB98NH5jtrlS4tGecIxbxvfetqPCHol2ai3kjUhrc85hs9Bs7yquGlTF6Svmf1u8Vq R0ZlD9PvzrrTI1WbWofdsQYmYBQeJK3TBBcRBqrADhHs9L6sRkHKti1VcyrOv7LNclb1 2w1y+2L3EnJne53SpSolrAyjeES0ANzwoj+QV1f/tLw9E3cOB1fR/35W/Y0gEj0QmkJ3 i76A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=c/4I4qO/Z813fL3KErDp7bYME9KlGvjDeTN43qpqLtc=; b=INkFwwWTRT721PT7SFE/o3S7qupShy5K1T7h6+lkIg0vk3FpQFYQcKfmn71y3XMHr/ rdiuxmNIz9A03EkvwJafK9WnBUMcH0hKltSQtMRmE13bDisTCGkhpKCzAqR+o2KDXVH1 c1BYdm6YJmCTPqKbrazwQve799j7UdleDJdlhZwSTb75hWtRPkbgDzz5xnYEd0PKcsrM Jh3gyhnFIAnP3cY8K56asdFszOgV21kQFTk9SLdvAQ89H0S6YzXeQCyzFOiwBYhlUQ4d bF+nmQIqNqK/XFHgzPQhMtAbxZxPOcASyKav68f2+TNen/DIiPtiKhxFJs0Olc9qMRUn YJMw==
X-Gm-Message-State: APjAAAXuT4mQrcUg0hEcOfMfyy4XRxEZdoqcISFIvmqzSkoYt+IJxzTb bzbm9RoSRfd+ICMRdfERMLOsVj7uXl4brip5RVO9Fg==
X-Google-Smtp-Source: APXvYqwflmWwF7qJau2ftai+DEEOX+xfY40SjqzLRvfLOD1g5ibcsbagNl2frMqeJ0NcDp19Bxn6qw46wZiB7QPRqM8=
X-Received: by 2002:ac8:1e90:: with SMTP id c16mr64804489qtm.265.1578070538489; Fri, 03 Jan 2020 08:55:38 -0800 (PST)
MIME-Version: 1.0
References: <CAL02cgSE1xTF2Wsq-u=BCu2Z_4UzMzqMPi=D_H7_7hbRpUMVVA@mail.gmail.com> <2D195D14-9F9A-4D64-92EF-35C601C52C01@inria.fr> <CAL02cgR8gQ6cH_QXd_9v46aJ5aeo=b=1GiYu9YxCNYzJb0tOFQ@mail.gmail.com> <B36BF8F5-EAE9-4C96-A867-82CDFBF830C0@inria.fr> <CAL02cgQ7-JMQsG6sq6YBB3G-5tmCVQoo07nvW63tzBzHPQ0ZWw@mail.gmail.com> <AC74CACD-541B-49CD-9CC9-63343307A53D@fastmail.com> <CEAEFC1B-7581-4263-A45D-44E7348D7DB7@callas.org> <80ABB08C-AEE6-4E94-A972-4983E12241B6@inria.fr> <CAL02cgQjp5+C1eYztrqNW2xO+4RLjp5TER0NAe04jti5hgg2yA@mail.gmail.com> <CAL02cgSr07Kd9RR76Eb=oFLr_eBZ97LkpboOXV3ky4oBL6N5zA@mail.gmail.com> <CAOdM_7kJsmp-ViEjdQJUE2rxRExJmM9ODEvs77Xjh3AQrpckKw@mail.gmail.com> <4E8A7725-EBC6-4BD4-8D3A-5C52D4712D39@wire.com>
In-Reply-To: <4E8A7725-EBC6-4BD4-8D3A-5C52D4712D39@wire.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Fri, 3 Jan 2020 11:55:21 -0500
Message-ID: <CAL02cgQ9jOGeKqO1=7OcwQ2FMagODK-un6B0+mjm+RUH3xig+g@mail.gmail.com>
To: Raphael Robert <raphael@wire.com>
Cc: Kelvin Ritland <kelvinr=40google.com@dmarc.ietf.org>, Michael Rosenberg <micro@fastmail.com>, Messaging Layer Security WG <mls@ietf.org>, Benjamin Beurdouche <benjamin.beurdouche@inria.fr>, Jon Callas <jon@callas.org>
Content-Type: multipart/alternative; boundary="000000000000e0a98c059b3f2dce"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/c-Kq5DOmrsnrizg8NvqNdCnE1xI>
Subject: Re: [MLS] Unpredictable epochs?
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 03 Jan 2020 16:55:43 -0000

Yeah, I'm on the same page here. My objective is to remove the roadblock
without trying to solve the whole problem.  As Kelvin points out, there's a
lot of interesting thinking to be done about how to manage a DAG of state.

In chatting with Raphael just now, he proposed a nice framing -- that the
tiebreaker bits could be used for fork *detection*.   Even in the case
where the DS is trying to maintain order, there's a chance that things go
wrong.  The tiebreaker bits would ensure that people don't try to use the
wrong keys for a message in that case.

Here's a quick PR implementing the "extended epoch" proposal:
https://github.com/mlswg/mls-protocol/pull/281



On Fri, Jan 3, 2020 at 10:32 AM Raphael Robert <raphael@wire.com>; wrote:

> I agree with Kelvin’s points in general. Allowing forks might be an
> interesting goal, but it raises a wealth of new questions.
> On the other hand I think Richard’s proposal of extending the Epoch ID
> with a commit hash makes sense to detect potential forks.
>
> I’d like to propose that we adopt that as a first step, but only in the
> context of fork detection for now. This doesn’t preclude us from building
> on top of that in the future, but we also don’t introduce something
> dangerous right now.
>
> Raphael
>
> On 3 Jan 2020, at 00:15, Kelvin Ritland <
> kelvinr=40google.com@dmarc.ietf.org>; wrote:
>
> Not-pseudorandom implies some assumptions, e.g., that each sender would
>> only send one Commit on top of each epoch
>
> This isn't bad imo, it reduces complexity to some extent. I'm somewhat in
> favour of a non-pseudorandom tiebreaker if there's no other arguments
> against it.
>
> How many bits of sequence number?
>
> Have we considered using varints? Similar to the CTLS proposal -
> https://tools.ietf.org/id/draft-rescorla-tls-ctls-02.html#rfc.section.3.1
>
>
> Other forking considerations, I think there's more involved than just
> changing the epoch identifier:
>
> 1. We'll need merges as well, since forks can lead to inconsistent group
> membership:
> Suppose in epoch 1 a group has A, B, and C
> A removes C in epoch 2A
> B adds D in epoch 2B
>
> We now have two group states 2A with AB and 2B with ABCD - and it's
> unclear which group to use to send with. We could mandate that any client
> MUST send a "merge" commit on it's view of history before sending any
> message. This commit could just be the list of epochs that are being merged
> (+a usual DirectPath update?), and processing it would mean replaying all
> proposals up to the common ancestor for those epochs on the common ancestor.
>
> 2. Forward secrecy issues.
> By allowing forks, devices must now keep the previous epoch around to
> derive possible future forks - but this means we'll be re-using
> init_secret_. A possible solution could be to use the nth app secret from
> the ASTree instead of init_secret_ as the start for the new epoch secret.
> This ties nicely with using a non-pseudorandom tiebreaker.
>
> 3. Ordering implications
> It's unclear what a sensible ordering strategy is for the DS if we allow
> forking. (simply ensuring that each commit is based on the "current" epoch
> isn't well defined since there can be multiple "current" epochs).
>
> By allowing forks the DS need not enforce ordering at all imo. This means
> that apps need to keep around old epochs, but this is already required per
> (2). A different question is how many we need to keep around - perhaps a
> TTL or the past N epochs after a topological sort would make sense.
>
> Generally I think getting rid of server ordering is good idea:
> - Helps Matrix and general federation use cases
> - A common consistent mutated state for group operations can cause server
> side DB contention in my experience
>
> Forks is one way to remove ordering, and if we need to support it anyways
> it's a nice benefit.
>
> On Thu, Jan 2, 2020 at 12:52 PM Richard Barnes <rlb@ipv.sx>; wrote:
>
>> Argh, hit send too soon.  Continuing below...
>>
>> On Thu, Jan 2, 2020 at 3:38 PM Richard Barnes <rlb@ipv.sx>; wrote:
>>
>>> Hey all,
>>>
>>> Resurrecting this thread, as it seems that we never came to resolution
>>> on this question.
>>>
>>> I'd like to propose we scope down and solve a narrower problem, namely
>>> the problem of enabling forks in the group's history.  So we're not going
>>> to try to provide any privacy properties, just remove the impediment to
>>> forking.  This seems like a worthwhile thing to me just because it seems
>>> silly to have forking blocked just because of syntactic constraint, in
>>> addition to it likely being necessary for some decentralized use cases
>>> (e.g., Matrix).
>>>
>>> To allow forks, we really just need some "tie breaker" bits in the epoch
>>> ID so that if a given epoch has multiple successors, they end up with
>>> different epoch IDs.  And in order to avoid synchronization, each
>>> participant needs to be able to generate those bits independently.  There
>>> are a couple of basic questions about how to construct the tie breaker:
>>>
>>> 1. Pseudorandom or not?
>>>   - Not-pseudorandom example: tiebreaker = commitSenderID
>>>   - Pseudorandom example: tiebreaker = H(MLSPlaintext(Commit))
>>>   - Not-pseudorandom implies some assumptions, e.g., that each sender
>>> would only send one Commit on top of each epoch
>>>   - Pseudorandom risks random collisions
>>>   - Possible to do both: tiebreaker = commitSenderID ||
>>> H(MLSPlaintext(Commit))
>>>
>>> 2. How many bits of tiebreaker?
>>>
>>   - Non-pseudorandom size will be dictated by what we include
>>   - Pseudorandom size will be dictated by tolerable collision probability
>>   - Probability of collision ~ (number of forks per seq no) / 2^{number
>> of bits}
>>
>> 3. How many bits of sequence number?
>> - DS might want to see sequence to help enforce ordering
>> - Probably want this big enough to avoid wrapping.
>>
>> (Note that this is a value that goes in every message, so there's some
>> incentive to keep things small.)
>>
>> Personally, my proposal would be something like:
>>
>> struct {
>>   uint64 sequence_number;
>>   uint64 commit_hash; // H(MLSPlaintext(Commit))
>> } EpochID;
>>
>> That seems to strike a reasonable balance between low collision
>> probability (~2^-64) and a reasonably small identifier.  If 128 bits is
>> good enough for IPv6, it can be good enough for us :)
>>
>> Does that seem workable to folks?
>>
>> --Richard
>>
>>
>>
>>>
>>>
>>>
>>>
>>>
>>> On Fri, Apr 26, 2019 at 4:18 PM Benjamin Beurdouche <
>>> benjamin.beurdouche@inria..fr <benjamin.beurdouche@inria.fr>>; wrote:
>>>
>>>>
>>>> > On Apr 26, 2019, at 9:26 PM, Jon Callas <jon@callas.org>; wrote:
>>>> >
>>>> >> On Apr 26, 2019, at 2:22 AM, Michael Rosenberg <micro@fastmail.com>;
>>>> wrote:
>>>> >>
>>>> >> So why not remove epoch entirely?
>>>> >
>>>> > 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.
>>>>
>>>> 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
>>>>
>>> _______________________________________________
>> MLS mailing list
>> MLS@ietf.org
>> https://www.ietf.org/mailman/listinfo/mls
>>
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls
>
>
>