Subject: [MLS] Async Add

From: Raphael Robert <[email-masked]>
Date: Mon, 21 Sep 2020 20:15:10 +0200

Hi all,

Over the course of the past weeks when assessing how well MLS would fit into existing messengers, it became obvious that adding new members is still problematic. The operation – while technically asynchronous – still requires two parties to be online in many cases.

Rather than writing a lot of prose here, I attached a presentation that explains the problem and offers a potential solution.

I also created the following PR: https://github.com/mlswg/mls-protocol/pull/406
I will bring this up at the interim tomorrow for discussion.

Raphael

---

From: Joel Alwen <[email-masked]>
Date: Tue, 22 Sep 2020 15:24:35 +0200

My initial 2 cents: this is not just a corner case. MLS should specify how to
support such functionality but as an optional mode and making explicit the price
in security it entails.

I believe such a feature would be used quite a bit if it where available. E.g.
My phone is the only device on my account. It breaks. I get a new one and log
back in to my account. Now I want my re-join my old groups. In most deployments
I'd expect that to be permitted by group policies. But how can I re-join w/o the
help of someone else in the group actively "pulling" me in? If I'm not mistaken
then this PR provides an answer.

The solution does come with a price though. Some things that come to mind:

 - It seems to require storing public group state on the DS (or some other
server) which isn't great for E2E metadata protection.

 - An external commit provides weaker security guarantees than a normal commit.
It throws out the old init_secret. Ergo, if ever an HPKE sk to which one of the
UpdatePath secrets was encrypted to leaks then the entire application key
schedule of the new epoch is compromised. (Not to mention that further epochs
may also be compromised depending on the particulars of the execution.) For
normal commits that's not the case because the adv. also needs the old epoch's
init_secret.

- Joël

On 21/09/2020 20:15, Raphael Robert wrote:
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Richard Barnes <[email-masked]>
Date: Tue, 22 Sep 2020 10:56:14 -0400

Thanks for posting this, Raphael.  I agree with Joël that this is a feature
that is likely to get some use.  And the PR is pleasantly short (though I
think it might need a bit more elaboration).

On the topic of entropy from the last epoch, I'm wary of the current
all-zero approach.  It seems like there are at least two other approaches
available:

a. "Public init secret" - Alongside the regular init secret, derive a
"public init secret" from the key schedule.  Then use this as the init
secret for external commits.

b. "Init with KEM" - You could generate a key pair off of the key schedule,
use some KEM-based operations to derive the next init secret.  In the early
days of MLS, we used DH for this.  Nowadays, we're KEM-only, but I think
the HPKE exporter might be pressed into serving a similar purpose.

Looking forward to the discussion...

--RLB

On Tue, Sep 22, 2020 at 9:24 AM Joel Alwen <[email-masked]> wrote:

> > Over the course of the past weeks when assessing how well MLS would fit
> into existing messengers, it became obvious that adding new members is
> still problematic. The operation – while technically asynchronous – still
> requires two parties to be online in many cases.
> >
> > Rather than writing a lot of prose here, I attached a presentation that
> explains the problem and offers a potential solution.
> >
> > I also created the following PR:
> https://github.com/mlswg/mls-protocol/pull/406

---

From: Brendan McMillion <[email-masked]>
Date: Tue, 22 Sep 2020 08:08:54 -0700

>
> b. "Init with KEM" - You could generate a key pair off of the key
> schedule, use some KEM-based operations to derive the next init secret.
>

This is a really smart idea and seems like it wouldn't break PCS of the
group like the initial proposal or a public init secret would

On Tue, Sep 22, 2020 at 7:56 AM Richard Barnes <[email-masked]> wrote:

> Thanks for posting this, Raphael.  I agree with Joël that this is a
> feature that is likely to get some use.  And the PR is pleasantly short
> (though I think it might need a bit more elaboration).
>
> b. "Init with KEM" - You could generate a key pair off of the key
> schedule, use some KEM-based operations to derive the next init secret.  In
> the early days of MLS, we used DH for this.  Nowadays, we're KEM-only, but
> I think the HPKE exporter might be pressed into serving a similar purpose.
>

---

From: Richard Barnes <[email-masked]>
Date: Tue, 22 Sep 2020 13:21:18 -0400

