Subject: [MLS] Re-randomized TreeKEM

From: Joel Alwen <[email-masked]>
Date: Wed, 16 Oct 2019 23:51:23 +0200

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/

---

From: Karthik Bhargavan <[email-masked]>
Date: Thu, 17 Oct 2019 07:42:54 +0200

Hi Joel,

This looks very interesting. It is new to me since I was not at the interim.
After reading the paper and the slides, I am still a bit fuzzy about what the recipient of an update needs to do.

For example, for the running example in your slide deck, it would help if I could see:
- what secret keys does each leaf need to keep
- how do these secrets change when an update from some other node is received.
Just working this out for one update is enough.

I know that this is made precise in the eprint, but it would be faster if you could help us understand it :)

Best,
Karthik

> On 16 Oct 2019, at 23:51, Joel Alwen <[email-masked]> wrote:
> 
> <FS-TreeKEM.pdf>

---

From: Yevgeniy Dodis <[email-masked]>
Date: Thu, 17 Oct 2019 07:47:05 -0400

Hi Karthik.

Sorry for the short answer, about to drive for 4 hours ;).

Each user still stores at most log n secret keys on the path to the root
(and all public keys, unless retrieving them as needed). During each
operation where this user is not initiator, there will be precisely one
ciphertext this user needs to decrypt using one of these log n keys,  just
like before. In the original TreeKEM, after decrypting this ciphertext, the
public and secret
key for this encryption stays the same. In RTreeKEM, --- and this is the
main (and effectively only) difference, --- the public and secret keys for
this encryption change. In a way that the new secret key will be able to
decrypt ciphertexts encrypted under NEW public key, not not OLD public key.
In particular, new secret key will not be able to decrypt the ciphertext
that the user just decrypted. Given our global ordering assumption, this
does not get users out of sync, even if some and offline for long periods
of time.

So think of this as public key analog of a steam cipher. Where after each
decryption the steam cipher state changes to ensure forward secrecy. Here
the cute part is that the public key will be effectively changed by the
sender (who does not know neither new or old secret key), but in a way that
the recipient (and only the recipient!) can recover the matching secret
key. Intuitively, the sender will not only encrypt the message, but also a
random Delta value. It will change public key using homomorthism by
multiplying with g^Delta (in specific DH based scheme), while the recipient
will decrypt Delta (using old secret key), and add it to the old secret key
to get there new one. So now corrupting (old sk plus Delta) will not help
decrypting the ciphertext just decepted, emailing forward secrecy. So very
small cost compared to the original TreeKEM (see our earlier email for more
details). And really the same scheme, modulo PKE  being stateful ala a
steam cipher.

This is the high level, hope it makes sense.
Thanks for your question,
Yevgeniy

On Thu, Oct 17, 2019, 1:43 AM Karthik Bhargavan <
[email-masked]> wrote:

> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Karthik Bhargavan <[email-masked]>
Date: Thu, 17 Oct 2019 16:37:29 +0200

Thanks Yevgeniy,

This helps a lot.

To further my understanding, another question:

>  Intuitively, the sender will not only encrypt the message, but also a random Delta value. It will change public key using homomorthism by multiplying with g^Delta (in specific DH based scheme), while the recipient will decrypt Delta (using old secret key), and add it to the old secret key to get there new one. So now corrupting (old sk plus Delta) will not help decrypting the ciphertext just decepted, emailing forward secrecy. 

I see that in the DH-based scheme, this Delta needs to be private, otherwise the adversary can compute sk once it knows sk+Delta.
But, in general, is it possible to conceive of a UPKE scheme where the recipient effectively “hashes forward” its symmetric key,
where this one way hash-forward function does not have to rely on an externally chosen secret value?

Best,
Karthik

> On Thu, Oct 17, 2019, 1:43 AM Karthik Bhargavan <[email-masked] <mailto:[email-masked]>> wrote:
> Hi Joel,
> 
> > On 16 Oct 2019, at 23:51, Joel Alwen <[email-masked] <mailto:[email-masked]>> wrote:
> > 
> > <FS-TreeKEM.pdf>
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>

---

From: Karthik Bhargavan <[email-masked]>
Date: Thu, 17 Oct 2019 16:39:34 +0200

Sorry: typo (symmetric key —> private key)

I see that in the DH-based scheme, this Delta needs to be private, otherwise the adversary can compute sk once it knows sk+Delta.
But, in general, is it possible to conceive of a UPKE scheme where the recipient effectively “hashes forward” its *private* key,
where this one way hash-forward function does not have to rely on an externally chosen secret value?

---

From: Joel Alwen <[email-masked]>
Date: Thu, 17 Oct 2019 17:18:40 +0200

I think the challenge with the hash-forward approach is how to do that
homomorphically. I.e. what we need are two algorithms; one to refresh
the PK without knowing the SK (but possibly knowing a secret
rerandomizer delta if needed) and one to update SK (again possibly using
delta). So to use a hash-forward approach their must be:

 1) a way to evolve PK forward to PK' and
 2) a *one-way* method to evolve SK forward to SK' compatible PK'.

One-wayness is what gives us Forward Secrecy and "compatibility" between
the two key evolution methods is what allows for asynchronous (i.e. 1
packet) updates.

Currently we use a secret re-randomizer delta to ensure the SK update
method is one-way. That is, without the delta you cant "undo" the
update. But that would break if we (at least naively) used some public
delta, say hash(ciphertext). So I think this is the challenge that we'd
have to overcome. Basically, make sure we SK evolution is one-way but
also compatible the public evolution of PK.

Now one way sweet way to get all this (and more) would be to use a HIBE.

Initial, PK for a ratchet tree node (i.e. its "identity" since this is a
HIBE now) is simply the empty vector PK := () while the secret key is
the master public key for a fresh HIBE instance SK := MSK. We also
include, as a second component of the nodes PK, the master public key
PK_0 = MPK. To "hash forward" / "re-randomize" when sending a ciphertext
C to that node we can do:

 PK' := (PK, hash(C)).
 SK' := DeriveHIBEKey(PK, SK).

So simply append hash(C) to the identity for that node and derive the
corresponding HIBE key.

Ignoring the problems with using HIBE for a second, this is a very cool
solution. We don't need to send out the updated PK since everyone in the
group (and even the adversary) can compute it for themselves. We also
dont need a re-randomize delta as part of the plaintext because we're
using delta := hash(ciphertext) so the plaintext is shorter again.
Moreover, HIBE security means that learning SK' doesn't tell you
anything interesting about SK. In particular, we have forward security.
(In fact, FS will hold even if hash(C) were chosen *completely*
adversarially, say, as part of a malicious update in an insider attack!)

Of course, the problem with this solution is that we're using HIBE.
Worse, with unbounded depth because each new ciphertext sent to a node
results in going one depth further into the hierarchy. AFAIK all HIBE
constructions have pretty horrible (read exponential) efficiency as a
function of their depth. (And I won't mention the state of
standardization and open implementations for HIBE.)

Now there could be a totally different approach that entirly avoids
HIBE. But even with this approach there's at least some glimer of hope
to improve on it because, if we don't wory about insider attacks we can
assume C is honestly generated which means hash(C) really has a ton of
entropy. So we dont seem to need the full expresivity HIBE identities
allow us. Rather we only need HIBE for "random" identities. Still, that
seems like a pretty slim hope for major efficiency improvement. It also
doesn't do anything to address the lack of implementations and standards.

- Joël

On 17/10/2019 16:37, Karthik Bhargavan wrote:
>>  Intuitively, the sender will not only encrypt the message, but also a
>> multiplying with g^Delta (in specific DH based scheme), while the
>> recipient will decrypt Delta (using old secret key), and add it to the
>> old secret key to get there new one. So now corrupting (old sk plus
>> Delta) will not help decrypting the ciphertext just decepted, emailing
>> forward secrecy. 
> 
> I see that in the DH-based scheme, this Delta needs to be private,
> otherwise the adversary can compute sk once it knows sk+Delta.
> But, in general, is it possible to conceive of a UPKE scheme where the
> recipient effectively “hashes forward” its symmetric key,
>> On Thu, Oct 17, 2019, 1:43 AM Karthik Bhargavan
>> <[email-masked]
>> <mailto:[email-masked]>> wrote:
>>
>>     Hi Joel,
>>
>>     After reading the paper and the slides, I am still a bit fuzzy
>>     about what the recipient of an update needs to do.
>>
>>     I know that this is made precise in the eprint, but it would be
>>     faster if you could help us understand it :)
>>
>>     Best,
>>     Karthik
>>

---

From: Brendan McMillion <[email-masked]>
Date: Fri, 18 Oct 2019 10:48:55 -0700

Hey Joel

