Re: [MLS] Proposals for handling concurrent messages

[Karthikeyan Bhargavan <[e-mail]>]

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