Re: [MLS] Improving entropy in MLS

Konrad Kohbrok <konrad.kohbrok@datashrine.de> Wed, 31 March 2021 09:04 UTC

Return-Path: <konrad.kohbrok@datashrine.de>
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 39AE93A20F1 for <mls@ietfa.amsl.com>; Wed, 31 Mar 2021 02:04:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Level:
X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 907WYzl2AGwM for <mls@ietfa.amsl.com>; Wed, 31 Mar 2021 02:04:24 -0700 (PDT)
Received: from mout-p-201.mailbox.org (mout-p-201.mailbox.org [IPv6:2001:67c:2050::465:201]) (using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 845093A20F0 for <mls@ietf.org>; Wed, 31 Mar 2021 02:04:24 -0700 (PDT)
Received: from smtp1.mailbox.org (smtp1.mailbox.org [IPv6:2001:67c:2050:105:465:1:1:0]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-384) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mout-p-201.mailbox.org (Postfix) with ESMTPS id 4F9L3S3FkPzQk1W; Wed, 31 Mar 2021 11:04:20 +0200 (CEST)
X-Virus-Scanned: amavisd-new at heinlein-support.de
Received: from smtp1.mailbox.org ([80.241.60.240]) by spamfilter06.heinlein-hosting.de (spamfilter06.heinlein-hosting.de [80.241.56.125]) (amavisd-new, port 10030) with ESMTP id 7h0IipbeFZ-j; Wed, 31 Mar 2021 11:04:13 +0200 (CEST)
Date: Wed, 31 Mar 2021 11:04:12 +0200 (CEST)
From: Konrad Kohbrok <konrad.kohbrok@datashrine.de>
To: Franziskus Kiefer <franziskuskiefer@gmail.com>
Cc: ML Messaging Layer Security <mls@ietf.org>, Brendan McMillion <brendan@cloudflare.com>, Benjamin Beurdouche <benjamin.beurdouche@inria.fr>
Message-ID: <596405221.416.1617181452901@office.mailbox.org>
In-Reply-To: <CAJowLmNOOmeaLONAu62wzdTGK=p340mLugo6gZ0k9C1ngotNsA@mail.gmail.com>
References: <1529628012.30519.1617089251424@office.mailbox.org> <DBED46A1-F3E3-4C79-B9C5-B13088F7B20D@inria.fr> <965197897.32483.1617096310176@office.mailbox.org> <CABP-pSRLXdiowmd-GO601fj3SLqVJAq92ULOsMCKi-9aVS12Eg@mail.gmail.com> <535299944.41006.1617176490395@office.mailbox.org> <CAJowLmNOOmeaLONAu62wzdTGK=p340mLugo6gZ0k9C1ngotNsA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Priority: 3
Importance: Normal
X-MBO-SPAM-Probability:
X-Rspamd-Score: -7.65 / 15.00 / 15.00
X-Rspamd-Queue-Id: 154811860
X-Rspamd-UID: bcf82f
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/mKMjCezF9Ub8bm2pZUJizte5D2g>
Subject: Re: [MLS] Improving entropy in MLS
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: Wed, 31 Mar 2021 09:04:29 -0000

Hi Franziskus,

Fundamentally, I believe that bad entropy is something we should address in the spec and our PR is just one way to do that. Having an external document which we then reference from the spec would be another way, if that is what the WG prefers.

Regarding an instantiation of G'(n) as recommended by [1]: It's certainly a good idea and including this in the entropy considerations is something we should do. It should work nicely with the entropy pool as well.

I just want to point out that implementing the approach of [1] and having an entropy pool is not quite the same. [1] proposes we leverage the existence of a long-term secret key (which potentially resides in an HSM or similar) to improve entropy, where our proposal does two different things: 1) it introduces an entropy pool and 2) it allows the  injection of secrets from a party's groups (which in turn originate from other parties).

Again, we should consider doing all of that, but the approaches are not the same.

Konrad

[1] https://eprint.iacr.org/2018/1057