This is a pretty subtle topic so I want to state the assumption that my conclusion is based on upfront: RTreeKEM achieves FS and PCS after a single Update (and all users come online and process the update), while normal TreeKEM requires everyone in the group to Update before achieving the same security guarantee.

This actually makes TreeKEM more attractive to me because it encourages implementors to keep the Update frequency high, and it provides an explicit signal to the group that everyone has processed every update. With TreeKEM, the policy would be “everybody Updates at least once per day”. But with RTreeKEM, the equivalent policy is “at least one person Updates every day” which isn’t as strong, because you don’t know whether or not everybody came online that day and processed the one Update.

And if you have a high Update frequency, I don’t think the security properties of TreeKEM and RTreeKEM are materially different. But RTreeKEM has costs like being harder to implement, and restricting what algorithms we can use.

It’s on this basis that I’m opposed to including RTreeKEM in the spec.

> On Oct 17, 2019, at 8:18 AM, Joel Alwen <[email-masked]> wrote:
> 
>>> <mailto:[email-masked] <mailto:[email-masked]>>> wrote:
>>> 
>>>    Hi Joel,
>>> 
>>>> On 16 Oct 2019, at 23:51, Joel Alwen <[email-masked] <mailto:[email-masked]>
>>>    <mailto:[email-masked] <mailto:[email-masked]>>> wrote:
>>>> 
>>>> <FS-TreeKEM.pdf>
>>> 
>>>    [email-masked] <mailto:[email-masked]> <mailto:[email-masked] <mailto:[email-masked]>>

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Mon, 21 Oct 2019 14:03:32 +0200

I see. So, here’s how I read the improvements proposed in RTreeKEM.

Currently, in TreeKEM (like in ART before it) we rely on each member to regularly *send* updates in order to get both PCS and FS for the group secrets.
The informal secrecy guarantees we get are that:
- (FS) if member A sends an update in epoch N (moving the epoch to N+1), and if A gets compromised in epoch N+1, the messages sent in epoch N remain secret
- (PCS) if member A sends an update in epoch N (moving the epoch to N+1), and if A was (passively) compromised in epoch N, the messages sent in epoch N+1 remain secret
In other words, each member who sends an update gets local protection against compromise, encouraging vulnerable members to keep sending updates.

However, as Joel, Sandro, Yevgeniy, and Yiannis note in their paper, we could do better, at least for FS, if we use one-time decryption keys.
If each recipient deletes the old decryption key after processing an update, then even just by *processing* an update, we get an additional  guarantee:
- (FS’) if member A processes an update in epoch N (moving the epoch to N+1), and if A gets compromised in epoch N+1, the messages sent in epoch N remain secret

It is also worth remembering that Signal also has a notion of one-time prekeys that work similarly for new messaging sessions.
Although the following would be a bit ridiculous to use in large dynamic groups, here  is a sketch to achieve the receiver FS guarantee without the need for new crypto.
- Every time a member A sends an update, it generates fresh node secrets for nodes on the path from A to the root
- From each node secret, A generates a large number K (= 100) private-public encryption keypairs and sends the public keys with the update.
- On receiving the update, each member B stores all K public keys for each node in its co-path
- Each of these public keys can be used only once for sending an update, after which the private key is deleted from all recipients.
- The last public key at each node is not deleted; it can only be replaced when one of the members under that node sends a new update (with a fresh batch of public keys).

As far as I understand, the above scheme can be seen as an (inefficient) implementation of UPKE, right?
Of course, it increases the size of each update by K, and only provides FS for K updates, after which some member has to send an update.
Conversely, it does not require any new crypto algorithm. Is this a good baseline to compare UPKE schemes against?

If I am mis-reading something, do let me know!

-Karthik

> On 17 Oct 2019, at 17:18, Joel Alwen <[email-masked]> wrote:
>

---

From: Konrad Kohbrok <[email-masked]>
Date: Mon, 21 Oct 2019 14:20:30 +0200

Hi Karthik,

I think you got it right with regard to the additional guarantees gained by
RTreeKEM.

Regarding your UPKE proposal: Wouldn't A then also have to send the private keys
of each key pair to all leaves of the sub-tree blonging to the node that the key
pair is generated for? Otherwise, only A could decrypt updates sent to those
keys. These private keys would have to be encrypted under some previous one-time
key that is subsequently deleted.

Cheers,
Konrad

On 21.10.19 15:03, Karthikeyan Bhargavan wrote:
> Currently, in TreeKEM (like in ART before it) we rely on each member to
> regularly *send* updates in order to get both PCS and FS for the group secrets.
> - (FS) if member A sends an update in epoch N (moving the epoch to N+1), and if
> A gets compromised in epoch N+1, the messages sent in epoch N remain secret
> - (PCS) if member A sends an update in epoch N (moving the epoch to N+1), and if
> A was (passively) compromised in epoch N, the messages sent in epoch N+1 remain
> secret
> In other words, each member who sends an update gets local protection against
> compromise, encouraging vulnerable members to keep sending updates.
> 
> However, as Joel, Sandro, Yevgeniy, and Yiannis note in their paper, we could do
> better, at least for FS, if we use one-time decryption keys.
> If each recipient deletes the old decryption key after processing an update,
> then even just by *processing* an update, we get an additional  guarantee:
> - (FS’) if member A processes an update in epoch N (moving the epoch to N+1),
> and if A gets compromised in epoch N+1, the messages sent in epoch N remain secret
> 
> It is also worth remembering that Signal also has a notion of one-time prekeys
> that work similarly for new messaging sessions.
> Although the following would be a bit ridiculous to use in large dynamic groups,
> here  is a sketch to achieve the receiver FS guarantee without the need for new
> crypto.
> - From each node secret, A generates a large number K (= 100) private-public
> encryption keypairs and sends the public keys with the update.
> - Each of these public keys can be used only once for sending an update, after
> which the private key is deleted from all recipients.
> - The last public key at each node is not deleted; it can only be replaced when
> one of the members under that node sends a new update (with a fresh batch of
> public keys).
> 
> Of course, it increases the size of each update by K, and only provides FS for K
> updates, after which some member has to send an update.
> Conversely, it does not require any new crypto algorithm. Is this a good
> baseline to compare UPKE schemes against?
> 
>> On 17 Oct 2019, at 17:18, Joel Alwen <[email-masked]
>> <mailto:[email-masked]>> wrote:
>>
>>>> <[email-masked] <mailto:[email-masked]>
>>>>    <mailto:[email-masked]>> wrote:
>>>>>
>>>>> <FS-TreeKEM.pdf>
>>>>
>>>>    [email-masked] <mailto:[email-masked]> <mailto:[email-masked]>

---

From: Benjamin Beurdouche <[email-masked]>
Date: Mon, 21 Oct 2019 14:28:01 +0200

> On Oct 21, 2019, at 2:20 PM, Konrad Kohbrok <[email-masked]> wrote:
> 
> Hi Karthik,
> 

No, I think Karthik suggested to KDF (K=100) keypairs from the new secret (instead of K=1 today)
and immediately kill the received node secret for FS…

B.

---

From: Konrad Kohbrok <[email-masked]>
Date: Mon, 21 Oct 2019 14:31:04 +0200

Ah, ok I misunderstood. That sounds a lot more feasible :-)

Konrad

On 21.10.19 15:28, Benjamin Beurdouche wrote:
> 
> 
>> On Oct 21, 2019, at 2:20 PM, Konrad Kohbrok <[email-masked]
>> <mailto:[email-masked]>> wrote:
>>
>> Hi Karthik,
>>

---

From: Joel Alwen <[email-masked]>
Date: Mon, 21 Oct 2019 23:15:55 +0200

> - From each node secret, A generates a large number K (= 100)
> private-public encryption keypairs and sends the public keys with the
> update.
> - Each of these public keys can be used only once for sending an update,
> after which the private key is deleted from all recipients.
> - The last public key at each node is not deleted; it can only be
> replaced when one of the members under that node sends a new update
> (with a fresh batch of public keys).
> 

I think your right. I think its similar to UPKE with the caveat that
only K ciphertext can be sent per call to UPKE-KeyGen. (In other words,
as you point out below, after K nodes encrypted to a ciphertext it
effectively becomes blank.)

But I think it does achieves the same properties for TreeKEM as the UPKE
constructions based on re-randomization, at least for the corruption
model we've been looking at.

> Of course, it increases the size of each update by K, and only provides
> FS for K updates, after which some member has to send an update.

Well, its close but but has the limit on how many ciphertexts can be
sent to any given key-pair which UPKE normally doesnt have. On the other
hand if sender knows the old SK and then they can compute the new SK in
UPKE which is not the case in your construction. So I'd say its (at
least formally speaking) incomparable to UPKE.

- Joël

---

From: Joel Alwen <[email-masked]>
Date: Mon, 21 Oct 2019 23:50:34 +0200

Hey Brendan,

