Subject: [MLS] UPKE for X25519/X448

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

Hey,

This is a follow up to the earlier Re-Randomized TreeKEM email. (Its a
separate thread as it changes whats in that first email and I didn't
want it getting lost in the other thread when people evaluate whether to
adopt RTreeKEM for MLS.)

In short, after some very helpful back and forth with Mike Hamburg, it
is looking like we have a reasonable way to do Re-randomizable TreeKEM
(RTreeKEM) based on the X25519/X448 ciphersuits. That would mean we no
longer have to choose between RTreeKEM and those suits. IMO that removes
the biggest barrier to using RTreeKEM.

To be clear, we're still doing a some coding & testing to build
confidence. And we will also run it past the CFRG / a few more ECC
experts besides Mike, to make absolutely sure it works as intended.
But at this point we are pretty optimistic already.

The rest of this email contains the details for how RTreeKEM can be made
to work with the X* groups.

- Joël

-----------------------------------------------------------

Essentially, all we really need for RTreeKEM is to build "Updateable
Public Key Encryption" (UPKE) as defined in [1].

Rather than the construction in [1] which is based additive
key-homomorphism we can use the following construction based on a
multiplicative key-homomorphism. (It turns out the later is easier to
implement for X* groups than the former.)

To minimize the diff between current TreeKEM and this new variant of
RTreeKEM, the new construction is formulated it to use HPKE and HKDF as
black boxes.

Inherited from Cipher Suite
---------------------------
- sksize = # of bits for secret key scalars. (e.g. 32 for X25518)
- order = order of prime-order subgroup (e.g. as in RFC 7748)
- DH(A,b) : A Diffie-Hellman function. (E.g. X25519 or X448)
- Mult(a,b) : Multiplication of secret keys. See below.

Multiplication
--------------
- NIST curves : Mult(a,b) = a*b mod order.
- X25519 : let Clamp(k) = decodeScalar25519(k) as in RFC 7748.
- X448 : let Clamp(k) = decodeScalar448(k) as in RFC 7748.

For both X25519 & X448 use
 Mult(a,b) {
   c = (Clamp(a) - Clamp(b)) mod order
   if msb(c) = 0
     c = (order - c) mod order
   return c
 }

UPKE Construction (from HPKE & HKDF)
------------------------------------
- UPKE-KeyGen = HPKE-KeyGen

