Re: [MLS] Improving entropy in MLS

[Joel Alwen <[e-mail]>]

Hey People,

In principle modularity is definitely worth going for. The counter points though
are "defense in depth" and "minimize your assumptions". Yes, the OS/cryptolib
*should* provide good entropy. But we can still design protocols to minimize
their dependce on that service.

Other's have faced this issue in the past. Compare the ECDSA's strong dependency
on external entropy when signing to that of the newer sig scheme EdDSA which
requires none. It is precisely this *unnecessary* vuln in ECDSA that was
exploited to break the PS3's security. Lessons we're learnt and thats how we
ended up with EdDSA. The goal of this PR is to not make the same mistake with MLS.



But modularity aside, its also not totally clear to me how the PR's mechanism
would work as an external solution because it also feeds in entropy from ongoing
MLs sessions. Here the solution benefits from ensuring that both A) entropy
derived off the MLS session is never used for any other prupose and B) entropy
is absorbed once for each epoch. (More often would be fine too but less
efficient with no security improvement. Less would offer weaker security.)

To simulate the same security benefits with an external entropy pool (e.g. in
the OS or cryptolib) you'd want to reproduce both A) and B) since they both help
with security. A) is possible but potentially rather non-trivial if you want to
use exporter keys (and i'm not sure there's any other way to do it). Meanwhile
the PR, being an internal solution, has lower-level access to the key schedule
so it can trivially insure A) by defining a unique prefix to the HKDF for this
purpose e.g. automatically seperating the output away from all exported keys.
Ensuring B) doesn't look completely straightforward to me either. A "polling"
based solution seems pretty imperfect & less-efficient to me. An alternative
would be to have clients notify external services whenever a new commit has just
been processed but is that really what we want? Even commits containing only
update (or even no) proposals? (Not to mention is that even really an "external"
solution...)


Any way, I'm not saying I think there is no *possible* external solution. Just
that the mechanisms in the PR seem more aligned with an internal one built into
the MLS implementation rather than bolted on after the fact, especially in some
code that doesn't even "know" about MLS at all.

- Joël


On 31/03/2021 09:55, Franziskus Kiefer wrote:
> 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 <https://eprint.iacr.org/2018/1057>
> [2] https://www.rfc-editor.org/rfc/rfc8937.html
> <https://www.rfc-editor.org/rfc/rfc8937.html>
>
> On Wed, 31 Mar 2021 at 09:41, Konrad Kohbrok <[e-mail]
> <mailto:[e-mail]>> 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 <https://eprint.iacr.org/2018/1057>
>     [2] https://eprint.iacr.org/2021/137 <https://eprint.iacr.org/2021/137>
>
>
>     > Brendan McMillion <[e-mail] <mailto:[e-mail]>>
>     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
>     <[e-mail] <mailto:[e-mail]>> 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 <[e-mail]
>     <mailto:[e-mail]>> 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
>     <[e-mail] <mailto:[e-mail]>> 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/
>     <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
>     <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
>     > >  > > [e-mail] <mailto:[e-mail]>
>     > >  > > https://www.ietf.org/mailman/listinfo/mls
>     <https://www.ietf.org/mailman/listinfo/mls>
>     > >
>     > >  _______________________________________________
>     > >  MLS mailing list
>     > >  [e-mail] <mailto:[e-mail]>
>     > >  https://www.ietf.org/mailman/listinfo/mls
>     <https://www.ietf.org/mailman/listinfo/mls>
>     > >
>
>     _______________________________________________
>     MLS mailing list
>     [e-mail] <mailto:[e-mail]>
>     https://www.ietf.org/mailman/listinfo/mls
>     <https://www.ietf.org/mailman/listinfo/mls>
>
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>


On 31/03/2021 09:55, Franziskus Kiefer wrote:
> 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 <https://eprint.iacr.org/2018/1057>
> [2] https://www.rfc-editor.org/rfc/rfc8937.html
> <https://www.rfc-editor.org/rfc/rfc8937.html>
> 
> On Wed, 31 Mar 2021 at 09:41, Konrad Kohbrok <[e-mail]
> <mailto:[e-mail]>> 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 <https://eprint.iacr.org/2018/1057>
>     [2] https://eprint.iacr.org/2021/137 <https://eprint.iacr.org/2021/137>
> 
> 
>     > Brendan McMillion <[e-mail] <mailto:[e-mail]>>
>     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
>     <[e-mail] <mailto:[e-mail]>> 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 <[e-mail]
>     <mailto:[e-mail]>> 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
>     <[e-mail] <mailto:[e-mail]>> 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/
>     <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
>     <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
>     > >  > > [e-mail] <mailto:[e-mail]>
>     > >  > > https://www.ietf.org/mailman/listinfo/mls
>     <https://www.ietf.org/mailman/listinfo/mls>
>     > > 
>     > >  _______________________________________________
>     > >  MLS mailing list
>     > >  [e-mail] <mailto:[e-mail]>
>     > >  https://www.ietf.org/mailman/listinfo/mls
>     <https://www.ietf.org/mailman/listinfo/mls>
>     > >
> 
>     _______________________________________________
>     MLS mailing list
>     [e-mail] <mailto:[e-mail]>
>     https://www.ietf.org/mailman/listinfo/mls
>     <https://www.ietf.org/mailman/listinfo/mls>
> 
> 
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>