Re: [MLS] Async Add

Joel Alwen <> Wed, 23 September 2020 10:43 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 9BB0F3A0F5F for <>; Wed, 23 Sep 2020 03:43:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, NICE_REPLY_A=-0.001, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id QDSu9rlGODTF for <>; Wed, 23 Sep 2020 03:43:07 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::62c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 488373A0F59 for <>; Wed, 23 Sep 2020 03:43:07 -0700 (PDT)
Received: by with SMTP id p9so27068619ejf.6 for <>; Wed, 23 Sep 2020 03:43:07 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=subject:to:cc:references:from:autocrypt:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=jU7a/Z6YeZnVIFlUsyDOH4eh8FJN1ztI64nEyRxxB64=; b=L4dju+zphU/XVTdRS8wKMeNchW3tx6Vd8luMYPAYNJLJMV1txvf2oSIv44V1l4tbEm pSuDa+dC9iNlr5j1Rwnlyf85l2iOpqYnHBEenTfbnp959ijTK2eXV73Me9vNHxKxIA4O yiOeR0kQrOTVmJfYxIN7cJksB/V1gF9L3Mwv2BZxUA+hujPAHe+TAizkt68QyoJMmRQF ClN9sY9FhTmWHJaM5WBB8NRqBdPicsBuNo+kK0WqvM/MxE5ol96Jdhpxl/k2x8RjNwhV zcWLdUVqBdIRJYG/f6Qqz0Ad0AUMhWHqfQvuPxQZb1wdjpfhn26RfYdpNbXR4E44IUCD 22wA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:autocrypt :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=jU7a/Z6YeZnVIFlUsyDOH4eh8FJN1ztI64nEyRxxB64=; b=giNw6cE2eqhlgJVrEIK4zC8wU3WWOmxhFzysxG2e5sLnpe324W31r2SGLrqhf5IMP9 72HG0IQ/EaUfcQWO6+h0CpuNm1PNML9IsgffMIjSPxyMXEaA+QcwDKqZLG1/6X0ByCyh Ekb4X73eMt96P1NvziJWHF33dPfAwRxr2xD11I9rf+REnT9WpNOj602/acgYfILDPo2q 4s63RftT6dbdYx+/ueV3mklbMTaFJnu5o4M/q/tTeRHsX9Ef7VM6+W3eox33kAqms+cL 8n7G45EWM+rsq8QJrFAOc5C/DjnqqhAsTQ6NmDeRTM3S6IPe+Vy7YwkJ4gxV4jKwIKH8 xfJA==
X-Gm-Message-State: AOAM530XxGAHAcpoWxy93mj61Y+Tl2PDcNt/1IU2VT+I9mZmmB05bNbF rlxhDy12jMyckiqL/kDaZ8X/WufQ9twzIGGv
X-Google-Smtp-Source: ABdhPJyYpMrf01Ha1quM1enPIXeSfKv3WJ48u1GCbRPvJU/pmYd2PKlPkkpozbA8RBOcEE1+RWNNyA==
X-Received: by 2002:a17:906:cb98:: with SMTP id mf24mr10035354ejb.90.1600857784998; Wed, 23 Sep 2020 03:43:04 -0700 (PDT)
Received: from [] ( []) by with ESMTPSA id bo8sm13955672edb.39.2020. (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 23 Sep 2020 03:43:04 -0700 (PDT)
To: Richard Barnes <>, Brendan McMillion <>
Cc: Messaging Layer Security WG <>
References: <> <> <> <> <>
From: Joel Alwen <>
Autocrypt:; keydata= mQENBFyIZvABCAC65JupY1w7gzhhNo41ftIk09n7Lid9p31jDR8Jefv9R5sWL+HZFGDeABAY 1J1JvV6vOaMsfdy9iUFfGS1GhMJ3+mh799SIsB3JSfPq/eq6Jut57D2yPtILmc7ZbuJyBHg0 xuYfKCQQAYikW+v2LJQU1Y+BUDbVldpzxSc8Z3PPSfunWdzhY6qAAhyCv+Y8EzJlQivMwD5B f6737krf8SoBsjsqCHQrRo/r+BSj5Wtd5/K3FkmWLOUAFoYK23+cpoFntGJKZfss27gDPhyS gX9ibXcBGQqBEF4qDPEzEHK8iQmXTxLul5Y7lQ6ADf69xH15WM4GmRBeCvR3Uanxcr2/ABEB AAG0HUpvZWwgQWx3ZW4gPGphbHdlbkB3aWNrci5jb20+iQFUBBMBCAA+FiEEYFNg9IH2SV6e 03O3FR5tDZv8eygFAlyIZvICGwMFCQHhM4AFCwkIBwIGFQoJCAsCBBYCAwECHgECF4AACgkQ FR5tDZv8eyjSywgApQNIRcL4IKTJ0I4XwcQRhICu1Bht3c2fUnG2YziJXjGf6DZ49uKKtuIu fk8mNS+vKRLoLZ7+u+Pv/Yjmk8jtrr6Saz1vnfsle3GgmXG5JaKOM5cOfeo5JnlNUP3QonR7 LMZwY1qVKg2mzNmwi0jG1zIGgQ5fiAwqe+YTNFli5bc/H1O9LcSmbrLV9OyucARq11DIiAvU fDknZ17OahQls+9mgfAXH5vZjzo296tYvzkOJQ2A6GPxdMHIXGbJM/vjuMe2QJl6C0zaqOtm JvFcx/HpNhmugYI9OsNAd7846HASDp8BKyfY5FYP7bn0/JBuCpg18Aykru6xyFjG3gv0Lw==
Message-ID: <>
Date: Wed, 23 Sep 2020 12:43:03 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.12.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <>
Subject: Re: [MLS] Async Add
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 23 Sep 2020 10:43:10 -0000

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"

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

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 <
> <>> 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 <
>     <>> 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 <
>         <>> 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:
>             > I will bring this up at the interim tomorrow for discussion.
>             >
>             > Raphael
>             >
>             >
>             > _______________________________________________
>             > MLS mailing list
>             > <>
>             >
>             >
>             _______________________________________________
>             MLS mailing list
>    <>
>         _______________________________________________
>         MLS mailing list
> <>