Re: [MLS] Proposals for handling concurrent messages

"M.A.L. Weidner" <> Wed, 27 March 2019 11:16 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 4AA0D1202AC for <>; Wed, 27 Mar 2019 04:16:14 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Status: No, score=-1.901 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, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id h-curv-z3FXU for <>; Wed, 27 Mar 2019 04:16:11 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id B16E81202BE for <>; Wed, 27 Mar 2019 04:16:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=selector1-cam-ac-uk; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=8g372YAKTRbmsXcDUvQ4TlKFY/mftHanC8VVQheKiUc=; b=egBffeGedIeohSbyDtswt5ftlKC2hx+kbl/rbccuokMwvXDxilKISwqvjOSFJ1jD3JcbIOObVtB4uyDpjAxQ14GMsC5uxv6S08f04CZlD2Wez51xeuh+7qrQNaUFtI8SxZcpGkScKK5nYZv2hCFTODv/8p2VMktdWCXIKNq4UUk=
Received: from ( by ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1750.14; Wed, 27 Mar 2019 11:16:08 +0000
Received: from ([fe80::6814:77d6:db25:b321]) by ([fe80::6814:77d6:db25:b321%11]) with mapi id 15.20.1750.010; Wed, 27 Mar 2019 11:16:08 +0000
From: "M.A.L. Weidner" <>
To: "" <>
Thread-Topic: [MLS] Proposals for handling concurrent messages
Thread-Index: AQHU3qO7vFsPft27yE62tRLT8TpCKw==
Date: Wed, 27 Mar 2019 11:16:07 +0000
Message-ID: <>
References: <> <> <> <> <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
x-clientproxiedby: (2603:10a6:20b:14::40) To (2603:10a6:4:24::14)
authentication-results: spf=none (sender IP is );
x-ms-exchange-messagesentrepresentingtype: 1
x-gm-message-state: APjAAAWoL7SkRrpUtY6bbq/AJXrmeuAtTtSE+y4CcnDh/mpFc69lWZoL mP60ZpdSaHD5RoFKGZ3d+Ze9BIZ5qvt5idR010o=
x-google-smtp-source: APXvYqwzXLugCyL8y7f3gNpedEJW0W8v69OTmrPG8Noxc3zrTuxhiduQufnhTerDt/vuj6Uan3UNOtlnuuNKmaOFyTE=
x-received: by 2002:a5d:5343:: with SMTP id t3mr23831676wrv.49.1553685366046; Wed, 27 Mar 2019 04:16:06 -0700 (PDT)
x-gmail-original-message-id: <>
x-originating-ip: []
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 1e0a826a-92c1-45d5-76be-08d6b2a59bab
x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600127)(711020)(4605104)(2017052603328)(7153060)(7193020); SRVR:DB6PR0701MB2597;
x-ms-traffictypediagnostic: DB6PR0701MB2597:
x-microsoft-antispam-prvs: <>
x-forefront-prvs: 0989A7979C
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(346002)(136003)(39860400002)(366004)(396003)(376002)(189003)(199004)(498394004)(76176011)(5640700003)(9686003)(54896002)(478600001)(53936002)(54206008)(11346002)(6512007)(71190400001)(2501003)(106356001)(14444005)(61726006)(74482002)(561944003)(105586002)(6506007)(68736007)(55446002)(386003)(71200400001)(256004)(446003)(2351001)(95326003)(6246003)(93886005)(52116002)(476003)(14454004)(5660300002)(786003)(316002)(7736002)(486006)(66066001)(86362001)(6916009)(15650500001)(26005)(3846002)(6436002)(6486002)(6116002)(8936002)(8676002)(186003)(97736004)(305945005)(102836004)(99286004)(61266001)(25786009)(2906002)(229853002)(81156014)(1730700003)(81166006); DIR:OUT; SFP:1102; SCL:1; SRVR:DB6PR0701MB2597;; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1;
received-spf: None ( does not designate permitted sender hosts)
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam-message-info: jap+se0kVlvOOdB9G1yAB5YtoNRFu+z+QuqlD2m028rFWag11rS0D3vTiDuj7Q8E4k+OCKq4BS1OpxjOY3xqCN9n2ONctmDVjp2SvnaFy6a7B//j7xOZkVZSWMj1Qy+lj3eQD7uOEnCRCGmepPwqS8l3UlAtpPmncgsdRCy9IIDpdrAT3LQkA19CRWufTUohT6wMMumujZ00CLUGIg0wXDvu3+YbAFNytN/mBrJ6785QUB/yh54jo2TaSiTZo7QMuU2Iz0Z0UWY0Hs/A1BIoBOdIquYLToVv9asm0gjM2nLzc+aHRrD6xlXR6nYsBseEwwvy90Hznpl21+ABDbbMrENiWrcFokMX2Bx5bXkXeqZoNek9VgLpGRI2U2rcRVUcoseMt1Q0djJSht826veVZRrs5gRCVG8XOR01U3IS79c=
Content-Type: multipart/alternative; boundary="_000_CADSARUtsivWuOcFfMHLDhgpR3caXO87pCdQuaBOpwWjzSC6xxAmail_"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: 1e0a826a-92c1-45d5-76be-08d6b2a59bab
X-MS-Exchange-CrossTenant-originalarrivaltime: 27 Mar 2019 11:16:07.8884 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 49a50445-bdfa-4b79-ade3-547b4f3986e9
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB6PR0701MB2597
Archived-At: <>
Subject: Re: [MLS] Proposals for handling concurrent messages
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 27 Mar 2019 11:16:14 -0000

