Re: [MLS] MLS in decentralised environments

Matthew Hodgson <matthew@matrix.org> Tue, 03 April 2018 21:59 UTC

Return-Path: <matthew@matrix.org>
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 3FF7112D882 for <mls@ietfa.amsl.com>; Tue, 3 Apr 2018 14:59:47 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.009
X-Spam-Level:
X-Spam-Status: No, score=-2.009 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=matrix.org
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 l7H-K-LkAoG4 for <mls@ietfa.amsl.com>; Tue, 3 Apr 2018 14:59:44 -0700 (PDT)
Received: from hermes.matrix.org (hermes.matrix.org [83.136.254.153]) (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 DCFEA126C2F for <mls@ietf.org>; Tue, 3 Apr 2018 14:59:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=matrix.org; s=hermes; h=Content-Type:In-Reply-To:MIME-Version:Date:Message-ID:From:References:To:Subject; bh=EzMwxITTfK2qKZRwWTQabHraOhH+FdOKT78PL4QTjDg=; b=ul8FRGD9UiSQ80oorf7n9aDCnE4jyxGJTdPuP9x1/n//bSZKOyBsGpHLNRAVVUnKLg/7YpgGFx/Vdr3O6rfPVyIuVYnCQ70INLiyQUgAkuRl/SRJMK29dNgBw0nZXzbsSbLoZt1Ik5p16INN48u/w+cU9lw8Ay2ZZahNGEY3BG7ucAE0CHBE47GR/4VFecdlUvPYJVfoe7bjA8pHeqUxzY8npgzK5ZOXGEJf+pd/6yJDMDFpWttQd97Qp8VNim930RIxKrFGhjhkRYWp8HlWcDJBGzLQ0mbHWuSSJfGwxe2PrQpexi1Q+h1cbV5Iq4RCzJrXtC4upXSB+d2QcIUsag==;
Received: from [91.110.5.109] (helo=sierra.local) by hermes.matrix.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.84_2) (envelope-from <matthew@matrix.org>) id 1f3Txu-0001fM-8S for mls@ietf.org; Tue, 03 Apr 2018 21:59:42 +0000
To: mls@ietf.org
References: <6745e49d-9826-ac74-03b6-e6adbde7e805@matrix.org> <1522752111.78362.1324712112.35AEA1A1@webmail.messagingengine.com>
From: Matthew Hodgson <matthew@matrix.org>
Organization: Matrix.org Foundation
Message-ID: <744b2740-e7fc-0d58-a6c2-1625ef84bb70@matrix.org>
Date: Tue, 3 Apr 2018 22:59:41 +0100
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:60.0) Gecko/20100101 Thunderbird/60.0
MIME-Version: 1.0
In-Reply-To: <1522752111.78362.1324712112.35AEA1A1@webmail.messagingengine.com>
Content-Type: multipart/alternative; boundary="------------C8E145A2A6778115BD509AA1"
Content-Language: en-GB
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/16UjU1uo4-ZSswINco0w4ZO254k>
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: Tue, 03 Apr 2018 21:59:47 -0000

On 03/04/2018 11:41, Katriel Cohn-Gordon wrote:
> # 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.

Thanks for the speedy & comprehensive answer (and sorry for being slow 
at grokking this in person at IETF!)

Yup, I think we're on the same page - the only difference is that I've 
been fixating on races between adding devices to the group (as that's 
the one which has historically bitten us badly on Matrix) versus races 
betwen key updates, which is I guess is the more common failure mode for 
MLS.

> # 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.

Aaaah, interesting. Does this mean that a 'many worlds' style approach 
can work here, where each client calculates the possible trees resulting 
in the state changes arriving in different orders, and tries to decrypt 
the messages using the tree which 'works' (thus avoiding the need for 
keysharing)?

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

Okay. Is this the same as the proposed v. committed update strategy 
mentioned at 
https://tools.ietf.org/html/draft-barnes-mls-protocol-00#section-9.2?

>
> # 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.

I wasn't thinking of the server rebalancing the tree, but instead there 
being some kind of mechanism that alerts clients to the fact that there 
is been a race (e.g. two messages arriving with the same logical 
timestamp), causing them to all go and rebalance their trees to ensure 
everyone is back on the same page (to the best of their knowledge) 
rather than trying to apply the update to the 'wrong' base.  It feels 
like i'm missing something about the practicality of doing this in terms 
of the actual DH exchanges though?

In a 'many world' model, I guess this would just mean selecting the 
correct tree from the possibilities being maintained, rather than having 
to rebalance the currently 'wrong' tree to make it 'correct', which 
seems a bit cleaner.

> # Question about the Matrix context
>
> In the Matrix setup, do nodes actually know when there is consensus on 
> a particular set of messages?

They do not. We don't currently have a consensus mechanism which seals 
the history - instead, it's perfectly valid for a netsplit to cause a 
room to go off on a long-lived evolutionary fork.

We have considered sealing history in the context of transcript 
consistency however, as having a canonical version of the room can 
obviously be useful to avoid situations where folks insert or reject 
messages in their local fork of the room in order to twist the 
conversation.  It could also be useful when changing the replication 
algorithm (atomically sealing the history of the room on the old 
protocol before switching over to the new).

However, we'd prefer to avoid forcing participants into committing to a 
'one true copy of the room' as it effectively introduces centralisation, 
as well breaking the whole long-lived fork use cases.  Instead it'd 
probably be nicer to commit to transcript consistency *for a given 
partition of the room*, which we effectively already have via the Merkle 
signing of the Matrix room DAG.

> 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.)

So I wonder if the "many worlds" or "multiple proposed updates" idea 
works even if your forks can be longlived - it's just that the proposals 
can drag on for a long time and are never necessarily fully committed 
to.  Is this actually a problem?  I think I'm missing the attacks which 
you are considering...

> does that make sense? :)

mostly, I think!

M


-- 
Matthew Hodgson
Matrix.org