> Franziskus Kiefer <franziskuskiefer@gmail.com> hat am 31.03.2021 09:55 geschrieben:
> 
> 
> Hi Konrad, all
> 
> I agree with Benjamin and Brendan that the protocol is not the right place for something like this.
> Since you already mention [1], don't you think it would be better to recommend that implementations use RFC 8937 [2] and give an example of how to instantiate G'(n)?
> 
> Best,
> Franziskus
> 
> [1] https://eprint.iacr.org/2018/1057
> [2] https://www.rfc-editor.org/rfc/rfc8937.html 
> 
> 
> On Wed, 31 Mar 2021 at 09:41, Konrad Kohbrok <konrad.kohbrok@datashrine.de> wrote:
> > Hi Brendan,
> >  
> >  Thanks for your feedback! You make two good arguments here, that I want to address independently.
> >  
> >  The first is the maintenance of layers of abstraction. Yes, ultimately, we'd like to be able to rely on the OS's (CSP)RNG, but events in the past (see the introduction of [1] for a few examples) have shown that they are not always too reliable. As a consequence, protocols should be designed to be robust against bad sources of randomness. In particular, our design allows the inclusion of "remote" sources of randomness, which is something the OS's RNG can't provide. In addition, I'd like to mention that we're not intending to replace the OS's RNG, but rather complement it. Note, that the design ensures that no secret can be extracted from the pool without retrieving fresh randomness from the OS's RNG.
> >  
> >  This brings me to the second point, where I agree that we should keep MLS free from unnecessary complexity that makes it more prone to bugs and you're right in that the source of randomness is a particularly fundamental and thus vulnerable part of MLS. However, the design is conceivably simple and uses the same, tried, tested and provably secure mechanism that is used in the key schedule of TLS and MLS: a simple extract-expand cycle. See [2] for a security proof of the MLS key schedule, which can easily be adapted to the design of the entropy pool.
> >  
> >  To summarize, we're not proposing to replace the OS's RNG, but rather extend it such that additional sources of entropy can be included. The mechanism is simple and, in my opinion, reasonably easy to review, implement and prove secure without additional assumptions.
> >  
> >  Cheers,
> >  Konrad
> >  
> >  [1] https://eprint.iacr.org/2018/1057
> >  [2] https://eprint.iacr.org/2021/137
> >  
> >  
> >  > Brendan McMillion <brendan@cloudflare.com> hat am 30.03.2021 23:01 geschrieben:
> >  > 
> >  > 
> >  > Hey Konrad
> >  > 
> >  > Thanks for writing this up. However, I feel pretty strongly opposed to this idea, just as a matter of maintaining proper layers of abstraction. MLS implementations aren't remotely the only things on a user's system that require strong randomness, which is why every OS has its own CSPRNG. Those CSPRNGs are going to be much more robust, better designed, and thoroughly audited than anything we'd implement. Instead, it's more likely we'd have MLS implementations do this incorrectly and introduce more randomness-related vulnerabilities than we prevented.
> >  > 
> >  > 
> >  > 
> >  > On Tue, Mar 30, 2021 at 2:25 AM Konrad Kohbrok <konrad.kohbrok@datashrine.de> wrote:
> >  > > Great questions. I really should have included our thoughts on the threat model.
> >  > > 
> >  > > We don't assume the entropy pool to be more protected than any other secret in MLS.
> >  > > 
> >  > > Functionally, we want the pool to allow the following: 
> >  > > - a party should be able to accrue entropy over time using the OS's RNG
> >  > > - a party should be able to inject entropy from other sources (in particular secrets derived from the epoch_secret of any of the party's groups whenever a fresh commit comes in)
> >  > > 
> >  > > Assuming the OS's RNG is really bad (e.g. it spits out only zeroes), then a party can still have decent entropy once it receives commits from groups that it is in. Any party that wants to predict the entropy in the pool would have to know every secret that is injected into the pool. That means that an adversary would have to compromise all of the party's groups to predict secrets extracted from the entropy pool.
> >  > > 
> >  > > Of course, the pool will take some time to accrue entropy from various sources, so it doesn't help if the adversary is present from the start, but it will help if the adversary compromises a party later on. If that happens, then the compromised party can recover if the adversary misses (i.e. doesn't intercept and decrypt) any commit from another party after the compromise.
> >  > > 
> >  > > Now we have to make sure that the design doesn't give us any disadvantages over just sampling from the OS's RNG every time we need fresh randomness.
> >  > > 
> >  > > Let's assume full state compromise. Then
> >  > > 1) the adversary can't obtain entropy extracted from the pool in the past (because it's essentially a KDF-chain, just as the key schedule)
> >  > > 2) the adversary can't predict what entropy the client will extract in the future if one of the following is true:
> >  > > - the OS's RNG is good
> >  > > - a commit from a group arrives, where the group itself is not compromised
> >  > > - any other external entropy gets injected that the adversary doesn't have access to (e.g. a signature from a secret key that is kept secure in an HSM)
> >  > > 
> >  > > To summarize: It's no silver bullet against bad entropy in general, but it's cheap, no worse than just relying on the OS's RNG and provides a framework to accrue randomness over time from various sources even if the OS's RNG is bad/compromised and it allows parties to recover from compromise in that case.
> >  > > 
> >  > > Hope that shed some light on things.
> >  > > 
> >  > > Cheers,
> >  > > Konrad
> >  > > 
> >  > > 
> >  > > 
> >  > > > Benjamin Beurdouche <benjamin.beurdouche@inria.fr> hat am 30.03.2021 09:53 geschrieben:
> >  > > > 
> >  > > > 
> >  > > > Hi all,
> >  > > > 
> >  > > > I like this idea. I am not fully clear about the threat model, though.
> >  > > > 
> >  > > > From reading this, it looks like we assume that the adversary that compromised a 
> >  > > > principal doesn’t have complete control the entropy pool.
> >  > > > 
> >  > > > This is in contrast over what we assume of the AEAD keys or even the KEM keys
> >  > > > where a full state compromise will gain access to the values.
> >  > > > 
> >  > > > However it looks very close to the assumptions about additional protections for signing keys.
> >  > > > E.g., not directly accessible, and behind an interface that an adversary can query for certain operations
> >  > > > through an API (e.g. when is stored in an HSM, co-processor or a functional secure enclave).
> >  > > > 
> >  > > > Am I reading this properly?
> >  > > > If yes, I can understand the value in this threat model, but we should make it clear that the
> >  > > > entropy pool has to get these additional protections to provide these good properties.
> >  > > > 
> >  > > > Seems to me like a good improvement in all cases anyway, so I think we should consider it.
> >  > > > 
> >  > > > Thanks!
> >  > > > Ben
> >  > > > 
> >  > > > > On 30 Mar 2021, at 09:27, Konrad Kohbrok <konrad.kohbrok@datashrine.de> wrote:
> >  > > > > 
> >  > > > > Hi everyone,
> >  > > > > 
> >  > > > > MLS is a protocol that is very vulnerable to individual parties with bad randomness. For example, when a party joins a group, the secrecy of the group's key material relies on the quality of that party's key material. Similarly, when doing an external join, the groups entropy is completely replaced by that of the joining member.
> >  > > > > 
> >  > > > > There are multiple ways to mitigate this threat and Joël and Sandro proposed a few of them in the following mail to the list: https://mailarchive.ietf.org/arch/msg/mls/ZR84smU5xeLrziNTk5W1P1Z1nQI/
> >  > > > > 
> >  > > > > Concretely, there were two approaches: one that would be baked into the protocol (essentially using a secret derived from old path secrets to inject into new ones in addition to the current approach) and one that would mandate the use of an entropy pool.
> >  > > > > 
> >  > > > > The ideas were discussed a bit at the time, but nothing has happened since then. Joël, Sandro and I have just opened a PR with a concrete design for an entropy pool that is modeled after the key schedule (https://github.com/mlswg/mls-protocol/pull/467). Concretely, it allows gathering entropy over time and for parties with a bad entropy source to profit from parties with a good one without compromising security.
> >  > > > > 
> >  > > > > While for future iterations of MLS, we might want to consider a solution that is more integral to the protocol, we are aware that the authors want to avoid breaking changes at this point. With the entropy pool, we thus propose a solution that does not affect the protocol flow, but that still offers significant advantages over no mitigations at all.
> >  > > > > 
> >  > > > > Cheers,
> >  > > > > Konrad
> >  > > > > 
> >  > > > > _______________________________________________
> >  > > > > MLS mailing list
> >  > > > > MLS@ietf.org
> >  > > > > https://www.ietf.org/mailman/listinfo/mls
> >  > > 
> >  > > _______________________________________________
> >  > > MLS mailing list
> >  > > MLS@ietf.org
> >  > > https://www.ietf.org/mailman/listinfo/mls
> >  > >
> >  
> >  _______________________________________________
> >  MLS mailing list
> >  MLS@ietf.org
> >  https://www.ietf.org/mailman/listinfo/mls
> > 
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls