Re: [MLS] Proposals for handling concurrent messages

["M.A.L. Weidner" <[e-mail]>]

Dear MLS Working Group,

Thanks for the feedback.  Some responses:

On Fri, Mar 22, 2019 at 5:00 AM Karthikeyan Bhargavan <[e-mail]<mailto:[e-mail]>> 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 <[e-mail]<mailto:[e-mail]>> 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 <[e-mail]<mailto:[e-mail]>> 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.