Re: [MLS] hardening MLS against bad randomness
Christopher Wood <caw@heapingbits.net> Tue, 21 April 2020 19:37 UTC
Return-Path: <caw@heapingbits.net>
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 0B3E53A08C1
for <mls@ietfa.amsl.com>; Tue, 21 Apr 2020 12:37:44 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.1
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key)
header.d=heapingbits.net header.b=eTVwcGZ/;
dkim=pass (2048-bit key)
header.d=messagingengine.com header.b=jG1w3Yqm
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 D4wfZOyM7tEx for <mls@ietfa.amsl.com>;
Tue, 21 Apr 2020 12:37:31 -0700 (PDT)
Received: from out3-smtp.messagingengine.com (out3-smtp.messagingengine.com
[66.111.4.27])
(using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 163C23A088D
for <mls@ietf.org>; Tue, 21 Apr 2020 12:37:30 -0700 (PDT)
Received: from compute1.internal (compute1.nyi.internal [10.202.2.41])
by mailout.nyi.internal (Postfix) with ESMTP id F0BF65C007C
for <mls@ietf.org>; Tue, 21 Apr 2020 15:37:29 -0400 (EDT)
Received: from imap7 ([10.202.2.57])
by compute1.internal (MEProxy); Tue, 21 Apr 2020 15:37:29 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=heapingbits.net;
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=
messagingengine.com; 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: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-dev0-351-g9981f4f-fmstable-20200421v1
Mime-Version: 1.0
Message-Id: <6c40ac86-5861-4617-97c8-fa960f66943f@www.fastmail.com>
In-Reply-To: <717aea51-d03b-c555-3863-a7b2b7a0eed6@wickr.com>
References: <717aea51-d03b-c555-3863-a7b2b7a0eed6@wickr.com>
Date: Tue, 21 Apr 2020 12:37:09 -0700
From: "Christopher Wood" <caw@heapingbits.net>
To: mls@ietf.org
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/zEB2dSvqHdzgcRhWTYGW7j1Fw9A>
Subject: Re: [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: 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. Best, Chris 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 > MLS@ietf.org > https://www.ietf.org/mailman/listinfo/mls >
- [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)