[MLS] hardening MLS against bad randomness
Joel Alwen <jalwen@wickr.com> Fri, 17 April 2020 12:42 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 4244F3A064C for <mls@ietfa.amsl.com>; Fri, 17 Apr 2020 05:42:16 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_HELO_NONE=0.001, 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 cbIrX137anw0 for <mls@ietfa.amsl.com>; Fri, 17 Apr 2020 05:42:14 -0700 (PDT)
Received: from mail-pg1-x52c.google.com (mail-pg1-x52c.google.com [IPv6:2607:f8b0:4864:20::52c]) (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 C53083A0640 for <mls@ietf.org>; Fri, 17 Apr 2020 05:42:14 -0700 (PDT)
Received: by mail-pg1-x52c.google.com with SMTP id 188so1035834pgj.13 for <mls@ietf.org>; Fri, 17 Apr 2020 05:42:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wickr-com.20150623.gappssmtp.com; s=20150623; h=to:from:subject:autocrypt:message-id:date:user-agent:mime-version :content-language:content-transfer-encoding; bh=T25Bckq0Aj6ayIox588bnPtEV+yGyImkKDg+yJU5kd4=; b=g1bceUOuejjMEOdQPruMuCN2WgnhuIZYqFJFEnVuEEs5wglKqiEgYVWRzzXyBsayyG s9nrlxj/U9rkusNQ0s9PaOTJ9C0ybpluBsRkGE3FvwCVAooo7BQiBCd4s/Fwd1G9jRLf ufpTwY30e2QQngRoEQgZdGdKnl1/eHywUVKyia0XJAcOjt8eU6Pw7ALaC887qG1c6duU c3C5U6E4Jr/aIUIgdg4JKrIMPTCFX8QTqzMRQ9y1h8jiyluiZv87h3+qw54YNqSedVqG co5crkTdJ591S24zIdcbGQAkBYsF13d7RLANYThQS9Zm8m3THZFbGT3F2kK2doLS8IZ6 mXuw==
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:autocrypt:message-id:date :user-agent:mime-version:content-language:content-transfer-encoding; bh=T25Bckq0Aj6ayIox588bnPtEV+yGyImkKDg+yJU5kd4=; b=hNg7mQ4huYsdx3tv1NPB4vYR4+ohVfBO6T1ZH8rMowwLSyen8yeVJfXvcZBPt6UuUs FsyWZw5+Tdv4mHOyDZeRbuTtMP6Wxijncb6khsaQBCfgRonF3p1vJA1hWPyDAa0YbVO1 4Yi5yTj2Xx5L2N9CS5Zmq/2TQfHOmyo114qIQhktJeJbHV9hLNzKREkaGz9B7Toqd7iN U0wkbRzH4V9xLhwV3E8YVOBuBekuEWgC0lr3CM2EF+P1V22uQo9sMEMhO2BCAEzKLdQc Ivts+FPAdI167AlTXbBfQGYiAKSQ5LZz5OU2oNDBGRMbFFCT2DqGZCOk+QRiknQ0V5pO yNTQ==
X-Gm-Message-State: AGi0PuYuk/BWki3+G+zRTojM2UyidElM5HHmvWH5iFZutxr3odttDXuv RdmltzEXp1NR8l5rqATOA1UwAhxx+E4=
X-Google-Smtp-Source: APiQypK5T1yAw/aMRS5Pmdmh3pCIY+weHtKO15rFJg9uKxLDnHjQrZ597AqSuW+ctyJV6wb+iJ6gXA==
X-Received: by 2002:a63:cd08:: with SMTP id i8mr2813026pgg.55.1587127333675; Fri, 17 Apr 2020 05:42:13 -0700 (PDT)
Received: from [192.168.0.24] (zaq3dc06154.zaq.ne.jp. [61.192.97.84]) by smtp.gmail.com with ESMTPSA id h11sm19522441pfn.125.2020.04.17.05.42.12 for <mls@ietf.org> (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 17 Apr 2020 05:42:13 -0700 (PDT)
To: Messaging Layer Security WG <mls@ietf.org>
From: Joel Alwen <jalwen@wickr.com>
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/JBuCpg18Aykru6xyFjG3gv0Lw==
Message-ID: <717aea51-d03b-c555-3863-a7b2b7a0eed6@wickr.com>
Date: Fri, 17 Apr 2020 21:42:11 +0900
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.7.0
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/ZR84smU5xeLrziNTk5W1P1Z1nQI>
Subject: [MLS] hardening MLS against bad randomness
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, 17 Apr 2020 12:42:16 -0000
hey everyone, Sandro Coretti and I have the following suggestions around MLS's defenses against bad randomness. The Issue: Currently the (CGKA) protocol TreeKEM relies heavily on people continuously having good randomness available. The problem: Good randomness may not always be available though in which case things can go pretty wrong. E.g. Say, Alice does a Commit with too little entropy (from the adversaries perspective). This results in all new keys on her Direct Path (and the update_secret) having too little entropy because they are all derived deterministically *purely* from the entropy she samples in that procedure. To be clear, by "bad randomness" we're not just talking about low entropy because of an on-device attacks by an adversary. We also mean things like very deterministic boot process/environments. (E.g. on some VMs, embedded device or even sometimes mobiles.) There's also buggy RNGs. (Things like the Infineon keygen bug in the Estonian ID cards. Also the stuff in "Mining you Ps and Qs".) The point is, low entropy can be a practical concern even when an adversary can *not* access the rest of your local state. The fix: We thought of 2 types of fixes to reduce the dependence on continuous fresh entropy. General Fix ----------- Basic Idea: MLS explicitly mandates a local entropy pool. Whenever MLS needs random bytes (i.e. when doing KeyBundle gen, or a Commit) call the OS/crypto-lib to get some (supposed) random bytes B from outside. HKDF bytes B with your local entropy pool. First part of output overwrites your entropy pool. Second part are the bytes you actually pass on to the calling MLS function. This gives you 2 nice properties. First, you are accumulating any entropy B *may* have into your pool. So even with consistently low (but not 0) external entropy your pool fills up and eventually your good for ever more (till your state leaks of course). That's true even if your external calls start going back to 0 entropy (e.g. say you update to a buggy external RNG implementation or your in a VM and the OS is getting (poorly) initialized from some fixed snapshot but your apps local state is persistent). Second, if your pool leaks, then as soon as your OS/lib gives you enough good entropy again you back to having a good pool to. So you have PCS for leaked randomness. As long as either pool or external entropy are good the resulting being passed to MLS have enough entropy. Pro: general catch-all solution. efficient, easy to analyze. Con: requires implementors to handle cryptographically valuable randomness & probably, to hook calls from their crypto-libs; a new and maybe touchy practical requirement for implementors compared to what MLS currently asks of them. MLS Specific Fix ---------------- To avoid the above cons (and maybe others we didnt think of) here's an alternate solution approach using only already defined functions from the MLS spec. We demonstrate it on the case of a Commit as this is probably the most egregious case. (If Alice uses bad randomness it doesnt just "pollute" her own leaf like when she does an update proposal. It pollutes a whole chunk of the ratchet tree.) Basic idea: Whenever sampling/deriving a new secret key, make it also depend on the old secret key and on the application key schedule. That way, if either the old secret or application key schedule was secure, then so will the new one be *even when using bad randomness*. Mixing in the application key schedule is valuable if there was no old secret e.g. when we're assigning a new key pair to a previously blank node. For concreteness here's how that can work for the Commit operations (C.f. Section 5.4 in MLS protocol version 9) commit_secret = HKDF-Expand(epoch_secret, "mls 1.0 welcome", Hash.length) ---------- snip ----------- path_secret[0] = HKDF(leaf_hpke_secret||commit_secret, "path", "", Hash.Length) If node n on direct path is blank sk[n] := ciphersuite key length number of 0 bytes. Else sk[n] := old_node_priv[n] path_secret[n] = HKDF(path_secret[n-1]||sk[n], "path", "", Hash.Length) new_node_priv[n], new_node_pub[n] = Derive-Key-Pair(path_secret[n]) ---------- snip ----------- Pros: only uses existing MLS functions. other parties implicitly verify that the fix is being used by re-deriving same key material as commiter. no need to hook RNG calls. Con: less general so full fix requires changing other parts of MLS where security critical randomness is used. In particular, key bundle generation (or at least updating in an existing session). - Joël & Sandro
- [MLS] hardening MLS against bad randomness Joel Alwen
- Re: [MLS] hardening MLS against bad randomness Christopher Wood
- Re: [MLS] hardening MLS against bad randomness Richard Barnes
- Re: [MLS] hardening MLS against bad randomness Joel Alwen
- Re: [MLS] hardening MLS against bad randomness Konrad Kohbrok
- Re: [MLS] hardening MLS against bad randomness Joel Alwen
- Re: [MLS] hardening MLS against bad randomness Hale, Britta (CIV)
- Re: [MLS] hardening MLS against bad randomness Joel Alwen
- Re: [MLS] hardening MLS against bad randomness Hale, Britta (CIV)