To expand on what I said on the call: My proposal would be that we use the
HPKE exporter function

https://github.com/cfrg/draft-irtf-cfrg-hpke/blob/master/draft-irtf-cfrg-hpke.md#secret-export-hpke-export

So the scheme you would end up with would be something like:

init_priv = KEM.DeriveKeyPair(erstwhile_init_secret)
enc, ctx = SetupBaseS(init_priv.public_key, "") // on the send side
ctx = SetupBaseR(enc, init_priv, "") // on the receive side
init_secret = ctx.Export("mls 1.0 init", secret_size)

That "enc" value is the additional data that needs to be conveyed from the
sender to the receivers.  I'm sympathetic to Brendan's argument that if
this is good enough, we should just do it all the time.  What is missing
for me is an understanding of how the following two transformations relate:

epoch_secret --DeriveSecret-> init_secret
epoch_secret --DeriveSecret-> erstwhile_init_secret --DeriveKeyPair->
init_priv --SetupBase{skE},Export-> init_secret

(Aside from the latter involving a lot more steps!) Either way you have
transformed one secret to another; in the latter case, it is also available
to whomever holds skE.

--RLB

On Tue, Sep 22, 2020 at 11:09 AM Brendan McMillion <[email-masked]>
wrote:

>>> > Over the course of the past weeks when assessing how well MLS would
>>> fit into existing messengers, it became obvious that adding new members is
>>> > Rather than writing a lot of prose here, I attached a presentation
>>> that explains the problem and offers a potential solution.
>>> >

---

From: Joel Alwen <[email-masked]>
Date: Wed, 23 Sep 2020 12:43:03 +0200

Unfortunately, I missed the call so I hope I'm not repeating / misunderstanding
anything you've all figured out already.

I think Richards extension to Raphael's suggestion is super sweet for external
commits! To save space (and for lack of better terminology) I'll call that
version of a commit AEC for "asymmetric external commit".

> if this is good enough, we should just do it all the time.

If by "all the time" you mean replacing our normal internal commits with AEC I'm
not following.

AEC (necessarily) doesn't ensure the committer knows the old epoch's key
schedule. In other words it doesn't ensure committer is part of the group.
However for "internal" commits it make sense to require this as a security
property. As it stands now MLS does provide that guarantee via the
confirmation_tag. (And we have a PR in the works to guarantee the same thing for
Proposals via a membership_tag.) But if we switch to AEC also for internal
commits we loose that guarantee. Maybe I just misunderstood what "all the time"
means...

I'm also not sure why we'd want to switch from a few calls to symmetric
primitives (HMAC) to 2 asymmetric ones (DH in HPKE) if we don't have to. Whats
would we be buying at the cost of increased computation (and bandwidth for
commit packets)?

> init_secret = ctx.Export("mls 1.0 init", secret_size)

I'm not a fan of using (erstwhile_)init_secret both as coins (i.e. random bits)
for generating HPKE keys and as input to HKDF to derive (new_)joiner_secret.
More key/coins separation would be "healthy" at least from a provability
perspective.

Thing is, no standard security notion for PKE would allow reusing the coins from
keygen this (or any other) way. So if MLS does that it would make proving
security for MLS impossible based on some standard security of HPKE (say
IND-CCA). Normally, such a proof would turn an MLS attacker into an HPKE
attacker. But MLS would give the attacker extra data about the coins used in
keygen not available in the HPKE security game. So I dont see how to turn the
MLS attacker in to an IND-CCA attacker for HPKE.

We might consider deriving init_priv in a similar way as we do node keys. Namely
by having separate coins (node_secret) and a secret used for further derivation
purposes (path_secret). How about this?

init_coins = DeriveSecret(erstwhile_epoch_secret, "coins")
init_priv = KEM.DeriveKeyPair(init_coins)

- Joël

