[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