Thanks for taking the time to look at this stuff and answer! :-)

> This actually makes TreeKEM more attractive to me because it encourages
> implementors to keep the Update frequency high, 

If one can afford high update frequency then that's great. It helps
RTreeKEM too by the way. The longer between updates the less PCS we have
and the longer the corruption windows. So there's still plenty of
incentive in RTreeKEM to update as often as you can.

But more generally, to me a primary design goal for MLS is to get as
much security for as little bandwidth as possible. So I'm particularly
interested in the protocols behavior when there *isn't* that much
bandwidth to spare for frequent updates.

> and it provides an
> explicit signal to the group that everyone has processed every update.
> With TreeKEM, the policy would be “everybody Updates at least once per
> day”. But with RTreeKEM, the equivalent policy is “at least one person
> Updates every day” which isn’t as strong, because you don’t know whether
> or not everybody came online that day and processed the one Update.

If your not coming online then I'm not sure I see the difference between
using TreeKEM or RTreeKEM. I mean, either way your not refreshing any
key material so your preventing the group from achieving FS. Moreover,
coming online to send a daily update TreeKEM means already requires
processing other peoples updates first.

If, on the other hand, the concern is the lack of an explicit signal
wouldnt it be enough to have parties send out ACK msgs to the group when
they process an update? That would consume far less bandwidth (and
computation) than doing a full update alla TreeKEM.

> But RTreeKEM has costs like being harder to implement, and restricting what
> algorithms we can use.

FYI: In the mean time it looks like we may have found a way to make
RTreeKEM work with X25519/X448 groups. (See the email I just sent to the
group for more on this.) Harder to implement I do agree with. Albeit IMO
the difference is rather marginal compared to how much code is needed to
implement the rest of MLS, not to mention all the surrounding
infrastructure; e.g. the servers, the rest of the client, UX etc need to
actually deploy MLS. At the end of the day, I don't think we're talking
about much more than a few lines of code wrapping HPKE. But I might be
wrong here.

> It’s on this basis that I’m opposed to including RTreeKEM in the spec.

Fair enough! :-)

- Joël

---

From: Yevgeniy Dodis <[email-masked]>
Date: Mon, 21 Oct 2019 18:53:30 -0400

Great summary, Karthik!

As I put in the other thread, comparison with the "naive" UPKE (for K=100
or less) might be a good idea.

Pros of Naive Scheme:
- more general, uses any PKE
- using stream ciphers to generate K key pairs as needed makes the
efficiency hit noticeably less than a factor of K,
and perhaps closer to a factor of 2 (see below), but unclear a-priori.
- for K>1, offers non-trivial (but still sub-optimal) security enhancement
over basic TreeKEM (K=1)

Cons (pros of RTreeKEM):
- Public key storage increases by at least factor of K
- While the naive use increases secret storage and computation by a factor
of K, using stream cipher, after i uses one can only store the
current seed to generate last (K-i) keys. However, K public keys should be
published right away, so we must
lose at least factor of 2 compared to TreeKEM to generate all keys twice
(but possibly factor of K if people update too frequently, so all but
1 of the K keys gets used). So overall efficiency hit between 2 and K,
which might already be comparable or worse than RTreeKEM.
- Still much worse security than RTreeKEM, but possibly more expensive too,
already for small K!

Please let us know if you think this should be explored further.
Yevgeniy

On Mon, Oct 21, 2019 at 8:03 AM Karthikeyan Bhargavan <
[email-masked]> wrote:

> - (FS) if member A sends an update in epoch N (moving the epoch to N+1),
> - (PCS) if member A sends an update in epoch N (moving the epoch to N+1),
> and if A was (passively) compromised in epoch N, the messages sent in epoch
> N+1 remain secret
> In other words, each member who sends an update gets local protection
> against compromise, encouraging vulnerable members to keep sending updates.
>
> However, as Joel, Sandro, Yevgeniy, and Yiannis note in their paper, we
> could do better, at least for FS, if we use one-time decryption keys.
> If each recipient deletes the old decryption key after processing an
> update, then even just by *processing* an update, we get an additional
>  guarantee:
> - (FS’) if member A processes an update in epoch N (moving the epoch to
> N+1), and if A gets compromised in epoch N+1, the messages sent in epoch N
> remain secret
>
> It is also worth remembering that Signal also has a notion of one-time
> prekeys that work similarly for new messaging sessions.
> Although the following would be a bit ridiculous to use in large dynamic
> groups, here  is a sketch to achieve the receiver FS guarantee without the
> need for new crypto.
> - The last public key at each node is not deleted; it can only be replaced
> when one of the members under that node sends a new update (with a fresh
> batch of public keys).
>
> Of course, it increases the size of each update by K, and only provides FS
> for K updates, after which some member has to send an update.
> <mailto:[email-masked] <[email-masked]>>>
> wrote:
>
>    Hi Joel,
>
> On 16 Oct 2019, at 23:51, Joel Alwen <[email-masked]
>
>    <mailto:[email-masked] <[email-masked]>>> wrote:
>
>
> <FS-TreeKEM.pdf>
>
>
>    [email-masked] <mailto:[email-masked] <[email-masked]>>

---

From: Yevgeniy Dodis <[email-masked]>
Date: Mon, 21 Oct 2019 19:08:16 -0400

Hi Brandan.

To re-iterate Joel's answer, in terms of security RTreeKEM is at least as
good (and often strictly better) than TreeKEM in every dimension.
So whatever update policy somebody might apply to TreeKEM, applying the
same policy to RTReeKEM will be equally good and *likely
better* for security.

You correctly observed that RTreeKEM, by being strictly more secure, allows
for "lazier" update policies which nobody would ever consider
in the basic TreeKEM. And this leads to a potential danger of somebody
using a policy which is "too lazy" even for the more secure scheme.
But I think it is unfair to say that one would prefer a less secure scheme
because it is less likely to be mis-used.

So, in my opinion, the one and only consideration should be if efficiency
cost and slight loss of generality (as of now) justifies the gain in
security.  I hope the answer is yes, but would love to hear other opinions.

Thank you for voicing this though.
Yevgeniy

On Fri, Oct 18, 2019 at 1:49 PM Brendan McMillion <brendan=
[email-masked]> wrote:

> Hey Joel
>
> This is a pretty subtle topic so I want to state the assumption that my
> conclusion is based on upfront: RTreeKEM achieves FS and PCS after a single
> Update (and all users come online and process the update), while normal
> TreeKEM requires everyone in the group to Update before achieving the same
> security guarantee.
>
> implementors to keep the Update frequency high, and it provides an explicit
> signal to the group that everyone has processed every update. With TreeKEM,
> the policy would be “everybody Updates at least once per day”. But with
> RTreeKEM, the equivalent policy is “at least one person Updates every day”
> which isn’t as strong, because you don’t know whether or not everybody came
> online that day and processed the one Update.
>
> And if you have a high Update frequency, I don’t think the security
> properties of TreeKEM and RTreeKEM are materially different. But RTreeKEM
> has costs like being harder to implement, and restricting what algorithms
> we can use.
>

---

From: Brendan McMillion <[email-masked]>
Date: Mon, 21 Oct 2019 18:08:53 -0700

> computation) than doing a full update alla TreeKEM.

Right, my concern is the lack of an explicit signal. I'm taking the
perspective of an individual user thinking, "What policy do I need to
enforce, to ensure that after X amount of time without compromise, my group
is back to a secure state?" And the answer to that question is the same
whether you're using TreeKEM or RTreeKEM: you need to require everybody to
Update, and you need to Remove the users who haven't Updated. RTreeKEM
might get to a secure state faster but it's not that much faster, and it
doesn't change the promises we can make to our users. That's what I meant
when I said the security of the two schemes isn't materially different.

Having everybody send an ACK requires either quadratic bandwidth or
trusting the server, which isn't worth it imo.

---

From: Joel Alwen <[email-masked]>
Date: Tue, 22 Oct 2019 23:05:16 +0200

> RTreeKEM might get to a secure state faster but it's not that much faster, and it doesn't change the promises we can make to our users.

I'm curious what leads you to this conclusion. Suppose Alice produces an update defining new group key K. If the
adversary can't already process the update then with RTreeKEM we get FS for K once the update is processed by all
parties. For TreeKEM not only must that hold but we then need a further order n other parties to send out their own
updates too. At least in terms of # of message flows and total bandwidth (and, most likely, in terms of time) that gap
seems pretty big to me.

Moreover, to me this sounds like both a qualitative and quantitative change in the security promise. E.g.
  Quantitative: FS is achieved with fewer message flows & bandwidth.
  Qualitative : FS can be maintained even when there o(n*log(n)) bandwidth. Instead, O(log n) suffices.

> Having everybody send an ACK requires either quadratic bandwidth or trusting the server, which isn't worth it imo.

