[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