Re: [MLS] New Tree-based Application Key Schedule
Richard Barnes <rlb@ipv.sx> Mon, 01 July 2019 22:12 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 5A7F3120180 for <mls@ietfa.amsl.com>; Mon, 1 Jul 2019 15:12:42 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Level:
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: 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 CmQruRlIUTwZ for <mls@ietfa.amsl.com>; Mon, 1 Jul 2019 15:12:38 -0700 (PDT)
Received: from mail-ot1-x32d.google.com (mail-ot1-x32d.google.com [IPv6:2607:f8b0:4864:20::32d]) (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 406C91200E7 for <mls@ietf.org>; Mon, 1 Jul 2019 15:12:38 -0700 (PDT)
Received: by mail-ot1-x32d.google.com with SMTP id j19so15131903otq.2 for <mls@ietf.org>; Mon, 01 Jul 2019 15:12:38 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; 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; d=1e100.net; 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: <e49c3b6c-6ce6-da1f-f3bd-36f9af0c7d66@wickr.com> <CAL02cgQYdR=8d_6R=JmCaRQ5jERPogO2e7r2xhT2Md8mtb3kmQ@mail.gmail.com> <CANYP600AP_YwLONBedh5FJTbWMjj2j5AhugBN8vheeekM_41ig@mail.gmail.com>
In-Reply-To: <CANYP600AP_YwLONBedh5FJTbWMjj2j5AhugBN8vheeekM_41ig@mail.gmail.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Mon, 01 Jul 2019 18:12:22 -0400
Message-ID: <CAL02cgTv53EVc+R8xdmR2aB7Rca86tSnL13G_d7zVpX3aT-Eng@mail.gmail.com>
To: Joel Alwen <jalwen@wickr.com>
Cc: Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000043dba058ca5ed6c"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/tDLTT19_wWujOl60cS-T03TfKFc>
Subject: Re: [MLS] New Tree-based Application 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: Mon, 01 Jul 2019 22:12:43 -0000
Hey Joel, Just reviewed your PR (https://github.com/mlswg/mls-protocol/pull/146). 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. Cheers, --Richard On Fri, Apr 12, 2019 at 2:31 PM Joel Alwen <jalwen@wickr.com> 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, <rlb@ipv.sx> 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: >> >> https://github.com/mlswg/mls-protocol/pull/146 >> >> 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] https://tools.ietf.org/html/rfc8446#section-7.2 >> >> >> On Fri, Apr 12, 2019 at 10:07 AM Joel Alwen <jalwen@wickr.com> 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 >>> MLS@ietf.org >>> https://www.ietf.org/mailman/listinfo/mls >>> >>
- [MLS] New Tree-based Application Key Schedule Joel Alwen
- Re: [MLS] New Tree-based Application Key Schedule Richard Barnes
- Re: [MLS] New Tree-based Application Key Schedule Joel Alwen
- Re: [MLS] New Tree-based Application Key Schedule Richard Barnes