I dont follow. If I understood your earlier email correctly you said that updates in TreeKEM serve as a signal to others
guiding their update policy. All I was proposing was to use a much more lightweight ACK msg in exactly the same way you
thought updates were being used to guide policy.

Regardless, I don't really understand the problem here. RTreeKEM needs linear updates too for PCS. So people should
still be doing regular updates if they can afford to. That means if I don't see updates from Alice for a long time I'll
eventually want her removed from the group because she's harming the group's PCS. In other words, there's still reason
to do frequent updates which means they still serve as a signal that people are present. The main difference to me is
what we can say about time periods where we can't afford linear number of updates. For those cases RTreeKEM can still
give us FS but not TreeKEM.

- Joël

---

From: Richard Barnes <[email-masked]>
Date: Tue, 22 Oct 2019 17:20:19 -0400

Just so we're clear, I would be *strongly* opposed to putting anything like
this naïve UPKE scheme into MLS.  For the simple reason that it expands the
size of Welcome message by a factor of K.  RTreeKEM or nothing :)

--Richard

On Mon, Oct 21, 2019 at 6:53 PM Yevgeniy Dodis <[email-masked]> wrote:

> - Still much worse security than RTreeKEM, but possibly more expensive
> too, already for small K!
>
>> replaced when one of the members under that node sends a new update (with a
>> fresh batch of public keys)..
>>
>> have to overcome.. Basically, make sure we SK evolution is one-way but

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Tue, 22 Oct 2019 23:26:26 +0200

Indeed!

Like I said, it would be a ridiculous design for MLS.
I was simply trying to understand the guarantees.

-Karthik

> On 22 Oct 2019, at 23:20, Richard Barnes <[email-masked]> wrote:
> 
> Just so we're clear, I would be *strongly* opposed to putting anything like this naïve UPKE scheme into MLS..  For the simple reason that it expands the size of Welcome message by a factor of K.  RTreeKEM or nothing :)
> 
> --Richard
> 
> 
> On Mon, Oct 21, 2019 at 6:53 PM Yevgeniy Dodis <[email-masked] <mailto:[email-masked]>> wrote:
> Great summary, Karthik!
> 
> As I put in the other thread, comparison with the "naive" UPKE (for K=100 or less) might be a good idea.
> 
> Pros of Naive Scheme: 
> - using stream ciphers to generate K key pairs as needed makes the efficiency hit noticeably less than a factor of K,
> - for K>1, offers non-trivial (but still sub-optimal) security enhancement over basic TreeKEM (K=1)
> 
> Cons (pros of RTreeKEM):
> - While the naive use increases secret storage and computation by a factor of K, using stream cipher, after i uses one can only store the 
> current seed to generate last (K-i) keys. However, K public keys should be published right away, so we must 
> lose at least factor of 2 compared to TreeKEM to generate all keys twice (but possibly factor of K if people update too frequently, so all but 
> 1 of the K keys gets used). So overall efficiency hit between 2 and K, which might already be comparable or worse than RTreeKEM.
> - Still much worse security than RTreeKEM, but possibly more expensive too, already for small K!
> 
> On Mon, Oct 21, 2019 at 8:03 AM Karthikeyan Bhargavan <[email-masked] <mailto:[email-masked]>> wrote:
> In other words, each member who sends an update gets local protection against compromise, encouraging vulnerable members to keep sending updates..
> 
> - From each node secret, A generates a large number K (= 100) private-public encryption keypairs and sends the public keys with the update..
> - The last public key at each node is not deleted; it can only be replaced when one of the members under that node sends a new update (with a fresh batch of public keys)..
> 
>> On 17 Oct 2019, at 17:18, Joel Alwen <[email-masked] <mailto:[email-masked]>> wrote:
>>

---

From: Richard Barnes <[email-masked]>
Date: Tue, 22 Oct 2019 17:33:37 -0400

Since it appears I haven't chimed in on this thread -- I am generally OK
with this change, if folks think it would improve the FS properties of the
protocol, and assuming that Joël's / Mike's solution to the X25519 problem
works out.

On the one hand, if we have to shove X25519 overboard, my bias would
probably be against making this change, barring some really strong security
rationale.

On the other hand, if we can get confidence that the X25519 solution works
(or that the failures are rare and tolerable), then this seems like a
pretty minor burden from an engineering POV (a little more code, 2x the DH
operations on Update/Commit), so if there's security benefit, great.

On Tue, Oct 22, 2019 at 5:26 PM Karthikeyan Bhargavan <
[email-masked]> wrote:

> Just so we're clear, I would be *strongly* opposed to putting anything
> like this naïve UPKE scheme into MLS..  For the simple reason that it
> expands the size of Welcome message by a factor of K.  RTreeKEM or nothing
> :)
>
> --Richard
>
>
>> - While the naive use increases secret storage and computation by a
>> factor of K, using stream cipher, after i uses one can only store the
>> current seed to generate last (K-i) keys. However, K public keys
>> should be published right away, so we must
>>> - (PCS) if member A sends an update in epoch N (moving the epoch to
>>> N+1), and if A was (passively) compromised in epoch N, the messages sent in
>>> epoch N+1 remain secret
>>> against compromise, encouraging vulnerable members to keep sending updates..
>>>
>>> update..

---

From: Benjamin Beurdouche <[email-masked]>
Date: Wed, 23 Oct 2019 00:10:38 +0200

That’s my opinion as well... :)
B.

> On Oct 22, 2019, at 11:34 PM, Richard Barnes <[email-masked]> wrote:
> 
> 
> Since it appears I haven't chimed in on this thread -- I am generally OK with this change, if folks think it would improve the FS properties of the protocol, and assuming that Joël's / Mike's solution to the X25519 problem works out.  
> 
> On the one hand, if we have to shove X25519 overboard, my bias would probably be against making this change, barring some really strong security rationale.  
> 
> On the other hand, if we can get confidence that the X25519 solution works (or that the failures are rare and tolerable), then this seems like a pretty minor burden from an engineering POV (a little more code, 2x the DH operations on Update/Commit), so if there's security benefit, great.
> 
>> On Tue, Oct 22, 2019 at 5:26 PM Karthikeyan Bhargavan <[email-masked]> wrote:
>> Indeed!
>> 
>>>>> On Mon, Oct 21, 2019 at 8:03 AM Karthikeyan Bhargavan <[email-masked]> wrote:
>>>>> In other words, each member who sends an update gets local protection against compromise, encouraging vulnerable members to keep sending updates...
>>>>>

---

From: Brendan McMillion <[email-masked]>
Date: Tue, 22 Oct 2019 18:34:59 -0700

> adversary can't already process the update then with RTreeKEM we get FS
> for K once the update is processed by all
> parties. For TreeKEM not only must that hold but we then need a further
> order n other parties to send out their own
> updates too. At least in terms of # of message flows and total bandwidth
> (and, most likely, in terms of time) that gap
> seems pretty big to me.
>

Let's work an example. Say we set a policy that everyone should try to
Update every 12h and those that don't will be removed after 24h. One user
is compromised. How long is it until full FS and PCS is restored?

   - If the user is prevented from sending new Updates:
      - Whether you use TreeKEM or RTreeKEM, the group is secure again
      after the user is removed. So after 24h at most, but 12h on
average if the
      user is compromised at a random time.
   - If the user is not prevented from sending new Updates:
   - With TreeKEM, you must wait until everyone sends an Update. We're
      secure again after 24h at most, per policy. The average would
trend toward
      12h if everybody's Updates are uniformly distributed.
      - With RTreeKEM, you must wait until the compromised user sends an
      Update. The user could be compromised immediately after sending
an Update,
      so we're secure again after 12h max. On average, you could say that it's
      more like 6h.

Yes, RTreeKEM has very good best-case behavior when you know exactly who is
compromised and when. But in reality, RTreeKEM can only be expected to
recover twice as fast in the best-case (6h vs 12h), and is the same in the
worst-case (24h).

> I dont follow. If I understood your earlier email correctly you said that
> updates in TreeKEM serve as a signal to others
> guiding their update policy. All I was proposing was to use a much more
> lightweight ACK msg in exactly the same way you

The purpose of an ACK would be to let us know when everyone has processed
the most recent Update message -- that is, when FS has been achieved.
Without an ACK, the fact that RTreeKEM achieves FS faster than TreeKEM is
useless for applying any sort of policy to manage the FS properties of the
group, because nobody knows when FS is achieved.

Although of course, PCS still won't be achieved until everybody Updates. So
everybody Updates, everybody ACKs everybody's Updates, and the number of
messages sent is n^2. That's not scalable so the fact that RTreeKEM
achieves FS faster can't be enforced, which means it can't be relied on.

---

From: Dennis Jackson <[email-masked]>
Date: Wed, 23 Oct 2019 13:38:53 +0100

