[MLS] Re-randomized TreeKEM

[Joel Alwen <[e-mail]>]

Hey everyone,

Sandro, Yevgeniy, Yiannis and I wanted to give you a heads up about some
work we've been doing around TreeKEM. I'll summarize the main points
here. You can also check the slides (attached to this email) which go a
bit more in depth about some of the results with lots of pretty
pictures. But for those interested in the full story we invite you to
look at the full paper on eprint [1].

Basically, we're eager to hear what you all think about it all! More
specifically, one thing I think we could discuss on the list is whether
the work group wants to adopt the proposed changes to TreeKEM. While we
are quite convinced this would significantly improve security for MLS,
it does come at a price which we tried to summarize to the best of our
knowledge below.

Besides general feedback, here are some specific options to consider for
moving forward (just to get the ball rolling).

(1) Adopt the changes as part of MLS.
(2) Make it an optional mode for MLS.
(3) Save it for a future version of MLS.
(4) Just forget about it all together.

- Joël




Results
-------
1) We describe the poor Forward Secrecy properties of TreeKEM. Suppose a
path is updated resulting in a new update key k being fed into the MLS
key schedule. We show that an adversary seeing network traffic can
recover k by leaking any of roughly *n/2 different keys* from the
ratchet tree, some of which are known to multiple parties. That means FS
for k only kicks in once about half the nodes in the ratchet tree have
been assigned new key material. (I.e., its *not* enough to refresh the
log(n) keys on the co-path of the update that produces k.)

For MLS this means we have poorer PCS properties than hoped for. When
Alice is compromised and then updates to define new epoch key K there
remain n/2 keys spread across group member's states, any one of which
allows the adversary to recover K.

2) We prove security for TreeKEM but only under a pretty weak security
notion (which is unavoidable given the above issue).

3) We describe a modification of TreeKEM based on the proposal by Konrad
in the mailing list 24/Jan/2019 [2]. (We call it RTreeKEM for
"Re-randmoized TreeKEM" but the eprint version hasn't been updated yet
to reflect this nomenclature.) Essentially, RTreeKEM replaces HPKE with,
so called, "updatetable public key encryption" (UPKE). Its the same as
HPKE except that when encrypting to a PK, the output includes both a
ciphertext c and an updated (re-randomized) public key PK'. Decryption
of c with SK produces the plaintext and updated secret key SK'
corresponding to PK'.

The intuition here is that this gives TreeKEM a second mechanism for
updating ratchet tree key material besides updates. As a result a node's
SK is used to decrypt no more than 1 ciphertext before it's refreshed.
The offshoot is faster replacement of keys in the ratchet tree and so
faster FS. (Ergo, faster PCS for MLS.) In a sense, we are motivated by
treating the event that a group member actually comes online as a
valuable comodity so RTreeKEM tries to take more advantage of them than
TreeKEM does.

Technically, we define and construct UPKE, RTreeKEM, and prove their
security. In particular, we show that, *if* the delivery service ensures
Handshake (i.e. TreeKEM) packets are delivered in an arbitrary but same
order to all group members then RTreeKEM gives us "optimal" FS and PCS.
That is, assuming global handshake ordering, no protocol can give us FS
or PCS with *fewer* message flows exchanged in any type of execution.
Indeed, any such security improvement would necessarily imply curtailing
the functionality MLS wants from TreeKEM. (Put differently, better
security will invariably mean that there will be some situation in which
an honest group member can't produce an update secret they need to
advance to the next epoch and ends up getting left behind.)

Finally, to qualify "optimal": our results don't mean there can't be a
protocol with the same security but *smaller* packet sizes (just not
with *fewer* packets). Also if the global ordering assumption fails we
could still hope for better security with some other protocol.
(Although, personally, I suspect that will only be possible using
cryptographic primitives that are much less efficient and more advanced
-- read not publicly implemented let alone standardized yet).



The Trade-off
-------------
The stronger FS for RTreeKEM comes at a price which we believe can be
summarized as:

1) Currently, we aren't sure how to build UPKE from the X25519 and X448
groups. In particular, UPKE is currently formulated based on abstracting
the underlying ECC group and DH function as modular exponentiation
function (over a generic prime order group). But that's not quite the
case for those X* functions. They first fix some bits of the scaler
(called "clamping") before performing modular exponentiation so modeling
them as simple exponentiations is not accurate. If this doesn't change,
it would mean not supporting the X* functions as a ciphersuite.

Assuming we don't get things to work for X* groups then alternative DH
groups over (essentially) the same curves we could use instead are the
Ristretto variants. E.g. [3] currently under consideration by the CFRG
works in place of X25519. A downside here (relative to, say, X25519) is
that there are fewer public implementations (especially one's audited by
3rd parties if any?). To be clear, we can still use NIST curves and we
are quite confident that having a post-quantum instantiation (e.g. based
on various NIST PQ submissions) is relatively straight-forward.


2) When updating node secrets on a path the corresponding protocol
packet must now include one additional public key per UPKE (formerly
HPKE) ciphertext. Also UPKE ciphertexts are a bit larger (approx. one
extra AES block) than HPKE ones. The public key is needed to inform
group members that *can't* decrypt that ciphertext what the new
(re-randomized) public key at that node is. The extra AES block comes
from including the re-randomizer as part of the plaintext. No more than
$BIT_SECURITY bits are really needed here as they can be expanded
deterministically using a PRG (built from, say, HKDF) to get a
re-randomizer of the desired length. (This little optimization is not in
the eprint version yet. This approach also makes it much harder for an
colluding insider's to use knowledge of SK to choose a re-randomizer
resulting in some targeted SK' as that now requires inverting the PRG.)

In any case, the mitigating observation here is that the increased
packet size means faster FS. So from the point of view of "global
bandwidth required to achieve FS for a given update key" we actually get
a significant *reduction*, (especially if the server delivers things in
a global order). I.e. Basically, RTreeKEM has bigger packets but less of
them are needed.



Differences
-----------
[1] https://ia.cr/2019/1189

[2] https://mailarchive.ietf.org/arch/msg/mls/WRdXVr8iUwibaQu0tH6sDnqU1no

[3] https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristretto/