Re: [MLS] MLS in decentralised environments

Martin Thomson <martin.thomson@gmail.com> Wed, 04 April 2018 02:23 UTC

Return-Path: <martin.thomson@gmail.com>
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 C32F0127863 for <mls@ietfa.amsl.com>; Tue, 3 Apr 2018 19:23:23 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.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 EpI5ugxks36V for <mls@ietfa.amsl.com>; Tue, 3 Apr 2018 19:23:21 -0700 (PDT)
Received: from mail-ot0-x235.google.com (mail-ot0-x235.google.com [IPv6:2607:f8b0:4003:c0f::235]) (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 60EE91243FE for <mls@ietf.org>; Tue, 3 Apr 2018 19:23:21 -0700 (PDT)
Received: by mail-ot0-x235.google.com with SMTP id n40-v6so21679617otd.3 for <mls@ietf.org>; Tue, 03 Apr 2018 19:23:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=0UeSKb8laz92kyHpuIqy5QJMjtVNrccndCu8lW8ghZ0=; b=ma8RVT7qjIDCxSrPxtZTsTZvf/nglJsSUuyTMNl2up7krxAqYvnshPo64EHNI1+Ro+ y27A1h2sCVrYKr8YL4ZfuzbgA24cFdKWUb0s2+118YY4jNThdSPhZF8DKsGrqevf2F5x ND7hrEk5Km8k4HLIK0sO4zHsG9emtKQ5tCnUqjzaxKLajYLp+Gq+0vBGO58v4J/8cyjE EkTZUjcT0o/cfu+sF8VDG6yNOoHnRv8jhGe7o+CurtDn/78igsz30sCLe3cb7RD2ffUk SRHyYUZwghYmG1SEEwFwFQtv0LzeHCeD8dDz6sA+E2xBikH+aUI/FIaUGv0BXNzqoqvF 7Trw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=0UeSKb8laz92kyHpuIqy5QJMjtVNrccndCu8lW8ghZ0=; b=XbWgjaEdRVhlopLR1KzNB157tR5oZT5NoJ+LGdrxQgNlOQ5qL2kfxCroCr2J22Pinl FKRnf6zkFDAt5I5vTkOq0sTVPNIj9tArDcaHftjy/e7JTcP0FUyFSVo9n3TPK1U1HpFl 3Pi8wZp6nbrdWUTqn/RehSzaEoJr5wKeaKeLl/W5Ig9CMike9hP/Nnpp/HIotUrH9Le2 s5IT4WUfpdO9UC9bYfaxwznQL7mLADbhLDePBJhrj0QZbkBlTKLxM0fuhE1EawqlyelN XcU04vdfqtjVotZddmYOBdcVUcofzXGthUR7ALXZApZDgg7kD26Bc9KqqhvIBZmH948q xo0w==
X-Gm-Message-State: ALQs6tC4Gr0ITpyzJjGOPGRLJuzqHdCFJTrOwD7O3qefFWPkYFWU8AGL qnVRJRmFpU1UJVGzdl9HGCyGB/ar52lxj0ppT+Gk8Q==
X-Google-Smtp-Source: AIpwx4/Fo86+eu/6NXp4GbmAjSxBCfGViooKoDEVDETj5K8hpGafGqk3yCQGgup9fjp4dJvBSi//W4GIRWjkqt8KE40=
X-Received: by 2002:a9d:4541:: with SMTP id p1-v6mr10068938oti.15.1522808600433; Tue, 03 Apr 2018 19:23:20 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a9d:ac7:0:0:0:0:0 with HTTP; Tue, 3 Apr 2018 19:23:19 -0700 (PDT)
In-Reply-To: <1522752111.78362.1324712112.35AEA1A1@webmail.messagingengine.com>
References: <6745e49d-9826-ac74-03b6-e6adbde7e805@matrix.org> <1522752111.78362.1324712112.35AEA1A1@webmail.messagingengine.com>
From: Martin Thomson <martin.thomson@gmail.com>
Date: Wed, 4 Apr 2018 12:23:19 +1000
Message-ID: <CABkgnnVM9HyGxK9=e5byLgTLGBvL1K6TTeO87TLSF17+1vJkig@mail.gmail.com>
To: Katriel Cohn-Gordon <me@katriel.co.uk>
Cc: mls@ietf.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/zLJkd9AnEzXOcwMS1FnyPN2rG2c>
Subject: Re: [MLS] MLS in decentralised environments
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.22
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: Wed, 04 Apr 2018 02:23:24 -0000

Is it possible to have a common tie-breaker process and force the
loser to rebase?

That is, if the change c->c' wins, then d needs to apply their d->d'
change again on top of that change (or move to d'').

A simple tie breaker process would inform all participants of the head
of both forks and to pick a winner based on the one that gets the
largest result from H(root).  That's open to participants choosing
keys to influence the result, so you probably don't want that precise
design (esp. if forks include removals), but hopefully the idea makes
sense.

The next problem would be that repair of a fork can be expensive.  If
there are multiple changes on the losing fork, then all those changes
might also compete as the updates propagate.

On Tue, Apr 3, 2018 at 8:41 PM, Katriel Cohn-Gordon <me@katriel.co.uk> wrote:
> Hi Matthew,
>
> Thanks for thinking about this. I agree that it's a problem I think exists
> even in the centralised world, since it's much nicer to build a system that
> doesn't have to provide strict sequencing guarantees.
>
> # The problem
>
> I'll sketch out the underlying problem first, even though I think you
> spotted it pretty well, just to make sure we're on the same page. The
> problem is from the ratcheting tree construction: two updates which both
> want to change a particular intermediate node cannot both be applied at the
> same time. Let me try out some ASCII art: consider a simple tree like
>
> root
> ├── x
> │   ├── a
> │   └── b
> └── y
>     ├── c
>     └── d
>
> and suppose c wants to update to c', giving the following tree and
> publishing g^i(y') where y'=g^c'd
>
> root
> ├── x
> │   ├── a
> │   └── b
> └── y'
>     ├── c'
>     └── d
>
> while d also wants to update to d', giving the following tree and publishing
> g^i(y'') where y''=g^cd'
>
> root
> ├── x
> │   ├── a
> │   └── b
> └── y''
>     ├── c
>     └── d'
>
> These can't both be applied by A: A can either set their view of the last
> node on their copath to be y' or y'', but not both of them. Moreover, A has
> no way of "combining" the two updates.
>
> # Not the problem
>
> One thing I should highlight up front is that this does not necessarily
> prevent decrypting messages, only applying key updates. Specifically, if A
> receives either C's or D's update they can apply it and compute the
> resulting root key, then decrypt the message. Of course, if the update is
> one that should have bounced, then they might have to "un-apply" it.
> Moreover, if A wants to send their own update, they need to pick one of y'
> and y'' to base it on. This is something I don't think we've reasoned about
> in detail yet.
>
> For other reasons due to malicious group members, I think we're likely to
> come up with a system where each participant has various "proposed" updates
> sitting around, and then only confirms them after receiving some other
> message. This sort of algorithm should also help here, because I think it
> will also need the ability to unwind or not apply a potential update.
>
> # Things we tried that don't yet work
>
> One thing we thought about was using some tricks with Diffie-Hellman to
> allow both updates to be processed at the same time. Unfortunately we
> couldn't actually come up with a system that works (using a KDF to turn
> group elements back into integers hurts here), but there might well be one.
>
> Another thing is the observation that in fact it is sometimes possible to
> apply two updates at once: specifically, if two updates change different
> copath elements with respect to a recipient, then that recipient can apply
> both of them. Unfortunately this only helps some recipients, not all of
> them, so it doesn't really solve the whole problem.
>
> Another thing is having the server do some clever re-ordering. The challenge
> is that in the end, by construction the correct value of the intermediate
> node should only be computable by its children, so there's only so much the
> server can do.
>
> For the same reason, I'm not sure the server can unilaterally rebalance the
> tree; I think it would need some help from one of the participants. I'd have
> to think more carefully about the precise keys which it would need to do so,
> though. In particular, if you are more worried about re-ordering join events
> than re-ordering key updates, there might be some specialised tricks that
> work.
>
> # Question about the Matrix context
>
> In the Matrix setup, do nodes actually know when there is consensus on a
> particular set of messages? That is, is there some point at which they can
> conclude "ok, I know that the following messages are actually the right
> ones, and haven't been pre-empted or undone by successors"? (If so then I
> think the "multiple proposed updates" ideas will help here too.)
>
>
>
>
> does that make sense? :)
>
> best,
> K
>
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls
>