# PCS and Eviction

I think it is worth noting the trade off between evictions and leaving
members in the group. Evicting a member who is not updating improves the
group's PCS, but it harms the member's PCS. Worse, if the evicted member
subsequently rejoins then the group's PCS is also destroyed.

In short, quick eviction policies are not a panacea for PCS and in fact
are harmful in the current protocol. This motivates some kind of ability
to rejoin a group by proving knowledge of a recent epoch secret. This
was discussed as a way to recover from a faulty update / device state
loss at the last interim, but it would also be useful in this context.

# PFS Frequency

I think it is important to achieve PFS very quickly - ideally after
receiving a message the PFS guarantee should kick in. If a user receives
a message and immediately deletes it, then has their device compromised
it should indeed be gone forever.

Key Point: PFS should be a function of how frequently a user receives
messages, not limited by how frequently they send them, because we might
to 'use' the PFS property after receiving any particular message.

RTreeKEM achieves this, TreeKEM does not. TreeKEM with ACKS does, but
requires O(n) messages per content message which seems infeasible.

# PCS Frequency

I think in most use cases PCS can have a looser time bound than PFS. For
example, as frequently as user sends a message or a most a week is not
inherently unreasonable. On the other hand, a PFS window of a week would
have clear real world repercussions.

On 23/10/2019 02:34, Brendan McMillion wrote:
> [...]
> The purpose of an ACK would be to let us know when everyone has
> processed the most recent Update message -- that is, when FS has been
> achieved. Without an ACK, the fact that RTreeKEM achieves FS faster than
> TreeKEM is useless for applying any sort of policy to manage the FS
> properties of the group, because nobody knows when FS is achieved.
> 
> Although of course, PCS still won't be achieved until everybody Updates.
> So everybody Updates, everybody ACKs everybody's Updates, and the number
> of messages sent is n^2. That's not scalable so the fact that RTreeKEM

I'm not sure this is a good way to think about FS. If a device goes
offline permanently, FS can never be achieved in this definition. FS can
never be enforced in manner you seem to want in any realistic setting.

It is worthwhile clarifying what we mean by PFS in this context. It is
quite common for people to talk about PFS being a property of the
plaintext of a message and ask "at what point is it impossible to
recover that plaintext?". This leads to some requirement on the entire
set of recipients involving deletion of their key material and the
stored plaintext. The involvement of every recipient makes this a
non-local property which can't be meaningfully enforced.

I think a more useful notion is to talk about PFS with respect to some
particular ciphertext and recipient. At what future time, would an
adversary with a copy of the network traffic and the compromised state
of the recipient at that time, be incapable of decrypting the
ciphertext? This definition means we do not have to worry about whether
the application stores the decrypted plaintext or not. Nor do we have to
worry about what other recipients do. This gives us a property that can
actually be enforced locally and will hold globally IF the other
recipients are also honest and received our message.

Best,
Dennis

---

From: Konrad Kohbrok <[email-masked]>
Date: Wed, 23 Oct 2019 16:50:45 +0200

> Let's work an example. Say we set a policy that everyone should try to Update
> every 12h and those that don't will be removed after 24h. One user is
> compromised. How long is it until full FS and PCS is restored?
> 
>   * If the user is prevented from sending new Updates:
>       o Whether you use TreeKEM or RTreeKEM, the group is secure again after the
>         user is removed. So after 24h at most, but 12h on average if the user is
>         compromised at a random time.
>   * If the user is not prevented from sending new Updates:
>       o With TreeKEM, you must wait until everyone sends an Update. We're secure
>         again after 24h at most, per policy. The average would trend toward 12h
>         if everybody's Updates are uniformly distributed.
>       o With RTreeKEM, you must wait until the compromised user sends an Update.
>         The user could be compromised immediately after sending an Update, so
>         we're secure again after 12h max. On average, you could say that it's
>         more like 6h.
> 

You're right in this particular example (although I think that eviction after
24h is pretty draconic). However, if you're looking at larger groups (>10.000
members) you might want to scale down the update frequency to avoid everyone
having to process 10.000 updates of a 10.000-member group every 12h. I'm not an
implementer, but I could imagine that this is pretty costly on battery powered
devices (please feel free to correct me if I'm wrong). In those cases, getting
FS for everyone just by processing a single update of any member is pretty
significant. I guess my expectation is that in large groups, other constraints
that also exist with "simple" TreeKEM will dictate a lower update frequency and
thus PCS guarantees will be rather weak, but that doesn't mean that FS
guarantees have to be.

Also keep in mind that even if it's not very beneficial in the example, we
generally get substantially better FS guarantees at a relatively small price in
bandwidth and local computation. Throwing that away because the upside is not
very big in some cases seems unnecessary to me.

If I understand you correctly, then your concern is that implementers could
think that due to the guarantees provided by RTreeKEM, they can get away with a
lower update frequency while maintaining the same security guarantees. That
seems to be a problem that can be solved by providing clear information on what
guarantees are provided upon an update and/or emphasizing the difference between
FS and PCS.

Cheers,
Konrad

---

From: Yevgeniy Dodis <[email-masked]>
Date: Wed, 23 Oct 2019 14:08:21 -0400

Thank you, Konrad, Joel and Dennis, totally agree with your responses. But
also grateful for Brendan
for voicing his concern, as it clarifies some confusion people might have
about combination of FS and PCS.
Couple of small points to hopefully reach consensus and convince Brendan.

1) As others said, the view "what should be done by users so that given
epoch key k is secure NO MATTER
WHAT THE ATTACKER DOES FROM NOW ON" is useful, but way too limiting. In
particular, under such limiting
and narrow point of view, no "security" is possible if one user is not
processing updates for a while, unless one mandates
"kicking out" such users. Which, as others pointed, is problematic in many
settings. But also does not allow to compare
schemes, as none of them will be secure under such a narrow viewpoint.

2) But even with the above super-narrow and restrictive view of forward
security, RTreeKEM has a clear advantage over
TreeKEM. Imagine the system is currently secure, and some control operation
(update/add/remove) is issued.
What should happen for the current key to be secure no matter what?
- In RTreeKEM, as long as all users PROCESSED this operation, the key is
secure no matter what.
- In TreeKEM, as Brandon pointed out, if you want to be absolutely sure,
more or less every user has to UPDATE
(sometimes you could get lucky and need less, but this is super-dependent
on what happened up to now).

So this is a huge difference - just passively processing something vs
issuing an actual update operation.

3) As others pointed out, a better way to think of FS/PCS combination might
be this. Assuming some sequence of
operations (Init, Add, Remove, Update, Corrupt) happened. Never mind how
and why. The question is which "epoch keys"
are secure? Ignoring the subtlety explained in the paper (about attacker
forcing honest users to "not delete" stuff),
in RTreeKEM, the answer is very clear, intuitive, and clearly OPTIMAL:
- All keys k_t, where all users corrupted at some time t' before t, updated
their keys from time t' to t.

In contrast, I cannot give an easy answer for TreeKEM. On a positive, we
have a polynomial time predicate which
gives an answer to this question. And has to do with graph reachability
question we explain in the paper. On a negative,
this predicate is very non-intuitive, and it very hard to visualize or
understand. In is also intricately specific to TreeKEM
(i.e., cannot be described as some general property of group messaging
protocols). More importantly, in most situations
the set of secure keys under TreeKEM will be dramatically smaller than for
RTreeKEM (see examples given in the
paper, by Joel, and in the slides we sent).

Thus, in many concrete situations "here is what the attacker knows; what is
secure?", RTreeKEM simply leaves more keys
secure.

Yevgeniy

On Wed, Oct 23, 2019 at 10:51 AM Konrad Kohbrok <
[email-masked]> wrote:

> Update

---

From: Brendan McMillion <[email-masked]>
Date: Wed, 23 Oct 2019 16:40:10 -0700

Hey Dennis

> subsequently rejoins then the group's PCS is also destroyed.

I'm not sure I understand what you mean by "member's PCS" or how allowing a
previously compromised user to rejoin harms the group's PCS. Do you mind
explaining in more detail?

> it should indeed be gone forever.

TreeKEM does give you that property, assuming that there's been no
compromises, or you've fully recovered from any compromise. All that
RTreeKEM improves is how quickly the group recovers from compromise. Your
statement that TreeKEM doesn't achieve this, or needs ACKs to achieve it,
is simply not true.

> never be enforced in manner you seem to want in any realistic setting.

It can be enforced. If a user is compromised and goes offline permanently,
then eventually you'll remove them and messages sent *after* the removal
will have forward-security again (assuming nobody else has been
compromised). Forward-security doesn't apply to messages sent while the
compromised user is in the group, that ship has obviously sailed.

---

Hey Konrad

In those cases, getting
> thus PCS guarantees will be rather weak, but that doesn't mean that FS

