Re: [MLS] New Tree-based Application Key Schedule

Richard Barnes <> Mon, 01 July 2019 22:12 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 5A7F3120180 for <>; Mon, 1 Jul 2019 15:12:42 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Status: No, score=-1.897 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id CmQruRlIUTwZ for <>; Mon, 1 Jul 2019 15:12:38 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::32d]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 406C91200E7 for <>; Mon, 1 Jul 2019 15:12:38 -0700 (PDT)
Received: by with SMTP id j19so15131903otq.2 for <>; Mon, 01 Jul 2019 15:12:38 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=UAPWFWaLJluuAsT/oyEdKMusBfFszTpWqZfm4VapgcQ=; b=M/MHkRvqLIVy1i6tdsG+FWxQ9c68sEpBvloS2UW+OHwabAqwNCeItGEZ8v1F00DT7M lL4yHkcqZHut0tXxUSjNzCkeE6k1ySmUoYpeCCuAt+FlHTAL8QM1JkLdF+loMAUsBepc 09C24vzY2WcgT9AE+rVWununKIOqfqznuMp492m7HnfcoBW6FDpQw+sRXqgMvZq/kPRq RApRn3Z9qMtZM+Gyl/3239Xy0+lBybfXEOv9ETSoL9RySXLwkiAGu1kvhv2UswYRV5Yl U0J2mm4Ow7cnLtbc/Asjw4R5nCz5p0w4xij6Wnx7FIvOXBNN+7bZMH068F3AN/h6HK67 eUjg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=UAPWFWaLJluuAsT/oyEdKMusBfFszTpWqZfm4VapgcQ=; b=e8jrrMe8mW2j01zbOg8MBvoQxZ+E7EffpHbAcLIhneoN8jYAhzGUZCSDpGtZC8SAIa rC/L0evLfu0DEyhi+384yDJFiMRXCrhAfgFk3F0Z8s8vu96mmuCdOqKai0ohMFhM8LlX JHsjHKNYxFV29DNnmexudctmu2jS5W4ex+GijdWrbv9067qz8DjRJk58KBB0uDJfI6J4 XTUz7fuHttQPSU9BMFSZn/NtjL+e2UiwrEavLNLx7UkhkFihKnx/rYtv9YL3o9J/8NLP dGsi9G3xz2JKXXzmBRTUrNJSFVeKu8dMbVEPY6A8Ov3Zr/yqLeNaFSmnlLZ7fBYz+5tu VccQ==
X-Gm-Message-State: APjAAAWne4nJqUsmKvxp58PjhtOdpCqVtzgcmTG6u+LTZNMwxMDFMFrN uj7ppTCXjwxasBKQFtjQyoIA0uVnyT1RYW0jAX0UPpLTqtykeg==
X-Google-Smtp-Source: APXvYqwsAnjzywhj+8jgj/Yb3/0VTKt9FKODnjXJdaURUC/cfr6+hJLQYM9uLIEn9AkZiF4su64Vpsf7szt77bXm9fY=
X-Received: by 2002:a05:6830:1542:: with SMTP id l2mr1773084otp.241.1562019157517; Mon, 01 Jul 2019 15:12:37 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <>
In-Reply-To: <>
From: Richard Barnes <>
Date: Mon, 01 Jul 2019 18:12:22 -0400
Message-ID: <>
To: Joel Alwen <>
Cc: Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="000000000000043dba058ca5ed6c"
Archived-At: <>
Subject: Re: [MLS] New Tree-based Application Key Schedule
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: Mon, 01 Jul 2019 22:12:43 -0000

Hey Joel,

