[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