Subject: [MLS] Proposals for handling concurrent messages

From: "M.A.L. Weidner" <[email-masked]>
Date: Tue, 19 Mar 2019 22:33:10 +0000

Dear MLS Working Group,

I've attached a document that details some proposals for how to better handle concurrent messages; see mainly Section 2.

The basic idea is to use some operator * which "combines" key pairs.  E.g., for Diffie-Hellman keys, (x, g^x) * (y, g^y) = (x + y (mod |g|), g^x g^y).

With this operator, we can combine concurrent updates.  E.g., if a updates with x and b updates with y, then the tree changes by: (embedded image)
With some extra effort, I believe we can even support concurrent Adds (Section 3.3).

My apologies if there are mistakes or if this has been discussed before.

Best,
Matthew Weidner
MPhil Student
Computer Laboratory, Cambridge

---

From: Richard Barnes <[email-masked]>
Date: Wed, 20 Mar 2019 11:23:15 -0400

Hi Matthew,

Thanks for thinking about this.  The idea has come up a few times, but it's
good to have such a thorough presentation to refer to.

I think this idea works fine if the DH / KEM group in question has a
homomorphism of the character you describe.  There's a practical problem in
that that is not universally true.  In particular, X25519 and X448 do not
have such a homomorphism: Because of the "clamping" behavior prescribed in
the RFC, it is the case that pk(a + b) != pk(a) + pk(b).  There was some
discussion on the CFRG list (after I tried to implement such a scheme):

https://mailarchive.ietf.org/arch/msg/cfrg/JVg30dldjr4pcwZ1perpA1k-OGQ

That said, if this approach were important to people, it could probably be
realized for curves that allow a homomorphism.  That would rule out
X25519/X448, but I'm told that the Ristretto adaptation of those curves
would work.  See Tony Arcieri's message on the above thread and:

https://ristretto.group/
https://tools.ietf.org/html/draft-hdevalence-cfrg-ristretto-00

And in any case, I think good old traditional Weierstrass ECDH has this
property (e.g., using the NIST curves).

I would be interested to hear folks' thoughts on whether the benefits of
reduced synchronization would be worth the costs of limiting DH group
selection (either old ECDH or new stuff without a lot of implementation).

Cheers,
--Richard

On Tue, Mar 19, 2019 at 6:33 PM M.A.L. Weidner <[email-masked]> wrote:

> Dear MLS Working Group,
>
> I've attached a document that details some proposals for how to better
> handle concurrent messages; see mainly Section 2.
>
> The basic idea is to use some operator * which "combines" key pairs.
> E.g., for Diffie-Hellman keys, (x, g^x) * (y, g^y) = (x + y (mod |g|), g^x
> g^y).
>
> With this operator, we can combine concurrent updates.  E.g., if a updates
> with x and b updates with y, then the tree changes by: (embedded image)
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Fri, 22 Mar 2019 06:00:36 +0100

Hello Matthew,

Thanks for the note. Concurrent updates was indeed one of the driving motivations for TreeKEM, so it is great to see this fleshed out.
It is also important to explicitly talk about causal ordering, I feel we have been missing discussions on this, not just for the TreeKEM part,
but also for data message transcript consistency.

One case we have been concerned about, and the main reason I didn’t recommend merging concurrency into MLS, is the following.
What guarantees do we get when leaves A and B update concurrently?
In the merged state after both these updates have been received and incorporated by all nodes,  do we have PCS against the compromise of the old keys of A and B?

In vanilla TreeKEM, the answer is no: we get PCS against one of the two old keys being compromised but not both.
However, all is not lost, if any node in the smallest subtree that includes A and B were to send a “causally dependent” update that has seen both the updates to A and B, 
the state of the tree “heals” and we have PCS against all old keys. 

Now, what is the situation with causal TreeKEM? As far as I see, it also does not protect concurrent updates against the compromise of both old keys?
And the guarantees of definition 4.1 appear only to hold for causally ordered updates, not for concurrent ones?
Is that the case? If so, I’d like to see a crisper distinction between the extra guarantees that Causal TreeKEM provides over vanilla TreeKEM.