There's no benefit to processing random Updates from random users. Even in
RTreeKEM, the benefit comes from processing the one Update from the one
compromised user. In TreeKEM, you need to process the compromised user's
Update and then everybody else's, which takes 2-4 times as long or so. So
this is the same, regardless of the group size.

Although I'll say that, especially in large groups, the biggest threat to
forward-security is most likely going to be devices going offline
permanently and being removed once somebody notices. TreeKEM vs RTreeKEM
doesn't improve anything there. Large groups seems like a case where
RTreeKEM is really giving up a lot to optimize the best-case scenario and
ignoring the most-likely scenario.

---

Hey Yevgeniy

In particular, under such limiting
> schemes, as none of them will be secure under such a narrow viewpoint.

I don't think that removing users who aren't updating is controversial.
That's always been my understanding of what we should do with users who
aren't updating.

> issuing an actual update operation.

 That RTreeKEM recovers faster from compromise is a clear benefit of using
the scheme, but it's not a gargantuan difference. It's only recovers about
2-4x faster than TreeKEM best-case, is the same in the worst-case, and
doesn't reduce the total number of Updates that have to be sent.

---

From: Dennis Jackson <[email-masked]>
Date: Thu, 24 Oct 2019 01:38:50 +0100

Hi Brendan,

On 24/10/2019 00:40, Brendan McMillion wrote:
> I'm not sure I understand what you mean by "member's PCS" or how
> allowing a previously compromised user to rejoin harms the group's PCS.
> Do you mind explaining in more detail?

Informally, in this context, the PCS property w.r.t to some set of
participants is the earliest timepoint at which a compromise of the
state of one of the participants allows the adversary to recover the
current state of a participant (or equiv recover a 'current' group
secret). Note: the adversary is required to have been passive at some
point between the earliest compromise and the current timepoint
otherwise no security can hold.

The better the PCS guarantee, the more recently the adversary must have
acted in order to recover the current group secret. Conversely, the PCS
guarantee is weak/non-existent if the adversary could have compromised
an agent a very long time ago and still recover the current group secret.

Let us assume the adversary compromised the initial state of some member
of a group at t=0. In either version of TreeKEM: once that group member
has successfully updated their state, the adversary will no longer have
access to the current group secret. However, if we ever throw out that
member and have them rejoin, the adversary has a way back into the
group. The group does not know whether the initial member rejoined, or
the adversary posing as the initial member. Likewise, the initial member
loses their guarantee on the rest of the group's identity/security.

> RTreeKEM improves is how quickly the group recovers from compromise.
> Your statement that TreeKEM doesn't achieve this, or needs ACKs to
> achieve it, is simply not true.

I'm not sure where the misunderstanding lies so I will expand on this point:

Timepoint: Event
t: User receives a message AEAD(m,...) and decrypts it
t+1: User deletes the message m
t+2: Adversary compromises user's device.

At t+3, can the adversary learn m?

In TreeKEM, the following attack works:

1. At t: the adversary records AEAD(m,...) as it is sent to the user.
2. At t+3, the adversary uses the user's state to decode AEAD(m,...)

This attack doesn't work in RTreeKEM because the user updated their
state after receiving the message at timepoint t. This attack doesn't
work in TreeKEM with ACKs because the user will have updated their state
and sent an update message at t+0.5.

The ability to achieve PFS immediately after receiving a message, rather
than after the transmission of the next message makes a huge difference
in practice. It's clear that having every member of a group ACK each
message isn't going to scale. Having a PFS window of hours, days or
weeks is much much worse than a PFS window of "immediately".

Think about the practical implications for individuals. In many
situations, e.g. inspection at a border, users are aware their device
has been compromised. This guides their future actions (which PCS aims
to protect), but it is typically too late for their past actions (which
PFS aims to protect). Consequently,weak PFS guarantees are much worse in
practice than weak PCS guarantees because future compromise is harder to
predict than deducing past compromise. Although obviously we want strong
forms of both to hold :).

Best,
Dennis

---

From: Yevgeniy Dodis <[email-masked]>
Date: Wed, 23 Oct 2019 20:45:33 -0400

I think I got your point, Brendan, and why we kept speaking past each
other! And we are partially guilty here, by occasionally using the
term "recover" to mean  two different things, contributing to the confusion.

1) "Recover" = achieve PCS. Namely, if attacker corrupts current state of
some user U (including current group key),
how long until the group key is secure, assuming no further corruptions. In
this sense the answer is the same in RTReeKEM
and TreeKEM (or any other secure scheme): corrupted user U should issue an
update (or be removed from group).
So, for multiple corruptions, we should wait until all corrupted uses
UPDATE. And, indeed, we formally show that
TreeKEM is what we call "backward secure" = "achieves PCS in isolation". So
here *you are right* and there is indeed
no security benefit of RTreeKEM over TreeKEM: a corrupted user should
update in order to recover
in *any secure scheme*, more or less by definition.

2) "Recover" = achieve FS. Namely, assuming an UPDATE (or ADD/REMOVE)
operation just happened resulting in a new
group key. What should happen from now until the FUTURE corruption to
guarantee this corruption does not harm the
current key? So I suggest we use the term "preempt" rather than "recover"
for this, as we are not recovering from anything which
happened, but  instead trying to prevent damage from a future hypothetical
corruption. For this notion, the difference between the
schemes is very clear:
 - in RTreeKEM, a user who already moved to the next key (i.,e. merely
PROCESSED)  is not helpful to the attacker. This is
clearly the best we can hope for.
 - in TreeKEM, only if a user  issues an UPDATE one can be sure this user
is not helpful (although sometimes one could get lucky, but this is hard
to describe concisely).

Whether this difference is "gargantuan" is a matter of taste. But I believe
it is, especially in large groups. And here I think
the dual point of view I advocated in my earlier email could be very
useful. Namely, rather than thinking as a policy maker,
what do we do to ensure the given key is secure (against either past or
future corruption), or how long it takes to preempt
(let's use this instead of "recover" going forward!), etc. Think of any
given situation instead: some sequence of operations
happens, including attacker corrupting several states of the users. Never
mind how and why, it just happened.
Which keys are compromised? I believe in majority of even typical cases,
the set of compromised keys in TreeKEM will be noticeably
larger than in RTreeKEM. Certainly in most examples I can think of. To me
this is the reason RTreeKEM offers substantially
more security than TreeKEM.

Do you agree?
Yevgeniy

On Wed, Oct 23, 2019 at 7:40 PM Brendan McMillion <[email-masked]>
wrote:

> I'm not sure I understand what you mean by "member's PCS" or how allowing
> a previously compromised user to rejoin harms the group's PCS. Do you mind
>> "kicking out" such users. Which, as others pointed, is problematic in
>> many settings. But also does not allow to compare

---

From: Yevgeniy Dodis <[email-masked]>
Date: Wed, 23 Oct 2019 20:48:31 -0400

I love your email, Dennis! Will use it in the future. Thank you!

"Think about the practical implications for individuals. In many
situations, e.g. inspection at a border, users are aware their device
has been compromised. This guides their future actions (which PCS aims
to protect), but it is typically too late for their past actions (which
PFS aims to protect). Consequently,weak PFS guarantees are much worse in
practice than weak PCS guarantees because future compromise is harder to
predict than deducing past compromise. Although obviously we want strong
forms of both to hold :)."

---

From: Brendan McMillion <[email-masked]>
Date: Wed, 23 Oct 2019 19:05:55 -0700

> loses their guarantee on the rest of the group's identity/security.

 Ah, when an adversary compromises a user, the user's ClientInitKeys are
also compromised. That's a really interesting point.

> and sent an update message at t+0.5.

This doesn't agree with my understanding of MLS. The way I'm reading your
example, AEAD(m, ...) is application data? There's a section in the spec
titled "Sender Ratchets" that describes how after application data is
decrypted, the symmetric decryption key and anything that you might be able
to derive it from is erased. So all of that erasing happens at t+1 and the
adversary has nothing to work with at t+2.

If on the other hand, AEAD(m, ...) is referring to something in the
handshake messages, that shouldn't be an issue either. Yes, the ciphertexts
can still be decrypted but epoch_secret[n] = HKDF(init_secret[n-1] ||
update_secret) where update_secret is what's decrypted, and
init_secret[n-1] was deleted after the handshake message was processed. The
adversary shouldn't have access to init_secret[n-1], so he can't compute
the next epoch secret.

---

> term "recover" to mean  two different things, contributing to the

I think I was using "recover" to refer to achieving both FS and PCS
simultaneously. Once the adversary is kicked out of the group, you have
PCS, but in TreeKEM you need to wait a bit to ensure future compromises
won't reveal past messages.

Whether this difference is "gargantuan" is a matter of taste.

