Re: [MLS] hardening MLS against bad randomness

Christopher Wood <> Tue, 21 April 2020 19:37 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 0B3E53A08C1 for <>; Tue, 21 Apr 2020 12:37:44 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.1
X-Spam-Status: No, score=-2.1 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key) header.b=eTVwcGZ/; dkim=pass (2048-bit key) header.b=jG1w3Yqm
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id D4wfZOyM7tEx for <>; Tue, 21 Apr 2020 12:37:31 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 163C23A088D for <>; Tue, 21 Apr 2020 12:37:30 -0700 (PDT)
Received: from compute1.internal (compute1.nyi.internal []) by mailout.nyi.internal (Postfix) with ESMTP id F0BF65C007C for <>; Tue, 21 Apr 2020 15:37:29 -0400 (EDT)
Received: from imap7 ([]) by compute1.internal (MEProxy); Tue, 21 Apr 2020 15:37:29 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; h=mime-version:message-id:in-reply-to:references:date:from:to :subject:content-type:content-transfer-encoding; s=fm1; bh=LiVEz DSVBonuefb0d2LuMReTZCH61TyFFcmJ35q8amM=; b=eTVwcGZ/qvoi1E5MWAyXQ MZLD+wmoL538sRPk1mR9qTOm2sBw8+tHjaxs7DWS63aIu+S1hC+bJG7rDhJkIt8F iWoc4WnhpoL05G0jLle39MGihlf7XzqK05n0aB9GmOgh1HAGXEKgs4x0y39FcVAv Iz/VQMogBaLXfR8w/UXGDUlsgUIcxbmqr///S1DUVsO8pcEiAmxnGKa54kC6yEd9 YJGA5VIfvTNcKgPHo6fd6ctzA+6v6G+fgVc0f9+caGGy0bmhAnFP05wKGkjObQ4g rZ3vlDthy8UmDpWOrm6cIIxnFRPPEbS0dJP5N67CeAE2hZef86LqtBVs5opnm0jX Q==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=; h=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm2; bh=LiVEzDSVBonuefb0d2LuMReTZCH61TyFFcmJ35q8a mM=; b=jG1w3YqmrTrE5/X/dpzbyiydJRRZm0FQzppgZBDWEgRjK89bdtJQbqRux 0+bcSJPgFGTe9/zRXfmDYVR+JCKFWKb1butreP5Z0lw/sLSTEQANtnwiDbtuoBHg dMDx2l4iGv8NOYh9Hi1TXYvC03TCvrV+z66R3ceLJwZWiRfMvaRB5sz/yv2wdFhS yzGdLNjA0Coy3HzT/S6z8PbSDQx9YAw73yyHU6S03esA/6nicrOc/hN9ObhMy/59 GAtRcPO0gC4OdE9PSkoazJOjmc7DuPVuh8ZAp7BqP1R7Lr/XksaZGT88CVQLSCrq wVU6qJp23jzOI72U9XXb1Av4AX+2A==
X-ME-Sender: <xms:eUufXnNwlXSJJYsoWAdMa22DLC6Ef01LaCbsxhJp71u0shStTgrDIw>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduhedrgeehgddufeekucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtgfesth hqredtreerjeenucfhrhhomhepfdevhhhrihhsthhophhhvghrucghohhougdfuceotggr fieshhgvrghpihhnghgsihhtshdrnhgvtheqnecuffhomhgrihhnpehivghtfhdrohhrgh enucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpegtrgif sehhvggrphhinhhgsghithhsrdhnvght
X-ME-Proxy: <xmx:eUufXuqNjhqkM2BkxLUM3XK4vp9qPtpo8rsGSpzgaXn0kTdeG-MyMg> <xmx:eUufXvX9VX6In9v5wofhP1D4gz-eTpNgTTFDAfXufY-nV3bMJbTejw> <xmx:eUufXgtt2wLJXacJiQ2TdkNJoF2vfnwbuqHeEQr3dtKG4haxhdEFkA> <xmx:eUufXoR5TxrddfD2MO-aZRchBWAm32eJomF0_y2a4QBUvfkftp0Lpg>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 799DA180093; Tue, 21 Apr 2020 15:37:29 -0400 (EDT)
X-Mailer: Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-dev0-351-g9981f4f-fmstable-20200421v1
Mime-Version: 1.0
Message-Id: <>
In-Reply-To: <>
References: <>
Date: Tue, 21 Apr 2020 12:37:09 -0700
From: "Christopher Wood" <>
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable
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: Tue, 21 Apr 2020 19:37:45 -0000

For what it's worth, I lean towards the general fix. This doesn't seem to be a protocol issue, so mitigating it with a protocol-specific fix doesn't seem ideal. 


On Fri, Apr 17, 2020, at 5: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