Best,
Karthik

> On 20 Mar 2019, at 16:23, Richard Barnes <[email-masked]> wrote:
> 
> Hi Matthew,
> 
> Thanks for thinking about this.  The idea has come up a few times, but it's good to have such a thorough presentation to refer to.
> 
> I think this idea works fine if the DH / KEM group in question has a homomorphism of the character you describe.  There's a practical problem in that that is not universally true.  In particular, X25519 and X448 do not have such a homomorphism: Because of the "clamping" behavior prescribed in the RFC, it is the case that pk(a + b) != pk(a) + pk(b).  There was some discussion on the CFRG list (after I tried to implement such a scheme):
> 
> https://mailarchive.ietf.org/arch/msg/cfrg/JVg30dldjr4pcwZ1perpA1k-OGQ <https://mailarchive.ietf.org/arch/msg/cfrg/JVg30dldjr4pcwZ1perpA1k-OGQ>
> 
> That said, if this approach were important to people, it could probably be realized for curves that allow a homomorphism.  That would rule out X25519/X448, but I'm told that the Ristretto adaptation of those curves would work.  See Tony Arcieri's message on the above thread and:
> 
> https://ristretto.group/ <https://ristretto.group/>
> https://tools.ietf.org/html/draft-hdevalence-cfrg-ristretto-00 <https://tools.ietf.org/html/draft-hdevalence-cfrg-ristretto-00>
> 
> And in any case, I think good old traditional Weierstrass ECDH has this property (e.g., using the NIST curves).
> 
> I would be interested to hear folks' thoughts on whether the benefits of reduced synchronization would be worth the costs of limiting DH group selection (either old ECDH or new stuff without a lot of implementation).
> 
> Cheers,
> --Richard
> 
> On Tue, Mar 19, 2019 at 6:33 PM M.A.L. Weidner <[email-masked] <mailto:[email-masked]>> wrote:
> Dear MLS Working Group,
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>

---

From: Matthew Hodgson <[email-masked]>
Date: Fri, 22 Mar 2019 23:17:34 +0000

> On 20 Mar 2019, at 15:23, Richard Barnes <[email-masked]> wrote:
> 

On the Matrix side we are still very much hoping that MLS will somehow support reduced synchronisation, as otherwise the sequencing of membership changes acts as a very undesirable centralising force when communicating in otherwise decentralised groups. The below approach seems quite promising and from our perspective could merit picking curves which support it.

Matthew

---

From: "M.A.L. Weidner" <[email-masked]>
Date: Sat, 23 Mar 2019 18:59:32 +0000

Dear MLS Working Group,

Thanks for the feedback.  Some responses:

On Fri, Mar 22, 2019 at 5:00 AM Karthikeyan Bhargavan <[email-masked]<mailto:[email-masked]>> wrote:
Now, what is the situation with causal TreeKEM? As far as I see, it also does not protect concurrent updates against the compromise of both old keys?
And the guarantees of definition 4.1 appear only to hold for causally ordered updates, not for concurrent ones?
Is that the case? If so, I’d like to see a crisper distinction between the extra guarantees that Causal TreeKEM provides over vanilla TreeKEM.

