Re: [MLS] hardening MLS against bad randomness

Richard Barnes <> Tue, 21 April 2020 19:47 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id F153F3A08FC for <>; Tue, 21 Apr 2020 12:47:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_NONE=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 pJg-mt9c_2GZ for <>; Tue, 21 Apr 2020 12:47:35 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::82b]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id C04183A0902 for <>; Tue, 21 Apr 2020 12:47:05 -0700 (PDT)
Received: by with SMTP id w29so12657706qtv.3 for <>; Tue, 21 Apr 2020 12:47:05 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=3Nw4hSmQCvYiX6I3ag5JvibMizxAkPXB+QIRbA2ooTk=; b=GXkFO9KLJRrGP7o7zszT4AHbSALdi+Ps9jV5+B0VG3cyq2nmTbJkMknvNA5WTb4s5C 7cLovxv5Cg5oG0sC2osVH7zEPAv/CHdiNznBjqv/aVi7uWY/EI1TMIlwc8BsIFmaFzCS 8gBbVze1IQCtcB5ecPdlLtFRTa4iIGrHT5RFDuZn5S/C16zuCTAb4KVj23Dk8glctBvv Ffum3ZcatV/LoOlvMQhioPbmssNdJxgJuFmeL+Ga0DPtasuuDzncJhxkOb6QYevhzvw6 XRmRQ9NDbOzOhWTvEqi17j8OECG7ZmUZDN9XggCxmgXiMj2ZYVmCcXXbVIqp2d/aoTal 5HeQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=3Nw4hSmQCvYiX6I3ag5JvibMizxAkPXB+QIRbA2ooTk=; b=j3LGDwi8czvxjDe7tY4ybzeUmWEMhJj+wfvyHwYWpQExnxuZC8OFnLQBpK08aIAPWQ c9Cl8xFf3M38wmolk5+ys+ZBhmIqB0pCFFhy451vXvrly1wUg54KaISkqgnR0jdZzWw4 6BVxngGrtvbN5c4+u8kYh4L/YmIivV/etiNHd5in1yMZOb/Nrhrv1FxqYOVCuaEtKs6t ezaHqzYf8imjRQhOy1vorXmZ9QHYCqGO9GIQkF/FqnNxywnHJYPQEinMY0JJKSV+OU7v BIZUYPSqRvRjgxDhYo8z1/WiPaOTMAmya7KUVYCosakPy2Dk7c07SzNf/ArwxAOo44Kd jPug==
X-Gm-Message-State: AGi0PuYAW5jWdlKeI+I8IHCk2a5EMRyzRh3k1lxdVdWpX0puldqugFwD iDgEpO4S7hAuXz174O5b5YKzjUo7IHbY3aiAp8e6eTdV
X-Google-Smtp-Source: APiQypKYxxbo1NehPvBocDClep81lWPTf9TKJ5z0NgL7Y08D+RQrvoQLFITJVJXSdSHhGe4IxH/eALDOUPQjzP8No5g=
X-Received: by 2002:ac8:764e:: with SMTP id i14mr9162096qtr.191.1587498419636; Tue, 21 Apr 2020 12:46:59 -0700 (PDT)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: Richard Barnes <>
Date: Tue, 21 Apr 2020 15:46:37 -0400
Message-ID: <>
To: Joel Alwen <>
Cc: Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="00000000000062633b05a3d24729"
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:47:39 -0000

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


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.
> 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