From the above discussion, it appears there are a few ideas for how to handle concurrent updates.  Here is my attempt at a summary.

The scenario is that we are sending an update message, and as part of this, we need to send a secret to a node on our copath; this node has k distinct "candidate" public keys, coming from >= k concurrent updates.  Our options are:

1. (Vanilla TreeKEM) Choose one of the candidates arbitrarily and send the secret encrypted under that.
- Cost (compared to an ordinary sequential update): none.
- PCS guarantee (of the secret we send): healed against compromise of the user who contributed the chosen public key.

2. (similar to Causal TreeKEM) "Combine" all of the candidate public keys and send the secret encrypted under that, so that only someone with all of their private keys can decrypt the secret.
- Cost: need to use a cryptosystem that supports key combining (e.g., Ristretto curves).
- PCS guarantee: healed against compromise of any *one* user who contributed a public key.

3. (Vanilla TreeKEM, multiple keys) Encrypt the secret under each of the candidate public keys in sequence, so that only someone with all of their private keys can decrypt the secret.  (I think this is what Jeff was suggesting - correct me if I'm wrong.)
- Cost: k encryptions for me, k decryptions for recipients (instead of 1 in the ordinary case).
- PCS guarantee: healed against compromise of any *one* user who contributed a public key.

4. (Blank out conflicts) Replace conflicted nodes with blanks (including the node we are sending to, and any conflicted children).  Thus we send the secret separately for each of the k candidates, using public keys deep enough in the tree that none of the contributors' old states can decrypt the secret.  In the extreme case where the k public key contributors are the only descendants of the conflicted node, this means we send the secret separately to each contributor.
- Cost: k encryptions for me, k times as much bandwidth.
- PCS guarantee: healed against compromise of any subset of the users who contributed public keys.

Another consideration is how to encrypt ordinary (e.g. chat) messages after concurrent updates lead to multiple choices for the root key.  We get the same guarantee as option 2 if we combine each concurrent updates' contribution into the root key, as in the original TreeKEM proposal or in Causal TreeKEM.  (This can be done using any KDF, since the root key is just a shared secret, not an asymmetric key pair.)  Getting the strong guarantee in option 4 seems harder.  We could adopt a rule that after concurrent updates, users must first send an update before sending ordinary messages, but that could lead to repeated rounds of concurrent updates.

Matthew Weidner