I agree it's a matter of taste, which is why I don't expect to change my
mind. It's also why you won't hear me complain if the change is adopted
anyways. RTreeKEM has objectively better security.

---

From: Konrad Kohbrok <[email-masked]>
Date: Thu, 24 Oct 2019 09:24:18 +0200

Hi Brendan,

> compromised user. In TreeKEM, you need to process the compromised user's Update
> and then everybody else's, which takes 2-4 times as long or so. So this is the
> same, regardless of the group size.

I might be confused what we're talking about here. In RTreeKEM processing a
random update from a random user allows the processing party to achieve FS.
Meaning that if previous messages and key material are deleted properly, even a
full compromise of the processing party doesn't give the adversary access to
those deleted messages. In regular TreeKEM on the other hand, processing the
update only gives the sending party FS guarantees.

Regarding Dennis' example:

> example, AEAD(m, ...) is application data? There's a section in the spec titled
> "Sender Ratchets" that describes how after application data is decrypted, the
> symmetric decryption key and anything that you might be able to derive it from
> is erased. So all of that erasing happens at t+1 and the adversary has nothing
> to work with at t+2.
>
> If on the other hand, AEAD(m, ...) is referring to something in the handshake
> messages, that shouldn't be an issue either. Yes, the ciphertexts can still be
> decrypted but epoch_secret[n] = HKDF(init_secret[n-1] || update_secret) where
> update_secret is what's decrypted, and init_secret[n-1] was deleted after the
> handshake message was processed. The adversary shouldn't have access to
> init_secret[n-1], so he can't compute the next epoch secret.

You have a good point in that the deletion of the init_secret gives you some
form of FS, but it's somewhat fragile in that if the adversary has gotten hold
of an init_secret in the past by some other means (e.g. compromise of another
party), that fragile FS is gone.

The way I understand MLS (and I might well be confused about this) and the way
FS works is as follows.

Example:
The adversary compromises A and thus gets the init_secret of epoch t. Then A
issues an update, recovering from the compromise. Some messages are sent and
some parties send updates. However, in TreeKEM if the adversary compromises some
party B at epoch t+x that has not issued an update since the compromise of A,
all messages sent in epochs t..t+x are exposed. This is because that party's
HPKE keys have not changed. Those compromised HPKE keys of B allow the adversary
to decrypt the update messages from the wire and, together with the init_secret
of epoch t, lets them decrypt any message that was sent since then. Handshake or
otherwise. In RTreeKEM on the other hand, the HPKE keys are updated as soon as
A's (or any other) update is processed and thus every processing party
immediately achieves FS.

Note, that if I understand the key schedule correctly, deleting the encryption
key doesn't give you FS, because the adversary can still derive all the
necessary keys once they have compromised the handshake secrets and get the
group key as detailed in the example. Feel free to correct me on this, though.

---

From: Raphael Robert <[email-masked]>
Date: Thu, 24 Oct 2019 12:09:41 +0200

Chiming in as well, I think that RTreeKEM starts to sound like a promising improvement to TreeKEM. Thanks to all who participated!

I like the idea that better FS can be achieved at a relatively moderate cost (slightly larger message size).
Particularly in very large groups, it is unreasonable to assume that all members can issue Updates at a high frequency, because this would simply be unfeasible in terms of bandwidth/processing power. RTreeKEM seems to address this particular issue elegantly.

For me the fundamental new development since the interim is that we wouldn’t need to throw away crypto primitives like curve 25519. I would however like to point out that the current proposal with UPKE/clamping means that the usual crypto libraries (libsodium, WebCrypto, etc.) still cannot be used out of the box. This means that vendors/implementors have to implement something at a new layer that is somewhere in between the crypto library and the protocol layer. This poses a new risk, because it requires a higher expertise than just implementing the protocol layer (as it would be the case with TreeKEM). If we move to adopting RTreeKEM, we should pay special attention to that.

Finally I also understand that because of the clamping the actual security level of DH operations with curve 25519 is not as clearly understood as it is the case with X25519 now.

But none of the above is a good enough reason to discard RTreeKEM at this point! I’m looking forward to further discussions!

Raphael

> On 23 Oct 2019, at 00:10, Benjamin Beurdouche <[email-masked]> wrote:
> 
>> On Tue, Oct 22, 2019 at 5:26 PM Karthikeyan Bhargavan <[email-masked] <mailto:[email-masked]>> wrote:
>> Indeed!
>> 
>>> On 22 Oct 2019, at 23:20, Richard Barnes <[email-masked] <mailto:[email-masked]>> wrote:
>>> 
>>>> homomorphically. I.e.. what we need are two algorithms; one to refresh
>>>>> https://www.ietf.org/mailman/listinfo/mls <https://www..ietf.org/mailman/listinfo/mls>
>>>>> 
>>>>

---

From: Brendan McMillion <[email-masked]>
Date: Thu, 24 Oct 2019 10:59:08 -0700

> update only gives the sending party FS guarantees.

 Sorry, I think i confused PCS and FS. But still, if Alice and Bob are
talking and Alice is compromised, then having Bob send an Update doesn't
accomplish anything. In RTreeKEM, Alice needs to send and Update and Bob
needs to process it, and then we know that any messages sent after Bob
processes the Update are forward-secure again. I think we probably agree,
we're just talking past each other.

> party), that fragile FS is gone.

Yes, this is the vulnerability that motivated the development of RTreeKEM,
but you're assuming multiple compromises while I wasn't. I want to state my
position again very clearly:

Assume that a single user was compromised and their state was given to an
adversary. Assume that the compromise has been *immediately healed* by an
Update/Remove message affecting the compromised user, meaning that the
adversary is no longer able to read messages. How long is it until we know
that messages sent after the compromise was healed are again
forward-secure, meaning that no future compromises will expose them?

   - *TreeKEM:* You need to wait until everyone sends an Update.
   - *RTreeKEM:* You need to wait until everyone processes the
   Update/Remove. How do you know everyone has processed the Update/Remove,
   and aren't offline with old key material waiting to be compromised? By
   waiting until everyone sends an Update.

Therefore RTreeKEM offers no material improvement over TreeKEM. RTreeKEM's
improvement over TreeKEM is unmeasurable, unenforceable.

---

From: Dennis Jackson <[email-masked]>
Date: Thu, 24 Oct 2019 20:05:03 +0100

Hi Brendan,

On 24/10/2019 18:59, Brendan McMillion wrote:
> I want to state my position again very clearly:
> 
> Assume that a single user was compromised and their state was given to
> an adversary. Assume that the compromise has been *immediately healed*
> by an Update/Remove message affecting the compromised user, meaning that
> the adversary is no longer able to read messages. How long is it until
> we know that messages sent after the compromise was healed are again
>   * *TreeKEM:* You need to wait until everyone sends an Update.
>   * *RTreeKEM:* You need to wait until everyone processes the
>     Update/Remove. How do you know everyone has processed the
>     Update/Remove, and aren't offline with old key material waiting to
>     be compromised? By waiting until everyone sends an Update.
> 
> Therefore RTreeKEM offers no material improvement over TreeKEM.
> RTreeKEM's improvement over TreeKEM is unmeasurable, unenforceable.

Your perspective seems quite warped. You've selected an arbitrary
scenario and criteria, decided there's no difference between the schemes
in that circumstance and concluded there's no difference between the two
under any circumstances. Spot the problem?

Typically, we analyze security protocols from the perspective of an
adversary who is trying to achieve some goal (learn a secret, forge a
message, etc). It is the adversary we wish to frustrate. RTreeKEM is
significantly better than TreeKEM in this light. There are many
situations (elucidated in earlier examples and the accompanying paper)
in which RTreeKEM resists attacks that TreeKEM does not.

The adversary is absolutely aware of the material improvement of
RTreeKEM over TreeKEM and can measure it quite easily. This difference
has numerous real world impacts, including the scenario I described in
an earlier email. The position that RTreeKEM doesn't offer security
benefits over TreeKEM is factually incorrect.

There are reasonable criticisms of RTreeKEM. It's more complex, it might
require different primitives, it increases message sizes etc. However,
"no material improvement in security" isn't a defendable position.

Regards,
Dennis

---

From: Brendan McMillion <[email-masked]>
Date: Thu, 24 Oct 2019 13:03:05 -0700

I feel like I'm the only one with a realistic perspective, while everyone
else is focusing on the Platonic benefits of RTreeKEM.

Does it use less bandwidth? No.
Does it guarantee faster PCS? No.
Does it guarantee faster FS? No.
Is it easy to implement in JavaScript? No.

---

From: Dennis Jackson <[email-masked]>
Date: Thu, 24 Oct 2019 21:08:09 +0100

>> Does it guarantee faster FS? *Yes*

