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

Joel Alwen <> Fri, 12 April 2019 18:31 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id E54191203D3 for <>; Fri, 12 Apr 2019 11:31:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.9
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, SPF_PASS=-0.001, 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 jyeVYur9mw0i for <>; Fri, 12 Apr 2019 11:31:28 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::62d]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 8CF121203EC for <>; Fri, 12 Apr 2019 11:31:25 -0700 (PDT)
Received: by with SMTP id f36so5530246plb.5 for <>; Fri, 12 Apr 2019 11:31:25 -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=ulnVDHCUCOgNZnP/46OLBs+McqliQeV1zbrFiEOQ2KE=; b=qrPRwgWxRrXwJqR2gyrufwBPb9sPV7qiznk8kAFeTwG2/Ai82v99/bJFuc9wnK0raS KgsKywBkSl5jl27LdJqkSW4SDdI/Mfs7zBs2CievF/RQlZK0poRxUAQI4G3R9+0uYm3F lWAXncLKQA2byyaQ4K7F3C/tw8j//LqVDnq0tkUqt5cEk0PiAJWzHkJGRRC3RozA3mFg +39QmEBes2withq8brRX9TfywBQnxb2X/LxNmQ7bpJ58/8AP7sKmAVJj6St2KINriGwm qBqohEL6PHrf41O81RpiOwY2izXSASt5kgpAJHLpVd6IBSaIs2raJxXnTdoHrZ5TyCIH /01w==
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=ulnVDHCUCOgNZnP/46OLBs+McqliQeV1zbrFiEOQ2KE=; b=JJEkhW4UbjutF3np80EPmPkNy+qcHcC1LGlc+gGGJ12O9r5uN8AKo9uVR+69KgBR2E Bq8uD29dJaGEDTqGiMf5VdekmORogiZNTop8PBt/JLqC065AuWFSHbTl75LXJIttq779 r1Esc1lSdMdYXl9IdKLZKAc3aYGZNF8lZZGQ3pvR/WDEmT6dqjusV3WaQpxPAEIwo+xq syOgkMUm44LzBG7S/bvU1nxB1iY921cULmfIeW46on1qNJz75FoZklv9Lf2BIRQMCGRc UZdmdfNAFNbcO2u4AAWtSkoJ/XPN3qBatuUoO9VnawjfkUkYvkxlgrnxqhboYX0trGXL YbrA==
X-Gm-Message-State: APjAAAX8CNRpNXHmDdi7JPlNVHrmA0LPaTtyUMi78z0Swhoi91zBum49 tt1JbqlPhMJ74mS2xNrZO0BVRUJMygHcvnAVseXn4s3y
X-Google-Smtp-Source: APXvYqyf2LJURhkXLM/2JSZ56l4msB4kGnSJzMSVcZJaM93NaIw/GlF/2Wpae5rqdgh/B7nScmznrXC5sf9f1vQ6fMI=
X-Received: by 2002:a17:902:2ec5:: with SMTP id r63mr5506206plb.139.1555093884487; Fri, 12 Apr 2019 11:31:24 -0700 (PDT)
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
From: Joel Alwen <>
Date: Fri, 12 Apr 2019 20:27:58 +0200
Message-ID: <>
To: Richard Barnes <>
Cc: Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="00000000000093de430586598255"
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:31:32 -0000

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