- UPKE-Encrypt(pk, m):
  d'  <-- {0,1}^secpar
  d   := HKDF(sksize, d', "", "derive UPKE delta")
  c1, context := HPKE.SetupBaseI(pk, "")
  c2  <-- context.Seal("", d' || m)
  pk' := DH(pk, d)
  return ((c1, c2), pk')

- UPKE-Decrypt(sk, (c1, c2)):
  epk, context := HPKE.SetupBaseR(c1, sk, "")
  d' || m := context.Open("", c2)
  d := HKDF(sksize, d', "", "derive UPKE delta")
  sk' := Mult(sk, d)
  return (m, sk')

References
----------
[1] http:\\ia.cr\2019\1189.

---

From: Benjamin Beurdouche <[email-masked]>
Date: Mon, 21 Oct 2019 23:57:12 +0200

That look excellent !
If that works as expected, that would indeed be very nice… : )

B.

> On Oct 21, 2019, at 11:20 PM, Joel Alwen <[email-masked]> wrote:
> 
> Hey,
> 
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

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

Thank you Benjamin.

We hope there will be no more surprises, like the lack of additive
homomorphism for the X-curves. So we would certainly love to get
guidance from other people on the list, in case we missed something else.

There is definitely some cost involved, but we hope it is small, and we
believe using UPKE in place of PKE gives a substantial security
enhancement to justify the (small) cost.

We could also follow Karthik's nice suggestion to compare our scheme with
"naive" UPKE, where for each updated tree node one prepares K (say, 100)
public-secret key pairs, and erases them one-by-one as they get used on
various co-paths. If one runs out of fresh pairs, the last key pair is not
erased, and gets used until the update happens. Ironically, K=1 corresponds
to the current scheme, so in this sense the naive scheme -- call it
K-TreeKEM -- is a natural generalization of TreeKEM. However, we believe
already for small K (like 3 or 4), K-TreeKEM will start becoming less
efficient overall than RTreeKEM, while still offering inferior security.
But this is a good thing to test if people are interested.

Thank you in advance for your comments,
Yevgeniy

---

From: Richard Barnes <[email-masked]>
Date: Tue, 22 Oct 2019 00:41:05 -0400

FWIW, I tried to update this and it appears not to work, either in the
sense of pk' = pk(sk'), or in the sense of pk' and sk' producing equivalent
DH results.

https://gist.github.com/bifurcation/795dd09ca399acfda5db87bc825a90ca

It seems odd to me that the *Mult* functions computes Clamp(a) - Clamp(b),
instead of multiplying ... well anything.  But even when I changed the Sub
to a Mul in my test code, things still didn't work.

The problem I observed in the CFRG thread on this long ago is that there
are X25519 DH outputs that are not valid public keys, which I think implies
that you can't have any homomorphism in which the DH function is the public
transformation.  Maybe that's what we're running into here?

Also possible that I'm just missing something :)

---

From: Joel Alwen <[email-masked]>
Date: Tue, 22 Oct 2019 13:18:26 +0200

Hey Richard,

Thanks for the code to help testing this stuff!

On 22/10/2019 06:41, Richard Barnes wrote:
> sense of pk' = pk(sk'), or in the sense of pk' and sk' producing
> equivalent DH results.
> 
> It seems odd to me that the *Mult* functions computes Clamp(a) -
> Clamp(b), instead of multiplying ... well anything.

The reasoning here is based on the view of X25519(pk, s) first does
Clamp(s)->s' and then pk^(s') mod order. So Mult() first maps the scalar
inputs the their clamped representatives and only then does the
multiplication.

But it could be this is not the right view of X25519 (though, in my
defense, Mike H. also seemed to think the construction should work and
he knows way more about this stuff than I do).

> are X25519 DH outputs that are not valid public keys, which I think
> implies that you can't have any homomorphism in which the DH function is
> the public transformation.  Maybe that's what we're running into here?

Indeed, from a formal mathematical point of view Mult() is *not* aiming
to be a multiplicative homomorphism because of some rare exceptions. But
Mike believed that the probability of running into such an output, when
using uniform randomly chosen inputs was around 1/2^{-126} or so.
Moreover, for X448 he thought the probability was 0. To be clear, he
wasn't 100% and recommended testing.

> Also possible that I'm just missing something :)

Yeah, same here. I'll see if I can figure out whats going on here and
get back to the mailinglist if I make any progress.

- Joël

> On Mon, Oct 21, 2019 at 5:21 PM Joel Alwen <[email-masked]
> <mailto:[email-masked]>> wrote:
> 
>     Hey,
> 
>     [1] http:\\ia.cr <http://ia.cr>\2019\1189.
> 
>     [email-masked] <mailto:[email-masked]>

---

From: Joel Alwen <[email-masked]>
Date: Tue, 22 Oct 2019 15:19:32 +0200

Ah crap. I had a typo in my original email in this thread. Mult() is supposed to _multiply_ the clamped values, not
subtract them. *facepalm*

So the correct pseudocode for Mult() is:

 Mult(a,b) {
   c = (Clamp(a) * Clamp(b)) mod order
   if msb(c) = 0
     c = (order - c) mod order
   return c
 }

Sorry about that. Unfortunately, I think the code *still* doesnt give us what we want though. I'll keep playing with this...

- Joël

On 22/10/2019 06:41, Richard Barnes wrote:
> FWIW, I tried to update this and it appears not to work, either in the sense of pk' = pk(sk'), or in the sense of pk'
> and sk' producing equivalent DH results.
> 
> It seems odd to me that the *Mult* functions computes Clamp(a) - Clamp(b), instead of multiplying ... well anything. 
> But even when I changed the Sub to a Mul in my test code, things still didn't work.
> 
> The problem I observed in the CFRG thread on this long ago is that there are X25519 DH outputs that are not valid public
> keys, which I think implies that you can't have any homomorphism in which the DH function is the public transformation. 
> Maybe that's what we're running into here?
> 
> On Mon, Oct 21, 2019 at 5:21 PM Joel Alwen <[email-masked] <mailto:[email-masked]>> wrote:
> 
>     Hey,
>

---

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

EUREKA!

I got it to work with the following changes:

1) clamp both scalars befor doing the Mul (instead of just le2bn)
2) using the composite order (n25519*8) instead of prime order (n25519)
3) mul instead of sub
4) condition on bit 254 == 0 instead of 255.

Here's the (now working I think) code. https://play.golang.org/p/UaFVV6HG-Nf

Reasoning for changes:
1) Was as originally intended. Basically X25519 clamps the scalar, then does exponentiation.
2) Mike had already mentioned I should use composite not prime order. I just missed it. more *facepalm*
3) Multiplicative not additive homomorphism
4) Goal here is msb should be set to 1. If it isn't then we need the negative. Basically, msb is bit 254 instead of 255.

- Joël

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Tue, 22 Oct 2019 17:02:16 +0200

Sorry if this is already in the paper, but a question.

>  return (m, sk’)

I believe it is important for the recipient to do some validation before returning from UPKE-Decrypt.

For example, what if the (malicious) sender set d to “0” (whatever that means in the DH group).
This would mean that the resulting key sk’ becomes “0” too, hence a non-member has been able to force the recipient group’s private key to a particular value, which is not ideal.
What conditions should we add to avoid this kind of key-forcing attack from happening?

-Karthik

---

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

Good question!

I'll see if I can think of anything intelligent to say about it. :-)

But one thing that comes to mind is that the sender gets to choose "only" d', not d. Instead d := HKDF(d') so to get d=0
you'd have to first invert HKDF.

- Joel

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Tue, 22 Oct 2019 18:29:50 +0200

