[MLS] Simplifying the key schedule
Richard Barnes <rlb@ipv.sx> Sat, 23 February 2019 03:28 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 3C099130E30 for <mls@ietfa.amsl.com>; Fri, 22 Feb 2019 19:28:16 -0800 (PST)
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 lBzdl2B6NDqg for <mls@ietfa.amsl.com>; Fri, 22 Feb 2019 19:28:14 -0800 (PST)
Received: from mail-ot1-x32f.google.com (mail-ot1-x32f.google.com [IPv6:2607:f8b0:4864:20::32f]) (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 D7FAF126F72 for <mls@ietf.org>; Fri, 22 Feb 2019 19:28:13 -0800 (PST)
Received: by mail-ot1-x32f.google.com with SMTP id c18so3591066otl.13 for <mls@ietf.org>; Fri, 22 Feb 2019 19:28:13 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:from:date:message-id:subject:to; bh=cydd69VkW7Q6A8o0oRbTCBmnD2RNKP8k10xmqH4gd+o=; b=yAlda0gr49H2r/YdMJ6ls5OhdzX/n0RIip+AvF19UF6QVS3e7DWuJaOkfKFzvPWlkv dKW8B/s5HYxKqGORRtqV0yDRxvYquEwka1s1Rq+hVvLXhTpG6tbxsSBEujPpnNiJtDh4 hScP1GuIEEaG6nJSB6j05fXAVRyGwIrWo5b7mPdvsqfM99imBSxtgLwKGhjdT6BNfQco tArdBBdgkjjzRLnlXxJEx/76sqzgEMpIjBysd8NfGQ79+n5/5ex3o+n/yGu6tfe+LXb/ 3ii0ou17qtaznRIpBVPZ9ZgKz+7Yr/zTCtN6RXL/R7ctRVriQBnvD8/i1lyFL24B5rq+ E1hA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=cydd69VkW7Q6A8o0oRbTCBmnD2RNKP8k10xmqH4gd+o=; b=hfYATopYGNUExgjrrmzvtqa/te5tTIUfp4wyf1IcD0BYzpYM/YXjkHD5Yc0nkUplm1 QoEPtKgHKt0J+AQaW3JW7Xkmvr7oQ5XR3lLz9h1NMX4wnByVayuEwXVybptFKal31eF4 Q5imR9lSGdHq1mChAZeI6I02DClFWCGMykwNk6G5JKeCwQRssgpXX3cRsvChflp8It0s g+uCgtDDHjWh6HI33wZnkxs2tZ2mG3He8KZJVh8E0SC8bebwP65gSWwPUdYh77R8KlYt 96SkfO7nA8MziFz1tAMCGay9kxSzcG9WdhsdtJq17KQZuod+sDigWX05zLQ5znMILP0P s5IA==
X-Gm-Message-State: AHQUAubK43bgk40JcWzC7+UpuDraOvq3eSx9D1r3RRqSNr1Br8AtNd1F /qd7TQfYVSEOgkt0o0pbKGpq0AnJ7uzHDyR20R2Kl6Ig
X-Google-Smtp-Source: AHgI3IZt+AwelLgtUwXJFgdpfOM8Lcj0eAPJby1T9Qq+nowbcfIP7Hr0iaBP8W5CBt6tDgdOg2U8ovzRdlH9QwZbr48=
X-Received: by 2002:a05:6830:1108:: with SMTP id w8mr4660639otq.167.1550892492759; Fri, 22 Feb 2019 19:28:12 -0800 (PST)
MIME-Version: 1.0
From: Richard Barnes <rlb@ipv.sx>
Date: Fri, 22 Feb 2019 22:27:56 -0500
Message-ID: <CAL02cgT_HiggpB6KDnXyqzyz5WUr=dAodmaRSPt+PfWj3BM3Mg@mail.gmail.com>
To: Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="0000000000001db44b0582874c8e"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/W8VYJv_i1xx3TN7U3x2nvAg5jOI>
Subject: [MLS] Simplifying the key schedule
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: Sat, 23 Feb 2019 03:28:16 -0000
At the last interim, we filed an issue to discuss simplifying the key schedule. In particular, folks were unhappy that the whole, possibly gigantic GroupState object has to be hashed on every epoch change. When I sat down to think about how to simplify, though, it wasn't clear what direction to go in, because it wasn't clear exactly what people were finding painful. I'll posit from the start that I'm pretty sure that we need to somehow include the tree, the roster, and the message transcript into the key schedule. The transcript inclusion follows from the same reasons as it does in TLS; the roster and tree are needed because the whole transcript isn't accessible to a new joiner (so the new joiner can't infer those values from the transcript). With that said, there are multiple ways to represent those values for inclusion the key schedule: 1. Directly (as now) 2. As hashes 3. As structured hashes, e.g., a Merkle or "ampelmann" tree People are clearly unhappy with (1). The difference between 2 and 3 (and between variants of 3) is what value we're trying to achieve. (2) reduces the amount of hashing somewhat, but it doesn't change the amount of state you have to keep -- each member has to keep the full roster and tree, and hash the whole thing when it changes. For (3), it seems like there are weak and strong forms. In the weak form, we make it so that the member has to hash a sub-linear-size amount of data to update its representation of the tree/roster when it changes (e.g., in a Merkle tree, you have to recompute log(N) nodes). But each member still has to have the whole structure. In the strong form, we arrange the protocol so that a member can operate while holding a sub-linear amount of state (e.g., just a copath/frontier in some tree). Note that the strong form would entail pretty major protocol changes, e.g., bringing back the Merkle membership proofs that were in earlier versions of the protocol. For similar reasons, this would also entail larger messages. So basically, the mapping of options to values is: 1. Overall simplicity 2. A smaller coefficient on the linear amount of data hashed 3(weak). Sub-linear amount of data hashed 3(strong). Sub-linear amount of state In my personal value judgement, I would probably end up somewhere between (2) and (3,weak). It seems pretty unavoidable to me that members will have *some* linear-size state for the group, even if it's only a names for the members; adding say a key and a roster entry for each of those doesn't seem like a huge increment. So appealing though the state savings would be, they're not compelling enough to merit the protocol complexity and overhead. All that said, I would be interested in other folks' thoughts on which options are to be preferred here, or if there are other options that come to mind. Thanks, --Richard
- [MLS] Simplifying the key schedule Richard Barnes
- Re: [MLS] Simplifying the key schedule Joel Alwen
- Re: [MLS] Simplifying the key schedule Benjamin Beurdouche
- Re: [MLS] Simplifying the key schedule Richard Barnes