Subject: [MLS] Improving entropy in MLS

From: Konrad Kohbrok <[email-masked]>
Date: Tue, 30 Mar 2021 09:27:31 +0200 (CEST)

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

---

From: Benjamin Beurdouche <[email-masked]>
Date: Tue, 30 Mar 2021 09:53:24 +0200

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 <[email-masked]> wrote:
> 
> Hi everyone,
> 
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Benjamin Beurdouche <[email-masked]>
Date: Tue, 30 Mar 2021 09:54:48 +0200

*ouch, sorry about all the spelling mistakes… :D

> On 30 Mar 2021, at 09:53, Benjamin Beurdouche <[email-masked]> wrote:
> 
> Hi all,
>

---

From: Konrad Kohbrok <[email-masked]>
Date: Tue, 30 Mar 2021 11:25:10 +0200 (CEST)

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 <[email-masked]> hat am 30.03.2021 09:53 geschrieben:
> 
>  
> Hi all,
>

---

From: Brendan McMillion <[email-masked]>
Date: Tue, 30 Mar 2021 14:01:13 -0700

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 <[email-masked]>
wrote:

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

---

From: Benjamin Beurdouche <[email-masked]>
Date: Tue, 30 Mar 2021 23:33:57 +0200

This is definitely a good argument against, I agree.

> On Mar 30, 2021, at 11:01 PM, Brendan McMillion <[email-masked]> wrote:
> 
> 
> 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 <[email-masked]> wrote:

---

From: Konrad Kohbrok <[email-masked]>
Date: Wed, 31 Mar 2021 09:41:28 +0200 (CEST)

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 <[email-masked]> hat am 30.03.2021 23:01 geschrieben:
> 
> 
> Hey Konrad
>

---

From: Franziskus Kiefer <[email-masked]>
Date: Wed, 31 Mar 2021 09:55:58 +0200

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 <[email-masked]>
wrote:

> 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
>
> > 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
> > >  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.
> > >
> > >  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
> > >  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
> > >  > E.g., not directly accessible, and behind an interface that an
> adversary can query for certain operations
> > >  > > 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:
> > >  > > 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
> > >  > > 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 (

---

From: Konrad Kohbrok <[email-masked]>
Date: Wed, 31 Mar 2021 11:04:12 +0200 (CEST)

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

> Franziskus Kiefer <[email-masked]> 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
> 
> On Wed, 31 Mar 2021 at 09:41, Konrad Kohbrok <[email-masked]> wrote:
> > Hi Brendan,
> >