[MLS] Concurrency in MLS: Lower and Upper Bound of Communication Overhead

Paul Rösler <paul.roesler@rub.de> Mon, 28 September 2020 09:59 UTC

Return-Path: <paul.roesler@rub.de>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 485A23A0B4A for <mls@ietfa.amsl.com>; Mon, 28 Sep 2020 02:59:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, URI_DOTEDU=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=rub.de
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id L_4z6-iObT_t for <mls@ietfa.amsl.com>; Mon, 28 Sep 2020 02:59:27 -0700 (PDT)
Received: from out1.mail.ruhr-uni-bochum.de (out1.mail.ruhr-uni-bochum.de []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BA1873A0B36 for <mls@ietf.org>; Mon, 28 Sep 2020 02:59:27 -0700 (PDT)
Received: from mx1.mail.ruhr-uni-bochum.de (localhost []) by out1.mail.ruhr-uni-bochum.de (Postfix mo-ext) with ESMTP id 4C0Hzw0rPFz8S7r for <mls@ietf.org>; Mon, 28 Sep 2020 11:59:24 +0200 (CEST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=rub.de; s=mail-2017; t=1601287164; bh=CTzpvX3evkaTfjv85hzFaTRUMJz6ObTpnxkPMdTyDbs=; h=To:From:Subject:Date:From; b=gRUnIka/E1c804igWDWuiWhAomcq/HwNpTjK2+DUaSWkl5wXSSz939aJO4evTGPHT VU4NEKMLSIvhVYYib/Glf65C36SfPVuL0pZj2HmQ5oiATzelvWE9aCo28my4p3gBFz WufKiGirbnRCL0m/tUA/Qo73y3jiZfIdzicHGbd0=
Received: from out1.mail.ruhr-uni-bochum.de (localhost []) by mx1.mail.ruhr-uni-bochum.de (Postfix idis) with ESMTP id 4C0Hzv6WFZz8S7m for <mls@ietf.org>; Mon, 28 Sep 2020 11:59:23 +0200 (CEST)
X-Envelope-Sender: <paul.roesler@rub.de>
X-RUB-Notes: Internal origin=IPv6:2a05:3e00:c:1001::8693:2aee
Received: from mail2.mail.ruhr-uni-bochum.de (mail2.mail.ruhr-uni-bochum.de [IPv6:2a05:3e00:c:1001::8693:2aee]) by out1.mail.ruhr-uni-bochum.de (Postfix mi-int) with ESMTP id 4C0Hzv3j1cz8S6p for <mls@ietf.org>; Mon, 28 Sep 2020 11:59:23 +0200 (CEST)
X-Virus-Status: Clean
X-Virus-Scanned: clamav-milter 0.102.2 at mx1.mail.ruhr-uni-bochum.de
Received: from [IPv6:2a05:3e00:9:2100:d54b:a3d6:cdfd:7a0b] (dyn-b0a7dfdc6d3ab45d00129000.nds.ipv6.ruhr-uni-bochum.de [IPv6:2a05:3e00:9:2100:d54b:a3d6:cdfd:7a0b]) by mail2.mail.ruhr-uni-bochum.de (Postfix) with ESMTPSA id 4C0Hzv1Q4jzDh0w for <mls@ietf.org>; Mon, 28 Sep 2020 11:59:23 +0200 (CEST)
X-Virus-Status: Clean
X-Virus-Scanned: clamav-milter 0.102.4 at mail2.mail.ruhr-uni-bochum.de
To: mls@ietf.org
From: =?UTF-8?Q?Paul_R=c3=b6sler?= <paul.roesler@rub.de>
Autocrypt: addr=paul.roesler@rub.de; prefer-encrypt=mutual; keydata= mQMuBFMPNo4RCACsEL23jO1k25wZhdphKuPdmEnxvjbtZavn1ZkALMxWJ4bYHPxNkpZWCT9h v0ZizDoosjlIvh0lK0nZgK0MLwjG/swrG/qUoZPIxStbXSVZPPwSdTaa+nzN0HD2y30zDExP 9WtchiEnGPB8WLCjkx5qscrBZV+PzI5akdK2CGBDthVvYzu4oLMZ89akJfM82ap9fGf0pfMh 4Qj4zIH6Vt6PIDn/r3d1GNW00RlEaq+MerAp3WkO+BwZ/2yCM+WJFG4w8tI3p+CjUlZehU2o WBxAmaLLHK3HOrCxiyGWZtIXy5plSfBjDomrlnlIiaDiC0N+MleHF8+IqxAo0XKySXn3AQDm UVBV0DpdIxm8dk2BCT5pMdnZFxzoBbSt57Tv9htwcwgAqpCy5Fhfcm5fVdhkeuaX86izCPfn 1k6FDt/3VUZ7lwcLJL9qYp1treUptfrUJ/DOeZN5LAyULj2Aijjy2Tni3RrDR9+1NvLTla4v bJpndEWI0nof1l8za+sfeQn8YnSylZLFt/Blx3MAe0MnNi9ZbGk50fdKjNsBwCwcZP/1Gyen s05rk2aaL07n5guCz/0bmlQFANCyi3lH+EcHJ0I4wYriBA4xJ3wDJmrCtjhsAtHNnc6pqvgE S2h2J7gAGa7A+ktFJhAxmVSx02GzakjNenx/SWMT2zlIZ/tu1T3wdX3SghUvX62p37FXPObF EbaEJZc9j4jUqnaJHbj/q717Gwf/S3mVyiMaIVzfbxmngGVfaf89vHRh7sWvkt9+TarR7Xen M2Bwi9wKgJ6pshkAnIe6VCGx4+JNH5SUiaxVr6TyrK9GcDkfCEwcVGwDBmeKdtv5Psb2Ho6t tTIWPwj/eQAJn283X18izF1xYYDFSct835R3hG6baP1FJZmMSm+CxV8C+uZXB/Yom/p4NblJ ujLJPGVampAZYs3ZVLrQBuxrXhGrDimFY9TLgO3ZN4gN4gQ3OvvBzmagwGMJdszTaRNE3JGE /qzvlvIs3KTLpQzybxZWwl7SO8b7A+i6+Yp9uN6thrpX7/TdnKcvnMezNYMRjuXvRGmaZ7c2 thgDF83fY7QvUGF1bCBSw7ZzbGVyICh1bml2ZXJzaXR5KSA8cGF1bC5yb2VzbGVyQHJ1Yi5k ZT6IewQTEQgAIwUCVAXA1QIbIwcLCQgHAwIBBhUIAgkKCwQWAgMBAh4BAheAAAoJEBbS1xKc azdG8XQBANG5xd6Uukm6eXmJRQoSoeax2AfsW7CU7oTb1svXQkqDAPkBhHVZXPjA52Y9en+d brtzeMJsONBXZ/HkU7BexNZ5SrQiUGF1bCBSw7ZzbGVyIDxwYXVsLnJvZXNsZXJAcnViLmRl Poh7BBMRCAAjBQJTDzbHAhsjBwsJCAcDAgEGFQgCCQoLBBYCAwECHgECF4AACgkQFtLXEpxr N0adkwD+KNzRjN+3gxZvDrOY47ABAFB06XM4lFzRYQy+JDJDgJYA+wa7pcSo2W8PnxbRGva5 Q1X/hB609vglzwzuw7qgMj1FuQINBFMPNo4QCACURJWG4Av5adB3/YMbhXGSSjNbANrLN2m8 /ovdqBx/pvF+1EeVg8UaHoqzmTCNOWjf5b11fQ/MzqsBp5OHWEmzXPv3en9IojoLXzgb9F4Z LFl/j+xfU4uOmyurKIKxbG2HzC/yFr2E0s0icXeMDp+kmdrtVWHikTTkSVzkEiRf6BfIZ3gu 0xR36vegSN5vqF8fF0zRo7C/96QmpjmjQxl02NDpsnyjtisp+nWYsbp1hcZr3PecSaNtcn/v hiBlKlO0aDUOj65o4JTgC8Pe4G8Hzk9bIiFqwKg6eI2HvrYcGEMMa70bJEZedAEjP/6BA2O5 dPNS8AJnYCFCxwOVnaqfAAMHCACGChurcAtQIbsN4ukQr27Bkky32sYl9HCWPlhp9dvrqQJG 4s46ArNKPL7t/k5hB6L5vLFhzT78kpPGFohF4sM/+Jp+b8TZvqfSQqvOet0K78TAn6rky3Ks uVQd5js0RWNVmFjD3NovonkR3gQl9s5gzOi9A+QnesMsKqz+mFimDVh3X6oajU4OMtcLxOEF ++hIv+kuG98fEvI9ABOm5PitWE1rdGwxx5DiM1UovlK8nC6iataAVTK15FAu3XYzoOOZpR5N cdKe1+qNBXLz7WsL+TVSFXfnK4ZQxsOY8vl1wZZi9hdGpMEoLf00xe0gIzzNMFNOUaEynZlz P6WRrstHiGEEGBEIAAkFAlMPNo4CGwwACgkQFtLXEpxrN0bDswEA2Aq8+20ke9jg6DBbiJ5W TfRAWsgy0qEM+vSIlyhvNqMA/0G4l/CwYBH/MTSUHJG0K8nKY1iGy3kd/0WK1jicEnZG
Message-ID: <8269896b-5b33-1aef-0e55-1cf0773b4764@rub.de>
Date: Mon, 28 Sep 2020 11:59:23 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/4h-LgdY1hdEu6PkdU4EufPI2f7Q>
Subject: [MLS] Concurrency in MLS: Lower and Upper Bound of Communication Overhead
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: Mon, 28 Sep 2020 09:59:30 -0000

Hi everyone,

some of you may have seen my talk on concurrency in group ratcheting at
the secure messaging summit already. The full paper by Alexander,
Yevgeniy, and me is now available as well [1]. In Section 6.5 we collect
some points relevant for practice.

I want to shortly summarize the interesting parts for MLS:

1. Lower Bound: "It will be hard to become better"

For our lower bound, we assume that members in static groups send in
rounds (i.e., in separated time slots during the execution). The number
of senders in a round i is defined as t_i. Naturally, members can decide
to send whenever (i.e., in which round) they want without being
scheduled by anyone. We only require from group ratcheting constructions
in this setting PCS against passive adversaries.
Our lower bound on communication overhead shows that every such group
ratcheting protocol, using as building blocks dual PRFs, broadcast
encryption, and hierarchical identity based encryption (thereby
key-updatable public key encryption), must let every sender in a round i
send at least t_{i-1} messages.
We note that there exists another lower bound on communication overhead
for group key exchange under FS [2] (allowing for the use of weaker
cryptographic building blocks only), showing that at least log(n)
messages must be sent per round if only one user sends.

We conclude that sending less than t messages per sender under
t-concurrency (i.e., t members send in every round) requires the use of
more powerful tools (potentially exotic ones like multi-party
non-interactive key exchange) or weaker required PCS guarantees.

It might actually be worse: In case the two mentioned lower bounds
simultaneously apply, t*log(n/t) could be the minimal communication
overhead per sender in a round. We did not formally analyze this.

2. Upper Bound: "It is achievable"

For static groups under PCS and FS we provide a group ratcheting
construction that has communication overhead of only t*(1+log(n/t))
under t-concurrency. Based on a TreeKEM-tree, the construction lets
every sender in a round firstly only update their own leaf key pair.
Secondly, senders update the paths of senders from the last round.
Although we originally didn't think of it as such (and the basic
concepts are actually closer to broadcast encryption literature), one
can intuitively view the protocol in the notation of Tainted TreeKEM [3]
as follows.
When sending:
1. Propose a new key-pair for only your own leaf and "taint" the entire
path from it to the root.
2. Commit by updating the key pairs on all paths that were tainted in
the last round and untaint them immediately.
3. All receivers agree which of all (concurrently) sent commits they
will apply (e.g., lexicographic).

We know that this simple protocol is insecure with respect to the
double-join issue. However, we think that many practical groups are
indeed static, and applying the other concepts of Tainted TreeKEM can
fix this issue. Also the issue of synchronizing rounds is only relevant
in a setting without a central server and can then be solved by weakly
synchronous clocks such that rounds have rather long periods (as
processing concurrent updates already saves a lot of time in reaching PCS).

We conclude that our idea may help to maintain a balanced tree and
speed-up path updates under almost optimal communication overhead for
users who want to reach PCS in a concurrent setting.

We are happy about any discussion, comment, or question (both on this
list and private). :)


[1] https://eprint.iacr.org/2020/1171.pdf
[2] https://cseweb.ucsd.edu/~daniele/papers/OptimalMulticast.pdf
[3] https://eprint.iacr.org/2019/1489.pdf

M.Sc. Paul Rösler
Horst Görtz Institute for IT-Security
Chair for Network and Data Security
Ruhr University Bochum, Germany

Universitätsstr. 150, ID 2/405
D-44801 Bochum, Germany

Telefon: +49 (0) 234 / 32-26728