Yes, the sender would have to find a “d’” such that HKDF(sksize, d', "", "derive UPKE delta”) falls in a small set of values.
This is a small risk, but it can be further reduced if we used epk in the derivation.
E.g. why not define:

d := HKDF(sksize, d’, epk, “derive UPKE delta”)

This way, the attacker has to choose d’ based on the node’s old public key, which makes it harder for it to do malicious things.

-Karthik

> On 22 Oct 2019, at 17:05, Joel Alwen <[email-masked]> wrote:
> 
> Good question!
>

---

From: Yevgeniy Dodis <[email-masked]>
Date: Tue, 22 Oct 2019 13:45:08 -0400

Good point, Karthik, we should definitely add this check (and possibly
something else).

As a small theoretical note, in our current model the users are considered
honest rather than malicious.
However, to model and prevent double-join attacks, the attacker is allowed
to request honest people not
to erase their local randomness (e.g., things like d' used above). So this
is why in our current description
we do not have to explicitly worry about d' being malicious.

We are pretty sure that with a check like the one you suggest we can also
withstand adversarial randomness
for UPKE. But we did not explore this yet - it is on the next to-do list.
In general, we don't consider too many insider
attacks (beside double join) for now, since TreeKEM and variants are not
secure against them anyway. Great
direction for the future.

Yevgeniy

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

> Yes, the sender would have to find a “d’” such that HKDF(sksize, d', "",
> "derive UPKE delta”) falls in a small set of values.
> This way, the attacker has to choose d’ based on the node’s old public
> key, which makes it harder for it to do malicious things.
>
> -Karthik
>
>
> > But one thing that comes to mind is that the sender gets to choose
> "only" d', not d. Instead d := HKDF(d') so to get d=0
> >> This would mean that the resulting key sk’ becomes “0” too, hence a
> non-member has been able to force the recipient group’s private key to a
> particular value, which is not ideal.

---

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

Hi Yevgeniy,

Thanks for the clarification,

We have been formally analyzing TreeKEM against malicious insiders and it actually has some nice invariants.

In particular: the secret (and private key) for each node is only determined by the members of the
subtree rooted at that node. So if one of these subgroup members is malicious, it can of course
set the subgroup key to whatever it likes. But outsiders do not have the ability to influence a subgroup’s keys.
(There is an exception to this rule for late joiners, making the invariant a bit more complicated than the one I have informally stated here.)

I believe this agains-outsiders guarantee is a good invariant to have, and some of my questions about UPKE were in order to see how we could keep a version of this invariant.

Best,
Karthik

> On 22 Oct 2019, at 19:45, Yevgeniy Dodis <[email-masked]> wrote:
> 
> Good point, Karthik, we should definitely add this check (and possibly something else).
> 
> As a small theoretical note, in our current model the users are considered honest rather than malicious.
> However, to model and prevent double-join attacks, the attacker is allowed to request honest people not
> to erase their local randomness (e.g., things like d' used above). So this is why in our current description
> We are pretty sure that with a check like the one you suggest we can also withstand adversarial randomness
> for UPKE. But we did not explore this yet - it is on the next to-do list. In general, we don't consider too many insider
> attacks (beside double join) for now, since TreeKEM and variants are not secure against them anyway. Great 
> On Tue, Oct 22, 2019 at 12:30 PM Karthikeyan Bhargavan <[email-masked] <mailto:[email-masked]>> wrote:
> > On 22 Oct 2019, at 17:05, Joel Alwen <[email-masked] <mailto:[email-masked]>> wrote:
> > 
> > Good question!
> > 
> >>> [1] http:\\ia.cr <http://ia.cr/>\2019\1189.
> >>> 
> >>> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> >> 
> > 
> > https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>
> 
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>

---

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

Hi Karthik.

Yes, our scheme already withstands malicious randomness when analyzed as
UPKE in isolation. We actually gave
both definitions in the paper, and satisfy the strongest. But we have not
propagated the stronger UPKE notion
into a formal continuous group key agreement game. Will not be hard, but we
wanted to get the paper out.

We have not captured yes a clean way to get fine-grained resilience to
insider attacks at the level you are suggesting,
since in the general notion there are no trees, or specific TreeKEM
structure (however, our safety predicate for TreeKEM
is scheme specific, --- because it has to be, --- which cold be viewed as
yet another advantage of RTreeKEM). But
resilience to bad update randomness is correlated to the property you are
saying: even though people outside a given sub-ttree
could somehow influence public-secret keys (by being on co-path and using
UPKE in place of PKE), they cannot violate
security of these nodes by being malicious. Hopefully we will add this to
the paper soon, but for now we wanted to make sure
we can support the X-curves, which we hopefully can.

Yevgeniy

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

> (There is an exception to this rule for late joiners, making the invariant
> a bit more complicated than the one I have informally stated here.)
>
> I believe this agains-outsiders guarantee is a good invariant to have, and
> some of my questions about UPKE were in order to see how we could keep a
> version of this invariant.
>
> Best,
> Karthik
>
>
>