Re: [MLS] ART Ideas in TreeKEM

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

Hi Richard and Raphael,

> Would it be accurate to summarize your proposal as a "hybrid mode", where when you update:
> - If both of a node's children are populated, then you do an "ART step", generating the parent from the children
> - Otherwise, you do a "TreeKEM step", encrypting the next secret to the resolution of the other child
That's a good way to describe it.  One extra detail is that if two updates both affect a node, you choose one update to win and set the new secret to be what it would have been given that update alone, instead of doing DH on both new children.

>The hunch is that TreeKEM is roughly an order of magnitude faster for average operations in MLS.
Yes, that seems like a good argument against it.  In principle we have a tradeoff between bandwidth and CPU cost, but in practice the bandwidth cost is small (perhaps 1 KB/update?) while this CPU cost is large, unless we are in an unusually network-constrained environment.

Best,
Matthew

On Tue, Feb 26, 2019 at 9:01 AM Raphael Robert <[e-mail]<mailto:[e-mail]>> wrote:
Hi Matthew,

One of the convincing reasons we saw when looking into ART vs. TreeKEM was that the recipient of handshake messages can process them with O(1) DH operations with TreeKEM as opposed to O(log n) with ART. This sounds like a small difference at first, but we believe that it makes a big difference in real life scenarios. Clients will mostly process handshake messages (particularly in large dynamic groups), but only rarely send them. The hunch is that TreeKEM is roughly an order of magnitude faster for average operations in MLS.
If we go back to O(log n) DH operations to derive the root secret we would lose the speed advantage.

Raphael

On 25 Feb 2019, at 23:07, Richard Barnes <[e-mail]<mailto:[e-mail]>> wrote:

Hi Matthew,

Thanks for the thoughts.  Would it be accurate to summarize your proposal as a "hybrid mode", where when you update:

- If both of a node's children are populated, then you do an "ART step", generating the parent from the children
- Otherwise, you do a "TreeKEM step", encrypting the next secret to the resolution of the other child

(Remove is probably similar; for Add there's no change needed.)

Assuming that's right, this honestly doesn't sound like a tremendously compelling proposition to me.  Your evaluation on the overhead seems mostly correct, but there have already been some complaints on the list about hashing overhead, so I'm not sure trading DH+smaller_messages for hashing is going to suit.  I'm also worried that this hybridization will introduce a bunch of new complexity into the protocol and make it harder to implement and analyze.  Open to arguments if other folks are enthusiastic, though.

--Richard







On Mon, Feb 25, 2019 at 4:37 PM M.A.L. Weidner <[e-mail]<mailto:[e-mail]>> wrote:
Greatings MLS Working Group!

I have been studying the proposals for TreeKEM, and earlier, ART, and noticed a way to use ART's DH tree ideas in TreeKEM, without sacrificing the ability to merge updates or use blank nodes.  My apologies if this has been discussed before or if there are any mistakes.

My main motivation here is to reduce the size of update messages, since the key encrypted keys in addition to new public keys means that they are ~2x as large in TreeKEM as in ART.

Basically, we use TreeKEM, but with ART's key derivation "as" H(X).  That is, when a node C1 gets the new secret X, instead of H(X), its parent gets the new secret

H2(DH(X, priv(C2))) = H2(pub(C2) ^ X) = H2(pub(X) ^ priv(C2))

where C2 is the neighbor of C1, for some hash function H2.  Since TreeKEM is agnostic about H, we can "define"

H(X) := H2(DH(X, priv(C2)))

in this way without issue, noting that the only users who will have to compute H2(DH(X, priv(C2))) are descendants of C1 (who know X) or C2 (who know priv(C2)).

We can merge updates as with "pure" TreeKEM, choosing one update to dominate at nodes where they conflict.  This will cause the tree to cease being a DH tree, which is fine.  Note that descendants of C2 will have to keep around priv(C2) for a short time after it is overwritten in case of simultaneous updates (so that they can compute the parent secret), but that is true for TreeKEM anyway, since any simultaneous update will send data encrypted under pub(C2).

Blank nodes can be handled by reverting to pure TreeKEM: if a node with new secret X has a blank neighbor, set the parent's secret to H(X) and send that separately to every public key in the resolution.

Now instead of including

pub(X), Enc(pub(C2), H(X))

in the RatchetNode struct for node C2, we need merely include pub(X), saving bandwidth.

Pros:
  - reduces the update message size by about 50% in the typical case (I think).
  - we can build a ternary tree using 3-party Joux DH (as with ART), giving a further log_3(2) ~ 0.63 scaling on update message size.  (I think it's possible to do this with pure TreeKEM as well, by replacing the ephemeral DH exchange with a Joux DH when doing asymmetric encryption.)

Cons:
  - forced to use a DH style cryptosystem (bad for post-quantum?) (as with ART).
  - need log(N) DH operations to compute the new key, instead of log(N) hashes (as with ART).  So this is a bad deal if CPU cycles are more expensive than bandwidth.
  - can also reduce bandwidth by 2 just by ratcheting half as often.

I hope you may find this interesting.

Best,
Matthew Weidner
MPhil student, University of Cambridge
_______________________________________________
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