Re: [MLS] hardening MLS against bad randomness

Joel Alwen <> Wed, 22 April 2020 12:15 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 358B83A0ADB for <>; Wed, 22 Apr 2020 05:15:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 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, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id I2KbJBuBG5HD for <>; Wed, 22 Apr 2020 05:15:14 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::1029]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id E7BFF3A0AD9 for <>; Wed, 22 Apr 2020 05:15:13 -0700 (PDT)
Received: by with SMTP id t40so863831pjb.3 for <>; Wed, 22 Apr 2020 05:15:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=subject:to:cc:references:from:autocrypt:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=EG7Gmu9N/oLUL348LxbtUi7qsPajvZztoe0vlyQIbfs=; b=UlousOnSEJI/f2NigfFq7gk6TXucdfyla9RE3MMftwXSBM1j02B4MnzLXuRF3DR5SG KVSoTt8v652cvdFK/IRm1LDVelPA6fPqaxqRpcMw8Lc82GlhgddKA3u1HPYlkLZFm4yc JBAGZEjgS46AGhd9KKsCEHaN2VBK4M2drTcw7vw5R3nuKHyKQBy5Q55wP8QqUMVBTSrP Vi84Ga/SQP5Ms6TiUcZm6saVu4sWHOpHhAebW51EtFxjORRtsRpM/0VdcdS+A8NXd5UT jnBtRGOQQqqALyJU+hhF24FLffw6NnPsEd+uMNdCzd9iVx9o84KYQW2VZVEBOtt5kopZ OdVg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:autocrypt :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=EG7Gmu9N/oLUL348LxbtUi7qsPajvZztoe0vlyQIbfs=; b=ZwJ41CMH0ijJI1EpQ1qK0Q3x4/iYSbv4QIk7HjzHeElajecsSH4MjH075HBTy5FSKn 9dYsGyhC8hazKbq7zO+0aBnkoJ+RpnpZaKfCQLO0NQ6Mx9k5ffAHAuClrVvxj79m1fM6 LwwlHqZcO9ueUf7mY5DqI87w26H9JldAqzWXKXX6XSdU+uXQOE6LARw0CwqFSYz0BY5g DJnyTaZaTzQ3huFUlFWAlsaj1oP2Ej0wQm5AQzMgshntmYkNDjOH+t9NY2e1i0RjQVfD 0UJrJSuVIxu4p+oeqn/A/rz5vndq6k1r0fGMsMLGraKp0mfiErzOClk6vNXVTYJH7DLT 2P3Q==
X-Gm-Message-State: AGi0PuYiklzvHSbvfFJpXgGMuff6YA9C/18BS3qAV4qwdnkbM7E5X5ia CHDuOgMd/oCPwfMbd01crlFfJu6+p2M=
X-Google-Smtp-Source: APiQypLqreyo31XXLMgs/xlsk5PzhzBUJLjYPDZ1kfshwysEjU5UgYVypPmhQR2SkW5GJY/uomYOvw==
X-Received: by 2002:a17:90a:104f:: with SMTP id y15mr11359405pjd.191.1587557712409; Wed, 22 Apr 2020 05:15:12 -0700 (PDT)
Received: from [] ( []) by with ESMTPSA id c15sm5288013pfo.188.2020. (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 22 Apr 2020 05:15:11 -0700 (PDT)
To: Richard Barnes <>
Cc: Messaging Layer Security WG <>
References: <> <>
From: Joel Alwen <>
Autocrypt:; 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: <>
Date: Wed, 22 Apr 2020 21:15:08 +0900
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.7.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <>
Subject: Re: [MLS] hardening MLS against bad randomness
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 22 Apr 2020 12:15:21 -0000

Hey Richard,

> I'm inclined to say that this is not a matter for the MLS spec.

> So I definitely would rather go for the general fix.

I'm not sure I understood you. Could you clarify? Are you leaning towards
putting the general fix in the protocol RFC or rather leave it out? Or something

As for not being in spec. My take is a bit different. In principle at least, I
like the idea of designing crypto/security tools to withstand bad randomness
when possible (at a reasonable cost). Two examples of modern designs which I
believe take a similar view are EdDSA (i.e. Ed25519 & Ed448) and AES-GCM-SIV
(and other nonce reuse/misuse resistant AEADs). They all include mechanisms to
reduce the impact of bad randomness. I think similar defenses could be in scope
for MLS too.

Could you elaborate why you lean towards this not being a matter for the MLS spec?

In the mean time, continuing with the EdDSA / AES-GCM-SIV analogies, the general
fix is philosophically closer to the EdDSA's approach. Functionality doesn't
depend on actually implementing the defense. (The verifier of an EdDSA signature
would still accept signatures if R where chosen differently than specified in
the spec. Similarly, a Commit msg receiver in MLS wouldn't know if the sender is
using an entropy pool.) None-the-less the EdDSA designers felt it a good idea to
design their scheme with such a defense in place.

The second solution for MLS -- "hashing in old keys" -- is more inline with
AES-GCM-SIV in that if you don't implement it as specified then you loose
functionality. Receivers wont decrypt / process your output correctly.

- Joël

On 22/04/2020 04:46, Richard Barnes wrote:
> Hi Joël,
> Thanks for thinking about this, and for the reminder on the call.
> I'm inclined to say that this is not a matter for the MLS spec.  It's not a
> protocol / interoperability issue, it's a consideration for how you build your
> client.
> So I definitely would rather go for the general fix.  If some better platform
> guidance is needed, run it through CFRG.  Maybe describe the implications of bad
> randomness in the Security Considerations to the protocol.
> --Richard
> On Fri, Apr 17, 2020 at 8:42 AM Joel Alwen <
> <>> wrote:
>     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 mailing list
> <>