Re: [MLS] Unpredictable epochs?

Richard Barnes <rlb@ipv.sx> Thu, 02 January 2020 20:52 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 4EA2712013F for <mls@ietfa.amsl.com>; Thu, 2 Jan 2020 12:52:42 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Level:
X-Spam-Status: No, score=-1.896 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, URIBL_BLOCKED=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 Y2_FsaGT_aDK for <mls@ietfa.amsl.com>; Thu, 2 Jan 2020 12:52:40 -0800 (PST)
Received: from mail-qt1-x82c.google.com (mail-qt1-x82c.google.com [IPv6:2607:f8b0:4864:20::82c]) (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 D5CBC12004D for <mls@ietf.org>; Thu, 2 Jan 2020 12:52:39 -0800 (PST)
Received: by mail-qt1-x82c.google.com with SMTP id t3so35501558qtr.11 for <mls@ietf.org>; Thu, 02 Jan 2020 12:52: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=HbqJDpCrgh62jGuVK2ThdRv/qL3SX7PYhUQcFJpL514=; b=TGhoKFOw6EUpiQqf26e5upNdU3mRnAQoA6juajvQ2T8fuewOXJV2Phsp9UZ5QsPvzp xLXSOgAWqR6w2T3Bm5uwjSGKhAboOdxWq8whidttsidTNIGtUrrCkvwFwV+w3b9gLuXp q3TIJDjlLAuJqdvBWAp5Fz8H38oux2xdCb0VJCzIfLACBPFXG2/UJW5xlgTMO0Y/xkI9 QJaTf1xVzxkzPal1N2J/c0NAYjJ0YNRqqacwAitbAsYhQne0NUbyZdIqRh3SNpmTfjsK dop4hL0l/nG4UoEiGCtuDvgrYgfWTHP6imG+kqOHnkaAfl2dUj2aF83kidZJiwBQGrzU E2Dg==
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=HbqJDpCrgh62jGuVK2ThdRv/qL3SX7PYhUQcFJpL514=; b=Q9x7kFLi7kziAYq4wdxCSAa2myxISroU9yf413xaDk2QZl5GZ2ft691S1xiYKLi1Rr J5+C0w9lz7pL3cKw6nS3pY4G4yJ7j6/rkI4noL2HUZfpA1t/PkIygjQlENnx4q/rlc+e ZJwnS24rqR4O9T5q81Ov0070bHHZFbnmEwtfvHSXmaRBonQs5OxyPx+XXREw8SOyXVmE FNbESaP7qw+iC1TQlUCZR3yF9Do+wy8Z0NnpR40+ULxviiP1E6ZkXTxEGCXYgcQz30Xy JFoBj0a6KTbMoMsrO/jSnhYtkZcCM3u1NWMJegSHGFqFo9WQKYBJp6YbXC5jjWTV9HoT yuVw==
X-Gm-Message-State: APjAAAWN6rMQoXC6caVo92MkBvVPTtZr2ipwOdq2vm4D0/CU9W3CwISV raF1d/TIeIfoCUgIojni8CYNUXJyDu9Mu5lWUzFN/Q==
X-Google-Smtp-Source: APXvYqzQbO7Uch9RnX3Ho351OpsNSS5JOhLrr3qNeoI4adnhnZInKiW0q3NVQBZ7uZrrrqKUKcTqkkCePbO8IIITW+0=
X-Received: by 2002:ac8:b43:: with SMTP id m3mr60611412qti.191.1577998358957; Thu, 02 Jan 2020 12:52: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>
In-Reply-To: <CAL02cgQjp5+C1eYztrqNW2xO+4RLjp5TER0NAe04jti5hgg2yA@mail.gmail.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Thu, 2 Jan 2020 15:52:22 -0500
Message-ID: <CAL02cgSr07Kd9RR76Eb=oFLr_eBZ97LkpboOXV3ky4oBL6N5zA@mail.gmail.com>
To: Benjamin Beurdouche <benjamin.beurdouche@inria.fr>
Cc: Jon Callas <jon@callas.org>, Michael Rosenberg <micro@fastmail.com>, Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000a45ca8059b2e5f45"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/T3puLcz8Sl7qufLbYWr06EU1NN4>
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: Thu, 02 Jan 2020 20:52:42 -0000

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