[MLS] New Tree-based Application Key Schedule
Joel Alwen <jalwen@wickr.com> Fri, 12 April 2019 14:07 UTC
Return-Path: <jalwen@wickr.com>
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 14874120716
for <mls@ietfa.amsl.com>; Fri, 12 Apr 2019 07:07:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1,
DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key)
header.d=wickr-com.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 ssUnBlBg5IuQ for <mls@ietfa.amsl.com>;
Fri, 12 Apr 2019 07:07:25 -0700 (PDT)
Received: from mail-wm1-x32d.google.com (mail-wm1-x32d.google.com
[IPv6:2a00:1450: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 BDEBA120715
for <mls@ietf.org>; Fri, 12 Apr 2019 07:07:24 -0700 (PDT)
Received: by mail-wm1-x32d.google.com with SMTP id o25so11398581wmf.5
for <mls@ietf.org>; Fri, 12 Apr 2019 07:07:24 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=wickr-com.20150623.gappssmtp.com; s=20150623;
h=to:from:subject:openpgp:autocrypt:message-id:date:user-agent
:mime-version:content-language:content-transfer-encoding;
bh=QpTq6bDWrGqYZsBkXvmcSDr802eE0Ie7DkdSl42cqzA=;
b=p9/em7MGMYd7zJFQOzZS5cAcU9g+BbfWAa3vOhJcetPYG2i0PupGchjF3ZTBo0DHGB
w3yhq9WXZxn3yDWud6DcHiSMcd/H7/4cn0zjuK4IvnUxzlJnRBnFZ+3MtCUSsv6FU+0E
voAzoa3WcdFPHjxHYgEFQXIeaWcQucNHIPogO2CUqmfmdc4gNt+vcjCGdg1dTe/Mi0Qy
O5jbmCmnbEWQPOeOl9qD2uE8ut5W0/d2b+Er6LrB9M5EscZhlsMoOYta+Ql9AQq+fz1G
ebhp7n3Og4KBTyEutlZjc8iUukAWe0tj/ipPjxlqjKDkkVERqE9LnksYvAHsDKA3/tle
dQxw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:to:from:subject:openpgp:autocrypt:message-id
:date:user-agent:mime-version:content-language
:content-transfer-encoding;
bh=QpTq6bDWrGqYZsBkXvmcSDr802eE0Ie7DkdSl42cqzA=;
b=hjj+ryLHyHfdErwaAW/QMLA+lc+5EY/+ef/mIiQWvIDZMtP3P8+3FGtZig9QFl67t1
aiSDOctREHVITW7IhfEpt4FIKLYxaAdlK4TlAePfe2fILiqq5vqNY64/8NsXwNzP6wKs
H0rvDV/sPxuKgvbLeKdRkTN8pNWmXnlpxa4dTO9v3Zedh+n3flM5KTeBpCtBA727FRM4
vAYpOL4BUWubhNnxUDHmT2JJO/oNeAuo7zyRUE/Efbekdg4Z+/UGT4LAX2gZ7FhIOIVH
ZHAUiuwguUKAnFo21SFLsHn1eaX/9rqxOfYkXovuj6XO3tRY4pKH8vSJlmZe29gDHjd/
l0Qg==
X-Gm-Message-State: APjAAAX5JKMX/eUc86LTmgNFNBBFxUhf1eLB/Bvd20MH9BeKcepLvODe
Wz9TBwta5oidZLWqj438lKuwjyMQH44=
X-Google-Smtp-Source: APXvYqyYEuO5BOSHo300Dn8+UdV6bb/e/VLdkqSZSHqEkHOrLEb8upYJPmbYEL391w/JV5p8XLcihw==
X-Received: by 2002:a7b:cbd6:: with SMTP id n22mr12085798wmi.57.1555078042697;
Fri, 12 Apr 2019 07:07:22 -0700 (PDT)
Received: from [192.168.1.137] (84-114-27-5.cable.dynamic.surfer.at.
[84.114.27.5])
by smtp.gmail.com with ESMTPSA id o6sm44550632wrp.41.2019.04.12.07.07.20
for <mls@ietf.org>
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Fri, 12 Apr 2019 07:07:21 -0700 (PDT)
To: mls@ietf.org
From: Joel Alwen <jalwen@wickr.com>
Openpgp: preference=signencrypt
Autocrypt: addr=jalwen@wickr.com; keydata=
mQENBFyIZvABCAC65JupY1w7gzhhNo41ftIk09n7Lid9p31jDR8Jefv9R5sWL+HZFGDeABAY
1J1JvV6vOaMsfdy9iUFfGS1GhMJ3+mh799SIsB3JSfPq/eq6Jut57D2yPtILmc7ZbuJyBHg0
xuYfKCQQAYikW+v2LJQU1Y+BUDbVldpzxSc8Z3PPSfunWdzhY6qAAhyCv+Y8EzJlQivMwD5B
f6737krf8SoBsjsqCHQrRo/r+BSj5Wtd5/K3FkmWLOUAFoYK23+cpoFntGJKZfss27gDPhyS
gX9ibXcBGQqBEF4qDPEzEHK8iQmXTxLul5Y7lQ6ADf69xH15WM4GmRBeCvR3Uanxcr2/ABEB
AAG0HUpvZWwgQWx3ZW4gPGphbHdlbkB3aWNrci5jb20+iQFUBBMBCAA+FiEEYFNg9IH2SV6e
03O3FR5tDZv8eygFAlyIZvICGwMFCQHhM4AFCwkIBwIGFQoJCAsCBBYCAwECHgECF4AACgkQ
FR5tDZv8eyjSywgApQNIRcL4IKTJ0I4XwcQRhICu1Bht3c2fUnG2YziJXjGf6DZ49uKKtuIu
fk8mNS+vKRLoLZ7+u+Pv/Yjmk8jtrr6Saz1vnfsle3GgmXG5JaKOM5cOfeo5JnlNUP3QonR7
LMZwY1qVKg2mzNmwi0jG1zIGgQ5fiAwqe+YTNFli5bc/H1O9LcSmbrLV9OyucARq11DIiAvU
fDknZ17OahQls+9mgfAXH5vZjzo296tYvzkOJQ2A6GPxdMHIXGbJM/vjuMe2QJl6C0zaqOtm
JvFcx/HpNhmugYI9OsNAd7846HASDp8BKyfY5FYP7bn0/JBuCpg18Aykru6xyFjG3gv0L7kB
DQRciGbxAQgA0Qx9LlxvJ0LGZlZRVyV8kPIxg8pNMmxJwJJ+JnTciW0LpfigfdAvGVf6PU0x
3V6SJKtz8D61c8KLyztxwPGRgJX2TRK3zvTlT5mqqnGYMAANttCF1+8DNpiYOMg3ibPRby46
4JPhMgWgvCJ1vHGu9cghjn1ttWIwBuKBXMc8HgACKYWsYZJiYtFEsnOdsD6aPWCg6NiImoc7
vRwNMKNNtDPxY95Yj4CRiLPVrZje3LyJlA9S+y2/p3w69R4AVLSRzAwDlupjXYs03QdNjGjP
2IR2u8RhstDgqW8+Bk3p7wjJ1kHTHgyox81/aHbnIRGKksPGPMPT3bvbpxevfqZ7ywARAQAB
iQE8BBgBCAAmFiEEYFNg9IH2SV6e03O3FR5tDZv8eygFAlyIZvECGwwFCQHhM4AACgkQFR5t
DZv8eygbLQf+OHSG6K9qiPdYxe61IR2kZdyogc2ArEGrl6AmcNzySXC8wlnreZo3FjfkD6xV
CQWwWDxI7B0JPM86IcfCfn45ADeI8rwm6yYIs00B4ag9Mmo0GQ4kQd2aTy60/QaE2ZSrnEtt
0fuz1G8DGnhPnOnMyCnCnkSNuTNG20OlI0cn5EJSxBS4fXVeBMBaV91DEmvLU6DjL+fOBQPq
CXIbFY7XffOmC4VxtAGhTadJ8WmUD8ZezXNs8c40Btpukr7j4piUshITfazPGEMXzTUTkimf
fAhNX1QQBsfP9kjfjxBn6jDl+lDJY34mANWwEJ8BKjgr09P0sOz4zjjFL62GcFczQA==
Message-ID: <e49c3b6c-6ce6-da1f-f3bd-36f9af0c7d66@wickr.com>
Date: Fri, 12 Apr 2019 16:07:22 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101
Thunderbird/60.6.1
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/1mu9j8cPDTOSa0Zkl6S9htOhWCY>
Subject: [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: Fri, 12 Apr 2019 14:07:27 -0000
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] 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