Re: [MLS] Unpredictable epochs?

Richard Barnes <rlb@ipv.sx> Thu, 02 January 2020 20:39 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 27AFE120103 for <mls@ietfa.amsl.com>; Thu, 2 Jan 2020 12:39:13 -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 pfIToVGJFngm for <mls@ietfa.amsl.com>; Thu, 2 Jan 2020 12:39:11 -0800 (PST)
Received: from mail-qk1-x736.google.com (mail-qk1-x736.google.com [IPv6:2607:f8b0:4864:20::736]) (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 1D7221200FA for <mls@ietf.org>; Thu, 2 Jan 2020 12:39:11 -0800 (PST)
Received: by mail-qk1-x736.google.com with SMTP id z76so32642584qka.2 for <mls@ietf.org>; Thu, 02 Jan 2020 12:39:11 -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=MPc3o5DgmtnCQMaUu6A0rWLfpErutk7ioykzg6PwRno=; b=pd10EIp33Hl1HrRSLON9Ih/dBh8D8BgLxiYO/GgC4qvkOPHZOZbHDhm4gfiCIYvf1n 1IYQa4emjRZkBI0UK3YNfdMR49ZwpaVSWcwR0rsRYeEsrs7ZAfgPNxyVpNIVEDWyPQp+ iTAgYKQhEP/LGQ9eLqZSV+fHFlG5BykCwX0vkvNhlC4hsHLKQvOTUxo+14IyF9dMPneq LeCQZddm52LtXf+Q/e/opn5W0ZxJFpuYDDp/RpEz+yqZ0Z7s3ZRL2/yFRz7+SAEOYtMc zfZoYtTAaqB3MlFCps9OL/oXNGe4xXwD7iJJEFnxGpFPnAUtY2W0vzYDqGHgHH9SnLnv Qjxg==
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=MPc3o5DgmtnCQMaUu6A0rWLfpErutk7ioykzg6PwRno=; b=puuf6hVh/cUonoVk15rxhgzjhoG0cepBRb49VmX6LNd6qOpDTYwggMjsynm+PwNPQh 0zgT68+1nzKtuEbwtWAllUjcaQP710q1mHPJCxV7CtQ2bJm61mLJrIjelWjQP60V9AIe +lCt/F8cQ1mcXnSXjjuvtkjZTetOu06d3/HVlm5nYlDRhbOezmDBYh0za/zYDH7uQRIs XKLegwZ1f1ooVs0oYh64PicYq2lkPaz9wHhvgzUybqv1nuVNKv1cijzdZD0I3UdenM/W 65V0+CBPgwSUF8GHqRW3W1jsPxxisMPu2fBu/4OdhRM+qkYyGaMQKsl1g7NcYkS0Wuer 1HMg==
X-Gm-Message-State: APjAAAUR2irFLXC+Hm6Tgl6vrbIXOe/SRBvXWrlLkIQtLfrYwf4g/c2Q B15Crncg5JWIBBAj3njfZyJZaPqRHyJtOg1IDR71ZQ==
X-Google-Smtp-Source: APXvYqycVXGk1MQtAM1aHZVkb3OvQ4pq1EVzvrjeYjGtgQx6JehuYVXKOV9JrPufpDW78+D3YOR3vDZXbUxwq2LYcEQ=
X-Received: by 2002:a05:620a:102e:: with SMTP id a14mr65974833qkk.159.1577997550071; Thu, 02 Jan 2020 12:39:10 -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>
In-Reply-To: <80ABB08C-AEE6-4E94-A972-4983E12241B6@inria.fr>
From: Richard Barnes <rlb@ipv.sx>
Date: Thu, 2 Jan 2020 15:38:53 -0500
Message-ID: <CAL02cgQjp5+C1eYztrqNW2xO+4RLjp5TER0NAe04jti5hgg2yA@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="0000000000006dc22a059b2e2fd8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/aAMAp1dFUMHCSGCg99yHyLcC7xQ>
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:39:13 -0000

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?





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
>