Fixed that for you :)
On 24/10/2019 21:03, Brendan McMillion wrote:
> I feel like I'm the only one with a realistic perspective, while
> everyone else is focusing on the Platonic benefits of RTreeKEM.
>
> On Thu, Oct 24, 2019, 12:05 PM Dennis Jackson
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     Hi Brendan,
>
>     > I want to state my position again very clearly:
>     >
>     > Assume that a single user was compromised and their state was given to
>     > an adversary. Assume that the compromise has been *immediately healed*
>     > by an Update/Remove message affecting the compromised user,
>     meaning that
>     > the adversary is no longer able to read messages. How long is it until
>     > we know that messages sent after the compromise was healed are again
>     > forward-secure, meaning that no future compromises will expose them?
>     >
>     >   * *TreeKEM:* You need to wait until everyone sends an Update.
>     >   * *RTreeKEM:* You need to wait until everyone processes the
>     >     Update/Remove. How do you know everyone has processed the
>     >     Update/Remove, and aren't offline with old key material waiting to
>     >     be compromised? By waiting until everyone sends an Update.
>     >
>     > Therefore RTreeKEM offers no material improvement over TreeKEM.
>     > RTreeKEM's improvement over TreeKEM is unmeasurable, unenforceable.
>

---

From: Joel Alwen <[email-masked]>
Date: Thu, 24 Oct 2019 22:19:29 +0200

On 24/10/2019 12:09, Raphael Robert wrote:
> This means that vendors/implementors have to implement something at a new layer that is somewhere in between the crypto library and the protocol layer.

Yeah, thats a good point. To me, proposing a reasonable way to build UPKE on top of, say, libsodium is one of the main
things I want to figure out right now (along with better understanding of how Mult() for X25519 can fail). Basically,
this means implementing Mult() from, say, libsodium as going from Mult() -> multiplicative UPKE should be very
straightforward using what I'd expect even the most basic interface for any X25519 implementation to provide. I guess
the challenge here is going to be that both clamp() and the composite order are neither exported nor directly accessible
in libsodium?

In any case, if Mult() needs implementing from scratch then some of the risks I see here are:
- Side-Channels: Mult() operates on secret keys so really it should be implemented with side-channel free code (e.g.
constant time, memory access, etc.). We could mitigate this by proposing a specific implementation similar to whats done
in RFC 7748.
- Memory management: Secret keys being exported out of an X25519 library need to be handled safely in memory (e.g. 0-ed
out before free, don't swap to disk, etc.) Libsodium does provide some memory-management functions for this very purpose.
- Good Entropy: The re-randomizer d' needs to be sampled uniformly and independently. (Again I think most crypto
libraries provide functions to do this.)

Probably a naïve attempt at such a list of risks & mitigations. But making this stuff explicit seems useful for later on
if we put this into the MLS RFCs (not to mention for a separate addendum RFC for 7748 describing the key-rerandomization
technique on its own). So any input on the expected risks (and possible mitigations) would be very appreciated!

On 24/10/2019 12:09, Raphael Robert wrote:
> Finally I also understand that because of the clamping the actual security level of DH operations with curve 25519 is
> not as clearly understood as it is the case with X25519 now.

Not sure I follow what you mean here. One the one hand the UPKE construction is built on top of the X25519 (or X448)
group not just Curve25519. In particular, Mult() uses the same point representation, clamping of scalars and scalar
multiplication as specified in RFC 7748.

On the other hand, if anything, I'd have thought questions about exact bit security are the other way round. It's X25519
that does the clamping so that's where the question about exact bit security would arise no? Clamping isn't inherent to
Curve25519 though; rather its just one way to do scalar multiplication mapping into a prime order sub-group based on the
composite order Curve25519 group. But, as shown by Ristretto, other methods are possible that completely avoid clamping
(and also happen to be both additively and multiplicatively homomorphic). In particular, I believe CDH, DDH and all the
other usual crypto hardness assumptions are equivalent for Curve25519's prime order subgroup and for the Ristretto
group. Not sure thats true for X25519 though.

In any case, I'm no expert on this stuff so feel free to correct me if I'm wrong. :-)

- Joël

---

From: Konrad Kohbrok <[email-masked]>
Date: Fri, 25 Oct 2019 08:02:37 +0200

Hi Brendan,

I'm sorry you feel frustrated with this discussion and I can see why. I agree
with you that we should be very careful with adding new stuff to MLS that
increases costs (be it bandwidth, complexity or otherwise). I also think it's
good to keep an eye on the measurability and enforcability of security
guarantees, which is something I hadn't thought about too much until now.
Although I have to admit that I can't follow your argument with those points
(who is measuring?).

I think one reason we're talking past each other is that to a certain degree I
(and probably a few of the other cryptographers here) am guilty of thinking very
much along the lines of the formal definitions of things like PCS and FS, while
losing sight of the probabilities for certain scenarios in the real world. Under
the formal definition of FS it shouldn't matter if A was compromised in the
past. B should get FS guarantees independent of that.

With a weaker definition of FS there might not be a difference between RTreeKEM
and TreeKEM. However, as Dennis said, it's then easy to lose track of the
scenarios where we're actually secure and the security model becomes complicated
very quickly (especially in a protocol like MLS with a lot of keys flying around
in a lot of different places). I've not been in the community for that long, but
I think sticking to the formal definitions and looking out for nuances and has
proven to be a good idea in the past.

Just as an afterthought: I think the attack would also work in a more likely
real-world scenario, where the adversary is part of the group and subsequently
gets kicked out (maybe a disgruntled employee). Then they have a past init
secret and the attack still works and everyone needs to issue an update to gain
FS. That sounds more likely in a real-world scenario.

Cheers,
Konrad

On 24.10.19 23:03, Brendan McMillion wrote:
> I feel like I'm the only one with a realistic perspective, while everyone else
> is focusing on the Platonic benefits of RTreeKEM.
> 
> On Thu, Oct 24, 2019, 12:05 PM Dennis Jackson <[email-masked]
> <mailto:[email-masked]>> wrote:
> 
>     Hi Brendan,
> 
>     > RTreeKEM's improvement over TreeKEM is unmeasurable, unenforceable..
>

---

From: Richard Barnes <[email-masked]>
Date: Fri, 25 Oct 2019 17:43:47 -0400

FWIW: I did a quick PoC implementing the update primitive on top of
OpenSSL, within the crypto framework of mlspp.  It wasn't trivial, but it
wasn't too painful.  It is almost certainly not constant-time.

https://github.com/cisco/mlspp/pull/59/files#diff-8c57ca8ea136d0bb8c846c77ae5b9e78R665

On Thu, Oct 24, 2019 at 4:19 PM Joel Alwen <[email-masked]> wrote:

> > This means that vendors/implementors have to implement something at a
> new layer that is somewhere in between the crypto library and the protocol
> layer.
>
> Yeah, thats a good point. To me, proposing a reasonable way to build UPKE
> on top of, say, libsodium is one of the main
> things I want to figure out right now (along with better understanding of
> how Mult() for X25519 can fail). Basically,
> straightforward using what I'd expect even the most basic interface for
> any X25519 implementation to provide. I guess
> the challenge here is going to be that both clamp() and the composite
> order are neither exported nor directly accessible
> in libsodium?
>
> - Side-Channels: Mult() operates on secret keys so really it should be
> implemented with side-channel free code (e.g.
> constant time, memory access, etc.). We could mitigate this by proposing a
> specific implementation similar to whats done
> in RFC 7748.
> - Memory management: Secret keys being exported out of an X25519 library
> need to be handled safely in memory (e.g. 0-ed
> out before free, don't swap to disk, etc.) Libsodium does provide some
> memory-management functions for this very purpose.
> - Good Entropy: The re-randomizer d' needs to be sampled uniformly and
> independently. (Again I think most crypto
> Probably a naïve attempt at such a list of risks & mitigations. But making
> this stuff explicit seems useful for later on
> if we put this into the MLS RFCs (not to mention for a separate addendum
> RFC for 7748 describing the key-rerandomization
> > Finally I also understand that because of the clamping the actual
> security level of DH operations with curve 25519 is
> Not sure I follow what you mean here. One the one hand the UPKE
> construction is built on top of the X25519 (or X448)
> group not just Curve25519. In particular, Mult() uses the same point
> representation, clamping of scalars and scalar
> On the other hand, if anything, I'd have thought questions about exact bit
> security are the other way round. It's X25519
> that does the clamping so that's where the question about exact bit
> security would arise no? Clamping isn't inherent to
> Curve25519 though; rather its just one way to do scalar multiplication
> mapping into a prime order sub-group based on the
> composite order Curve25519 group. But, as shown by Ristretto, other
> methods are possible that completely avoid clamping
> (and also happen to be both additively and multiplicatively homomorphic).
> In particular, I believe CDH, DDH and all the
> other usual crypto hardness assumptions are equivalent for Curve25519's
> prime order subgroup and for the Ristretto