Re: [MLS] Async Add

[Richard Barnes <[e-mail]>]

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 <[e-mail]> wrote:

> 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)?
>
> > 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)
>
> 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
>
>
>
> > 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 <
> [e-mail]
> > <mailto:[e-mail]>> wrote:
> >
> >         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 <[e-mail]
> >     <mailto:[e-mail]>> 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).
> >
> >         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 <[e-mail]
> >         <mailto:[e-mail]>> wrote:
> >
> >             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:
> >             > 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
> >             >
> >             >
> >             > _______________________________________________
> >             > MLS mailing list
> >             > [e-mail] <mailto:[e-mail]>
> >             > https://www.ietf.org/mailman/listinfo/mls
> >             >
> >
> >             _______________________________________________
> >             MLS mailing list
> >             [e-mail] <mailto:[e-mail]>
> >             https://www.ietf.org/mailman/listinfo/mls
> >
> >         _______________________________________________
> >         MLS mailing list
> >         [e-mail] <mailto:[e-mail]>
> >         https://www.ietf.org/mailman/listinfo/mls
> >
>