> sender to the receivers.  I'm sympathetic to Brendan's argument that if this is
> good enough, we should just do it all the time.  What is missing for me is an
> understanding of how the following two transformations relate:
> 
> epoch_secret --DeriveSecret-> erstwhile_init_secret --DeriveKeyPair-> init_priv
> --SetupBase{skE},Export-> init_secret
> 
> transformed one secret to another; in the latter case, it is also available to
> whomever holds skE.
> 
> --RLB
> 
> 
> 
> On Tue, Sep 22, 2020 at 11:09 AM Brendan McMillion <[email-masked]
> <mailto:[email-masked]>> wrote:
> 
>     On Tue, Sep 22, 2020 at 7:56 AM Richard Barnes <[email-masked]
>     <mailto:[email-masked]>> wrote:
> 
>         all-zero approach.  It seems like there are at least two other
>         approaches available:
> 
>         In the early days of MLS, we used DH for this.  Nowadays, we're
>         KEM-only, but I think the HPKE exporter might be pressed into serving a
>         similar purpose.
> 
>         On Tue, Sep 22, 2020 at 9:24 AM Joel Alwen <[email-masked]
>         <mailto:[email-masked]>> wrote:
> 
>             > Over the course of the past weeks when assessing how well MLS
>             would fit into existing messengers, it became obvious that adding
>             new members is still problematic. The operation – while technically
>             asynchronous – still requires two parties to be online in many cases.
>             >
>             > [email-masked] <mailto:[email-masked]>
>             [email-masked] <mailto:[email-masked]>
>         [email-masked] <mailto:[email-masked]>

---

From: Richard Barnes <[email-masked]>
Date: Wed, 23 Sep 2020 10:09:32 -0400

Glad you like it!

I think your point about not doing it all the time is pretty good.
Everything else aside, it's a lot more computation.  The main drawback to
not doing it all the time is that we need extra syntax for the AEC case,
and switching logic.  So you're trading all-the-time computation for the
logic to switch between the AEC and non-AEC cases.

Hopefully that won't be too complex.  As I mentioned on the call, I think
we can just do this with a new proposal, something like:

struct {
    opaque encapsulated_key<0..2^16-1>;
} ExternalInit;

On receiving a commit with this proposal type, you would change from using
the normal init_secret to deriving it from the encapsulated key.  The
bigger complexity comes from expressing how this proposal is used -- you
would really only want it in the specific case that (a) it comes with an
Add proposal and a Commit, (b) all three are signed with the new joiner's
key, and (c) the Commit covers only the Add and ExternalInit.

W.r.t. the erstwhile_init_secret -- yeah, definitely agree that we should
derive a separate secret for this (external_init_secret?).  So the bottom
of the key schedule diagram will basically have a loop on it, where one
path is epoch->init, and the other is
epoch->external_init->external_init_key_pair->init.

GroupContext_[n] -> KDF.Extract = epoch_secret
                        |
                        +--> DeriveSecret(., "ext init") --+
                        |    = external_init_secret        |
                        |                                  |
                        V                                  V
                  DeriveSecret(., "init")           DeriveKeyPair(.)
                        |                                  | =
external_init_key_pair
                        |                                  |
                        |                                  V
                        |                         HPKE.SetupBaseS(enc, .)
                        |                                  |
                        |                                  V
                        |                    CTX.Export("mls 1.0 ext init",
{})
                        |                                  |
                        |<---------------------------------+
                        |
                        V
                  init_secret_[n]

On Wed, Sep 23, 2020 at 6:43 AM Joel Alwen <[email-masked]> wrote:

> this is
> >             My initial 2 cents: this is not just a corner case. MLS
> should
> >             specify how to
> >             I believe such a feature would be used quite a bit if it
> where
> >             available. E.g.
> >             My phone is the only device on my account. It breaks. I get
> a new
> >             one and log
> >             back in to my account. Now I want my re-join my old groups.
> In most
> >             deployments
> >             I'd expect that to be permitted by group policies. But how
> can I
> >             re-join w/o the
> >             help of someone else in the group actively "pulling" me in?
> If I'm
> >             not mistaken
> >             The solution does come with a price though. Some things that
> come to
> >             mind:
> >
> >              - It seems to require storing public group state on the DS
> (or some
> >             other
> >              - An external commit provides weaker security guarantees
> than a
> >             normal commit.
> >             It throws out the old init_secret. Ergo, if ever an HPKE sk
> to which
> >             one of the
> >             schedule of the new epoch is compromised. (Not to mention
> that
> >             further epochs
> >             normal commits that's not the case because the adv. also
> needs the
> >             old epoch's
> >             init_secret.
> >
> >
> >             - Joël
> >