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

Richard Barnes <> Fri, 12 April 2019 18:14 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 6CEE51202E1 for <>; Fri, 12 Apr 2019 11:14:46 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 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, URIBL_BLOCKED=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 ZvYOoNsJZvAh for <>; Fri, 12 Apr 2019 11:14:43 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::22c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 9580A12012E for <>; Fri, 12 Apr 2019 11:14:43 -0700 (PDT)
Received: by with SMTP id j132so8748619oib.2 for <>; Fri, 12 Apr 2019 11:14:43 -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=+CE5w+n6zgczCuEVEowG5fdl43vzxXGvYIWScmsG0SE=; b=LW08Sx7PR/+UE11CLbhnBuo7jybkvhUFqbrCAqz5FfiA/WW4znEn6s1dqD9Pwo1k5p MRxANPQD7hnAz1+2ePkx1yCIjL7iaoQ72obI2A3kkvXHZqmy0dEcIJ89q5XxxIM1JoA3 HaPiw/wfox8BWcAFwlFYDWMYcC6AzlBhhGMfLayERbVWCr3OdWpjQ4xwuDt2EPagGYCh CA7BqEthxuFwdarA8QZKdH4RXJ2QbG3F1eCQAbm8VtIW33PrZZa0A7cJe9n0N9/8Vgkz 8W68zaXOX56XNj0hLQfvV0U3woFDzvhPFUzKEEbBfGOoQx34F7ahgw4CMlmE6zoND+o8 tSKw==
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=+CE5w+n6zgczCuEVEowG5fdl43vzxXGvYIWScmsG0SE=; b=Gt3of/L7oc0vbc406T+S27tQNKccoQk5C8MgvJ3ep9wejsQ0qyfpCPqoKcQa5cmfbV TX1NbL9r+XVYbAhH6dra67gtccgeThY40Uq0oDGqKuUBEgbTIr466uKzqn2zKc2aXbBe yNmgzZGsDj0EmVp0EEwyTNHH4IAcHDzGHDzAKfIoiRe1w7Zc+Tq6eHv1/3VF4kiVJNRf j7r+kjR4bx5LNfx90gmN7MWIypC6yrmn8hWmvA6+oxPt09AUfffUyZTtEkrZyJcGS6La eR3zXGsMU+aNcgr9qM/uWyyJpoFOPaufO4F1SjV7zGJzXrW5ueoEtUr9Odx+SN85ppB0 uLiQ==
X-Gm-Message-State: APjAAAXHLtWRvH2r859AOyHGYqwayk4FasZtRogPU3nPjpn5E7PWMj7c L7aoFD53RRNSK/sWgveAV6XsgOxAu2ApkqR966K2lw==
X-Google-Smtp-Source: APXvYqwgX7VD7Uop9bYpLEnTsf7my7FYfkLSng0qnSlzm5rs0RfPRRRvvv3aFB3ObnSJBpPRmJa5Pt2xHvnjPifaFI8=
X-Received: by 2002:aca:544b:: with SMTP id i72mr10443260oib.51.1555092882839; Fri, 12 Apr 2019 11:14:42 -0700 (PDT)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: Richard Barnes <>
Date: Fri, 12 Apr 2019 14:14:24 -0400
Message-ID: <>
To: Joel Alwen <>
Cc: Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="000000000000dfed9d058659461b"
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: Fri, 12 Apr 2019 18:14:47 -0000

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.



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