Just reviewed your PR (
Sorry for the long delay; the impending Internet-Draft deadline in a week
has spurred the authors back into action.

Overall, this seems pretty much right.  My major concern is that the
mechanism seems a bit heavy-weight, in that it pulls in a bunch of context
in the key derivations.  It seems like we could get away with a much
simpler scheme (as I've outlined in the review comments), but if you think
there are reasons we need the extra context, I'm listening.


On Fri, Apr 12, 2019 at 2:31 PM Joel Alwen <> wrote:

> Hey Richard,
> Thanks for your response! For the deletion schedule I think there's no
> problem with out-of-order messaging. Basically if a secret is consumed then
> just before deleting it derive any (unconsumed) children values that may
> still be needed.
> E.g. if in a ratchet msg j arrives before j'<j then first derive the j'-th
> key/nonce for deleteing secret j'. The same goes for any other (now
> consumed) secrets between j and j' in that ratchet. That way if any of
> those msgs arrive one can still decrypt them. But if there's a state
> leakage nothing useful for decrypting the j-th msg is leaked since keys &
> nonces are dead ends in the derivation hierarchy.
> Similarly in the AS Tree if a node's secret is marked as consumed then
> just before deleting it derive and store the secrets of its unconsumed
> child.
> - Joël
> On Fri, 12 Apr 2019, 20:14 Richard Barnes, <> wrote:
>> Hey Joël,
>> Thanks a lot for putting this together.  I'll review the PR shortly.  In
>> case other folks need it, here's the link for the PR:
>> Overall, I think this is a sane idea.  The thing that really sells it to
>> me is your observation that the AS tree has the same structure as the
>> ratchet tree, which points to a very elegant implementation approach:
>> - Add a field to each ratchet tree node to store an app secret or nil
>> - On epoch update, clear out all the app secrets in the tree, and set the
>> root node's app secret to the epoch app secret
>> - When you need an app secret for a leaf (to encrypt or decrypt)
>>   - Search toward the root until you find a node with an app secret set
>>   - Work back out to the leaf, deriving the two app secrets for the
>> children and deleting the parent app secret
>> On the "deletion schedule" idea: I might be wrong, but I don't think
>> we're going to be able to be super tight here.  Applications are going to
>> want to be able to tolerate out-of-order messages, in which case you're
>> going to want to keep around a parent secret after one or more of its
>> descendants have been consumed.  I like the "consumed" idea and
>> terminology, we just might have to apply it with a bit of flexibility.
>> On the "context" question: I don't really feel strongly here.  The
>> current scheme doesn't really fold in any group context at all, which is
>> consistent with what TLS does [1].  Given that that's simpler, I might be
>> tempted to keep things that way until we find that there's some deficiency.
>> --Richard
>> [1]
>> On Fri, Apr 12, 2019 at 10:07 AM Joel Alwen <> wrote:
>>> Hey everyone,
>>> I've submitted a PR implementing a tree-based application key schedule
>>> based on the ideas proposed by Benjamin Beurdouche, Sandro Corretti,
>>> Yevgeniy Dodis and myself.
>>> On the one hand it allows for easy handling of concurrent / out of order
>>> message delivery within an epoch (as each group member has their own
>>> independent symmetric ratchet). On the other hand it avoids having to do
>>> linear amounts of hashing and key/nonce storage as soon the moment the
>>> first message in an epoch is sent (as would be the case if we
>>> immediately seed all sender ratchets directly from application_secret as
>>> in the 03 draft).
>>> Basic idea:
>>> - The Application Key Schedule consists of a left balanced binary tree
>>> of secrets (the "AS Tree") and one symmetric ratchet per group member.
>>> The AS Tree has the same node/edge structure as the ratchet tree for
>>> that epoch. Members are assigned the same leaves.
>>> - Each node in the AS Tree is assigned a secret. The root's secret =
>>> application_secret. The secrets of children are derived from that of
>>> their parent.
>>> - The secret of a leaf is the initial secret of a symmetric hash
>>> ratchet. The ratchet generates the key/nonce sequence used by the leaf's
>>> group member to encrypt messages during that epoch.
>>> Other comments:
>>> - I included a "Deletion Schedule": keys, nonces are 'consumed' if they
>>> are used to encrypt or successfully decrypt a message. Secrets are
>>> 'consumed' if a value derived from them are consumed. Any consumed value
>>> must be immediately deleted (for reasons of forward secrecy).
>>> - Maybe the most contentious issue: I was very generous with contexts
>>> for all calls to HKDF. E.g. I included Hash(GroupState_[n]) in the
>>> context of every call. I doubt its needed to prove security against more
>>> coarse adversarial models (e.g. ones that only do all-or-nothing state
>>> leakage). Still, as a matter of the "defense in depth" principle I think
>>> including as much relevant context as possible during all key/secret
>>> derivation is a good idea. Albeit only as long as the price (in
>>> computation, complexity, etc) is not too high. To that end, I used
>>> Hash(GroupState_[n]) instead of GroupState_[n] directly in the context
>>> as it is much short, needs only to be computed once at the start of the
>>> epoch and can then be used to very cheaply to construct any context
>>> needed for the rest of the new schedule.
>>> Curious what you all think!
>>> - Joël
>>> _______________________________________________
>>> MLS mailing list