For concurrent updates by a subgroup of users who have all been compromised, I believe Causal TreeKEM gets the same guarantees as vanilla TreeKEM.  For example, if A and B are compromised and then update concurrently, we must wait for a causally dependent update by some user in the smallest subtree containing them, as you explained for the vanilla case.  (Definition 4.1 doesn't incorporate these guarantees because I was not aware of them, so thanks for bringing them up!)

The main advantage of Causal TreeKEM comes when there are compromised and non-compromised users updating concurrently.  For example, if one of A, B, C, etc. are compromised and they all update concurrently, then the whole state is healed in Causal TreeKEM, whereas in vanilla TreeKEM this is only true if the compromised user "wins" at every conflicted node.

For another example, suppose a group partitions into two subgroups S and T, which come back together later, merging their update sets.  This could happen in an application that lets users communicate through a LAN or ad-hoc network even if they are disconnected from the global Internet, as in Haggle [1] or delay-tolerant networking.  If some users in S are compromised and then heal before re-merging with T (perhaps S is Internet-connected and thus exposed to malware while T is not), then in Causal TreeKEM, S will still be healed after the merge.  In vanilla TreeKEM, this is only true if S's updates "win" over T's updates.

I think if we want concurrent updates to heal all updating users, we need some sort of "k-party Diffie-Hellman", which is an open cryptographic problem for k > 3.  I suppose we could accomplish this by replacing conflicted nodes with blanks during concurrent updates, at the cost of increased message sizes later (devolving to O(n)-size key updates if everyone updates concurrently).

On Fri, Mar 22, 2019 at 11:17 PM Matthew Hodgson <[email-masked]<mailto:[email-masked]>> wrote:
On the Matrix side we are still very much hoping that MLS will somehow support reduced synchronisation, as otherwise the sequencing of membership changes acts as a very undesirable centralising force when communicating in otherwise decentralised groups. The below approach seems quite promising and from our perspective could merit picking curves which support it.

Now that you mention this, I noticed that for the proposals to make Adds and Removes concurrency-friendly, we actually don't need special curves.  For Adds, we only need to combine *root* secrets in an associative and commutative way, not all node key pairs.  This can be done using xor, since the root only has a secret binary string, not an asymmetric key pair.  Concurrent Removes don't require any key combining at all.  So perhaps these parts of Causal TreeKEM are worth considering independent of the proposal for concurrent updates.

On 20 Mar 2019, at 15:23, Richard Barnes <[email-masked]<mailto:[email-masked]>> wrote:
That would rule out X25519/X448, but I'm told that the Ristretto adaptation of those curves would work.
[...] I would be interested to hear folks' thoughts on whether the benefits of reduced synchronization would be worth the costs of limiting DH group selection (either old ECDH or new stuff without a lot of implementation).

Thanks for this, I'll check Ristretto out.  One related concern I have is that I have not yet found any mainstream post-quantum crypto proposals that support key combining.

Best,
Matthew Weidner

[1] Jing Su, James Scott, Pan Hui, Jon Crowcroft, Eyal De Lara, Christophe Diot, Ashvin Goel, Meng How Lim, and Eben Upton. 2007. Haggle: seamless networking for mobile applications. In Proceedings of the 9th international conference on Ubiquitous computing (UbiComp '07), John Krumm, Gregory D. Abowd, Aruna Seneviratne, and Thomas Strang (Eds.). Springer-Verlag, Berlin, Heidelberg, 391-408.

---

From: Jeff Burdges <[email-masked]>
Date: Tue, 26 Mar 2019 15:40:07 +0100

Hello,

Aside form Matrix, there are several groups from the wider Ethereum 2.0 community interested in a messaging scheme that is both distributed and privacy preserving, including both at a cryptographic level and at the metadata level (mix networks).  These include Nym (Panoramix), Status IM, Validity Labs, and the Web 3 Foundation and Parity.

We’re largely out-of-the-loop on MLS but we’re exited about MLS possibly providing a cryptographic layer without too many centralising assumptions.  We’re definitely interested in the “concurrent" updates problem in particular because mix networks can incur considerable latency.

There are also a few projects like Meshenger who should consider using MLS or similar for group messaging over mesh networks.  These have a similar need for concurrent updates, albeit stemming from network topology rather than latency.

Again apologies for my being out-of-the-loop, but I’m not completely sure what concurrency means here.  There is a merge operation that requires any decrypting party processed all the merged trees, yes?  If I understand, there is a similar tree merge operation for vanilla TreeKEM that provides similar assurances to the merge operation that I assume Casual TreeKEM exists to provide:  You simply encrypt the key update messages to anyone who possesses a set of old keys.  This is not actually heavier than encrypting to parties who possess only one key, except that you must identify the set of old keys.

Ignoring the ECC issues [2], there are afaik no commonly discussed post-quantum schemes that support the key combining operation used by Casual TreeKEM, so if Casual TreeKEM is desired then you need an explicit tree merge function too?

All that said, I kinda like that Casual TreeKEM merges seem commutative, but maybe vanilla TreeKEM could support anything useful here by keeping some symmetric key material in a large abelian group?  I’m not sure if I understand the protocol well enough yet to say if that makes sense.

Best,
Jeff

[1]  I spoke with Benjamin some about the header encryption in MLS, which he convinced me looks suitable for some mix network specific concerns.

[2]  There is nothing wrong with requiring Edwards curve arithmetic instead of X25519/X448 of course, but I’m unsure if many constant-time implementations exist besides the Rust curve25519-dalek crate.  I think Ed25519 libraries normally only implement variable-time multiscalar multiplication and constant-time scalar multiplication by the basepoint.  I’d naively assume Weierstrass curves should be avoided due to similar constant-time concerns, but not personally familiar with the implementations.

---

From: Jeff Burdges <[email-masked]>
Date: Tue, 26 Mar 2019 16:00:47 +0100

> On 23 Mar 2019, at 19:59, M.A.L. Weidner <[email-masked]> wrote:

Just fyi, CSIDH supports composing secret keys, meaning if  CSIDH(A,b) = CSIDH(B,a)  then  CSIDH(A, x . b) = CSIDH(B, x . a)  for some other secret key that both A and B know.  You could do a simple successive multi-way DH too I think, so more CSIDH(CSIDH(B, x), a) etc.

I doubt this helps Causal TreeKEM, but it’s extremely helpful for mixnets.  In fact, mixnets are part of the reason CSIDH was created.  It might help do ART-like constructions and/or protect against malicious updates though.

Jeff

---

From: "M.A.L. Weidner" <[email-masked]>
Date: Wed, 27 Mar 2019 11:16:07 +0000

From the above discussion, it appears there are a few ideas for how to handle concurrent updates.  Here is my attempt at a summary.

The scenario is that we are sending an update message, and as part of this, we need to send a secret to a node on our copath; this node has k distinct "candidate" public keys, coming from >= k concurrent updates.  Our options are:

1. (Vanilla TreeKEM) Choose one of the candidates arbitrarily and send the secret encrypted under that.
- Cost (compared to an ordinary sequential update): none.
- PCS guarantee (of the secret we send): healed against compromise of the user who contributed the chosen public key.

2. (similar to Causal TreeKEM) "Combine" all of the candidate public keys and send the secret encrypted under that, so that only someone with all of their private keys can decrypt the secret.
- Cost: need to use a cryptosystem that supports key combining (e.g., Ristretto curves).
- PCS guarantee: healed against compromise of any *one* user who contributed a public key.

3. (Vanilla TreeKEM, multiple keys) Encrypt the secret under each of the candidate public keys in sequence, so that only someone with all of their private keys can decrypt the secret.  (I think this is what Jeff was suggesting - correct me if I'm wrong.)
- Cost: k encryptions for me, k decryptions for recipients (instead of 1 in the ordinary case).
- PCS guarantee: healed against compromise of any *one* user who contributed a public key.

4. (Blank out conflicts) Replace conflicted nodes with blanks (including the node we are sending to, and any conflicted children).  Thus we send the secret separately for each of the k candidates, using public keys deep enough in the tree that none of the contributors' old states can decrypt the secret.  In the extreme case where the k public key contributors are the only descendants of the conflicted node, this means we send the secret separately to each contributor.
- Cost: k encryptions for me, k times as much bandwidth.
- PCS guarantee: healed against compromise of any subset of the users who contributed public keys.

Another consideration is how to encrypt ordinary (e.g. chat) messages after concurrent updates lead to multiple choices for the root key.  We get the same guarantee as option 2 if we combine each concurrent updates' contribution into the root key, as in the original TreeKEM proposal or in Causal TreeKEM.  (This can be done using any KDF, since the root key is just a shared secret, not an asymmetric key pair.)  Getting the strong guarantee in option 4 seems harder.  We could adopt a rule that after concurrent updates, users must first send an update before sending ordinary messages, but that could lead to repeated rounds of concurrent updates.

Best,
Matthew Weidner