Re: [MLS] Proposals for handling concurrent messages

Richard Barnes <rlb@ipv.sx> Wed, 20 March 2019 15:23 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 4003612786D for <mls@ietfa.amsl.com>; Wed, 20 Mar 2019 08:23:36 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001] 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 s5l06Ca5px2P for <mls@ietfa.amsl.com>; Wed, 20 Mar 2019 08:23:32 -0700 (PDT)
Received: from mail-oi1-x22a.google.com (mail-oi1-x22a.google.com [IPv6:2607:f8b0:4864:20::22a]) (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 49A22129532 for <mls@ietf.org>; Wed, 20 Mar 2019 08:23:32 -0700 (PDT)
Received: by mail-oi1-x22a.google.com with SMTP id t206so2115280oib.3 for <mls@ietf.org>; Wed, 20 Mar 2019 08:23:32 -0700 (PDT)
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=VtdTTcWTc65BLeXKo3CBtgwsFut+Df2M7vksAGjj0QQ=; b=M3X1SuC1fgFpTJoDDyXXcrLR8/3WETpIbzeLxF7wa2L7H0KIclfsgghnNU8nVP0nqK 26q5UnC4MBLG+Y4mvMM3yDuUjpx8Ax9+WRVdDKzGAWkTZbD58zfYC3Xw5BlrxbyC0SrL C/nFHdo/5pALvqEla1WPjZaY8Sv2a4VbtowAOCUcnSeXU2OFNHxUz3ig/3XbC2x57nbU r5Hf713W7gBZnZaRCoyjNyFhKKLvVCcIo1OQ/bkyRYAzoE8yFSYhvMghWVTnpl0dvEZS f6r4Lgv65oXFVLLYxzkBBgiPS2e5bm9PRej3BynBkKIQ6ytzYJou1UDA0MRsNRITzuaY 1fiw==
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=VtdTTcWTc65BLeXKo3CBtgwsFut+Df2M7vksAGjj0QQ=; b=FQ+m4o7e5jTNb9SYVXELL3INQLJH79YWT9QUZ6Y3rAlWGRx3fny4k7rdBJGnhWYUQM uDOa2z5eoJEdNe5FU29grUbw+5FhfemuhZ2QdejXaocFUrd6SmHbQQO5WFdeIKmYpRup GvlYOQvqtN9eE6kf7zF5n/zseJ6WHLQDBYES8paCT66ND69XVB3+3hUF8TsfHDqjS12S hpTrwL1qV4ohYD+gpE8En8YxO4uWZAf8y/ReW874PsNqj34CrdU46GYp4ce9D47MHKp1 MiD+nV/fCFnnp0Np4UJob3Hknz30xTPrYwT/KX1MlgJj/HbyGdvtMb9+ZzKstlwuurJ2 Nysg==
X-Gm-Message-State: APjAAAXl4x/OMhUp4TvOo5Id4jftc6g1KTjo18KhHTg0OBVn7OybSajB irGdTYTt1m6j4MERzKL7HruLM+yHoJ+IQg9pZWrVDw==
X-Google-Smtp-Source: APXvYqzqpJDTSsZeu1d+st4+Z64erbzFppSljmHKenx5kyhUsYDF95syhFL1wjWzkvNzIuwVQYYm1hyK1Vgz1by+OBw=
X-Received: by 2002:aca:4812:: with SMTP id v18mr5191614oia.36.1553095411464; Wed, 20 Mar 2019 08:23:31 -0700 (PDT)
MIME-Version: 1.0
References: <CADSARUtSRJGW=z=9Spi=D87mOG34NCTswEcQMeeftv9x6gathQ@mail.gmail.com>
In-Reply-To: <CADSARUtSRJGW=z=9Spi=D87mOG34NCTswEcQMeeftv9x6gathQ@mail.gmail.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Wed, 20 Mar 2019 11:23:15 -0400
Message-ID: <CAL02cgQ-2gR9VK=_LthYO7fSGnDoaYei6dhuFjjdZQ7-aMSBaA@mail.gmail.com>
To: "M.A.L. Weidner" <malw2@cam.ac.uk>
Cc: "mls@ietf.org" <mls@ietf.org>
Content-Type: multipart/related; boundary="0000000000004df12d0584883483"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/t-A-q6PxH6XdUxtZQBMfFbQGt3g>
Subject: Re: [MLS] Proposals for handling concurrent messages
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: Wed, 20 Mar 2019 15:23:36 -0000

Hi Matthew,

Thanks for thinking about this.  The idea has come up a few times, but it's
good to have such a thorough presentation to refer to.

I think this idea works fine if the DH / KEM group in question has a
homomorphism of the character you describe.  There's a practical problem in
that that is not universally true.  In particular, X25519 and X448 do not
have such a homomorphism: Because of the "clamping" behavior prescribed in
the RFC, it is the case that pk(a + b) != pk(a) + pk(b).  There was some
discussion on the CFRG list (after I tried to implement such a scheme):

https://mailarchive.ietf.org/arch/msg/cfrg/JVg30dldjr4pcwZ1perpA1k-OGQ

That said, if this approach were important to people, it could probably be
realized for curves that allow a homomorphism.  That would rule out
X25519/X448, but I'm told that the Ristretto adaptation of those curves
would work.  See Tony Arcieri's message on the above thread and:

https://ristretto.group/
https://tools.ietf.org/html/draft-hdevalence-cfrg-ristretto-00

And in any case, I think good old traditional Weierstrass ECDH has this
property (e.g., using the NIST curves).

I would be interested to hear folks' thoughts on whether the benefits of
reduced synchronization would be worth the costs of limiting DH group
selection (either old ECDH or new stuff without a lot of implementation).

Cheers,
--Richard

On Tue, Mar 19, 2019 at 6:33 PM M.A.L. Weidner <malw2@cam.ac.uk> wrote:

> Dear MLS Working Group,
>
> I've attached a document that details some proposals for how to better
> handle concurrent messages; see mainly Section 2.
>
> The basic idea is to use some operator * which "combines" key pairs.
> E.g., for Diffie-Hellman keys, (x, g^x) * (y, g^y) = (x + y (mod |g|), g^x
> g^y).
>
> With this operator, we can combine concurrent updates.  E.g., if a updates
> with x and b updates with y, then the tree changes by: (embedded image)
> [image: causal_fig2.png]
> With some extra effort, I believe we can even support concurrent Adds
> (Section 3.3).
>
> My apologies if there are mistakes or if this has been discussed before.
>
> Best,
> Matthew Weidner
> MPhil Student
> Computer Laboratory, Cambridge
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls
>