Subject: [Cfrg] Curve25519 lacks private/public homomorphism?

From: Richard Barnes <[email-masked]>
Date: Mon, 4 Feb 2019 17:21:24 -0500

Hi CFRG,

I'm trying to work through whether the MLS working group can use Curve25519
in a particular way, and was wondering if folks here had any insights.

MLS has a case where it would be useful to be able to be able to implement
the following:

- Given a DH key pair whose private key is held by one set of parties and
public key by another
- Have a third party (holding only the public key) be able to generate a
"delta" such that:
  - The holders the private key can use the delta to update the private key
to a new value
  - The holders of the public key can use the delta to compute the
corresponding new public key

That is, we're looking to use a certain homomorphism in the DH group action
that translates a change in private key to a change in public key.  For
example, with traditional ECDH, you could generate a random number that the
private key holders could multiply with the private key, and the public key
holders could just do a DH operation to multiply the public key by the
delta.  (A sketch in Go here [1].)

When you try to do this with Curve25519 (or Curve448), however, you run
into a problem: `k_list[31] |= 64`.  The X25519 function in RFC 7748 [2]
ensures that the second-most-significant bit of a scalar private key is
always set, but this bit is not necessarily set in the product of two such
scalars.  In other words, there are scalars `ab` such that you can arrive
at `abG` as the result of a DH computation, but never abG will never be a
public key (since `X25519(ab, 9) != abG`).  The mapping from private keys
to public keys is not a homomorphism with regard to addition or
multiplication.

This means we're out of luck with regard to our delta scheme.  If the delta
happens to result in a new private key with its penultimate bit unset, then
it can't actually be used as a private key -- and there's no way for the
delta-generating party to know this.

Is this surprising to people?  Is it a consequence of some property of
Curve25519 that is good for security, or is it just collateral damage?
(Why does the penultimate bit need to be set?)  Do folks have other ideas
for a "homomorphic" construction such as the above that would accommodate
this quirk of Curve25519?

Thanks a lot,
--Richard

[1] https://play.golang.org/p/nyiRcJUDT-p
[2] https://tools.ietf.org/html/rfc7748#section-5

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 4 Feb 2019 15:23:44 -0800

On Mon, Feb 4, 2019 at 2:21 PM Richard Barnes <[email-masked]> wrote:

>   - The holders the private key can use the delta to update the private
> key to a new value

> delta.  (A sketch in Go here [1].)

Welcome to the party!

https://mailarchive.ietf.org/arch/msg/cfrg/lM1ix9R-0tVzhZorQhQlKvi4wpA

That is to say... this is a thorny problem which keeps coming up. The main
thing you might want to look at for an immediate stopgap is Tor's new V3
.onion addresses / hidden services design:

https://trac.torproject.org/projects/tor/ticket/8106

There have been other schemes proposed to address this problem using
blinding factors ala BIP32 non-hardened derivation. However those schemes
ran afoul of the issue you describe below, despite multiple attempts to
avoid it, and are vulnerable to key recovery attacks:

https://forum.web3.foundation/t/key-recovery-attack-on-bip32-ed25519/44

The explosion of complexity that arises from attempting to handle low order
points at the protocol level, even for such a comparatively simple protocol
as this, is what initially lead me to discover Mike Hamburg's work on Decaf
and vicariously the work of Henry de Valence et al on Ristretto:

https://ristretto.group/

> to public keys is not a homomorphism with regard to addition or

This is at least colloquially referred to as "clamping", and yes, the
complexity it glosses over is a huge problem for implementing more advanced
protocols on top of Curve25519. Here's a thread with more background (oh my
the moderncrypto.org cert is expired, how ironic):

https://web.archive.org/web/20180904062814/https://moderncrypto.org/mail-archive/curves/2017/000858.html

> This means we're out of luck with regard to our delta scheme.  If the
> delta happens to result in a new private key with its penultimate bit
> unset, then it can't actually be used as a private key -- and there's no
> way for the delta-generating party to know this.
>

> Curve25519 that is good for security, or is it just collateral damage?

It's a fundamental tradeoff of Edwards curves (of your above options I'd
call it "collateral damaged"). As Harry de Valence put it in a recent talk,
"Edwards curves are simpler... but they push complexity upwards into the
protocol".

Some more discussion here (unfortunately this link isn't in archive.org):

https://moderncrypto.org/mail-archive/curves/2017/000891.html

Per the curve's creator, it's intended for simple protocols like D-H and
signatures only.

(Why does the penultimate bit need to be set?)

My understanding is certain implementations of GF(2^255-19) field
arithmetic (including some of the reference ones, I believe? I don't have a
citation) as well as certain implementations of the Montgomery ladder
require this bit to be set.

> Do folks have other ideas for a "homomorphic" construction such as the
> above that would accommodate this quirk of Curve25519?
>

Ristretto elegantly solves these problems, and provides a prime order group
abstraction which eliminates the incidental complexity of cofactors / low
order groups which would otherwise get pushed into the protocol layer.

I believe the balls are in motion to publish a draft soon which the CFRG
can potentially select as a working group item.

-- 
Tony Arcieri

---

From: Richard Barnes <[email-masked]>
Date: Mon, 4 Feb 2019 18:28:11 -0500

Thanks, Tony.  In parallel, George Tankersley pointed me toward the
ristretto work as well.  There is an Internet-Draft now:

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

Given all this, seems like it could be something worthwhile for this group
to look at!

--Richard

On Mon, Feb 4, 2019 at 6:23 PM Tony Arcieri <[email-masked]> wrote:

>> MLS has a case where it would be useful to be able to be able to
>> implement the following:
>>
> That is, we're looking to use a certain homomorphism in the DH group
>> action that translates a change in private key to a change in public key.
>> For example, with traditional ECDH, you could generate a random number that
>> the private key holders could multiply with the private key, and the public
>> key holders could just do a DH operation to multiply the public key by the
> The explosion of complexity that arises from attempting to handle low
> order points at the protocol level, even for such a comparatively simple
> protocol as this, is what initially lead me to discover Mike Hamburg's work
> on Decaf and vicariously the work of Henry de Valence et al on Ristretto:
>
> https://ristretto.group/
>
>
> Ristretto elegantly solves these problems, and provides a prime order
> group abstraction which eliminates the incidental complexity of cofactors /
> low order groups which would otherwise get pushed into the protocol layer.
>

---

From: Adam Langley <[email-masked]>
Date: Mon, 4 Feb 2019 16:25:35 -0800

> way for the delta-generating party to know this.

Setting the 255th bit is just done to avoid having to worry about infinity
in the Montgomery ladder, I believe. But if you handle infinity explicitly,
doesn't that solve the problem?

(p.s. I'm imagining that an answer would either be a) "no, we thought about
that and it doesn't work because ..." or b) "no idea, what does 'handle
infinity explicitly' mean?". If (b), then I can see about knocking up an
example tomorrow.)

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Rene Struik <[email-masked]>
Date: Mon, 4 Feb 2019 20:53:05 -0500

Dear colleagues:

For any public-private key pair (k,Q:=k*G) for a curve with order n*h, 
where n is prime and h is a small co-factor, and where k is a random 
integer in the interval [1,n-1], (n-k, -Q) is another public-private key 
pair.

If n is close to a power of two (i.e., n ~ 2^m), then either k>=2^{m-1} 
or n-k >= 2^{m-1}, except for cases that are highly unlikely to occur if 
k is truly uniform in [1,n-1] (prob ~ prob of guessing DLP in one try).

So, if n is close to a power of two and h is a power of two, one can 
generate k as follows and shoehorn this into the ugly clamping form 
specified in RFC 7748:
1) Generate k in [1,n-1] uniformly at random;
2) Replace k by n-k if highest bit zero;
3) Set public-private key pair to (h*k, Q:=(h*k)*G).
Note: since DH keys only depend on the x-coordinate of the shared key, 
this works. For signatures, one should obviously not use this, since it 
would pick k from a "half space" (in that case, one could pick k in 
Z_{2*n} and modify the trick above if one cares).

So, if one cares about clamping, one can use the above approach with 
Curve25519 and Curve448 and any k. Alternatively, simply ignore clamping 
(since nobody would else should find out whether one used clamping or not).

This also works for MLS, since the procedure above is described for any 
k in [1,n-1].

This being said, clamping remains a poor hack.

Best regards, Rene

On 2/4/2019 7:25 PM, Adam Langley wrote:
>     When you try to do this with Curve25519 (or Curve448), however,
>     you run into a problem: `k_list[31] |= 64`.  The X25519 function
>     in RFC 7748 [2] ensures that the second-most-significant bit of a
>     scalar private key is always set, but this bit is not necessarily
>     set in the product of two such scalars.  In other words, there are
>     scalars `ab` such that you can arrive at `abG` as the result of a
>     DH computation, but never abG will never be a public key (since
>     `X25519(ab, 9) != abG`).  The mapping from private keys to public
>     keys is not a homomorphism with regard to addition or multiplication.
>
>     This means we're out of luck with regard to our delta scheme.  If
>     the delta happens to result in a new private key with its
>     penultimate bit unset, then it can't actually be used as a private
>     key -- and there's no way for the delta-generating party to know this.
>
>
> Setting the 255th bit is just done to avoid having to worry about 
> infinity in the Montgomery ladder, I believe. But if you handle 
> infinity explicitly, doesn't that solve the problem?
>
> (p.s. I'm imagining that an answer would either be a) "no, we thought 
> about that and it doesn't work because ..." or b) "no idea, what does 
> 'handle infinity explicitly' mean?". If (b), then I can see about 
> knocking up an example tomorrow.)
>
>
> Cheers
>
> AGL
>
> -- 
> Adam Langley [email-masked] <mailto:[email-masked]> 
> https://www.imperialviolet.org
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 5 Feb 2019 03:27:02 +0000

From: Cfrg <[email-masked]> On Behalf Of Adam Langley
Sent: Monday, February 04, 2019 7:26 PM
To: Richard Barnes <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [Cfrg] Curve25519 lacks private/public homomorphism?

On Mon, Feb 4, 2019 at 2:21 PM Richard Barnes <[email-masked]<mailto:[email-masked]>> wrote:
When you try to do this with Curve25519 (or Curve448), however, you run into a problem: `k_list[31] |= 64`.  The X25519 function in RFC 7748 [2] ensures that the second-most-significant bit of a scalar private key is always set, but this bit is not necessarily set in the product of two such scalars.  In other words, there are scalars `ab` such that you can arrive at `abG` as the result of a DH computation, but never abG will never be a public key (since `X25519(ab, 9) != abG`).  The mapping from private keys to public keys is not a homomorphism with regard to addition or multiplication.

This means we're out of luck with regard to our delta scheme.  If the delta happens to result in a new private key with its penultimate bit unset, then it can't actually be used as a private key -- and there's no way for the delta-generating party to know this.

Setting the 255th bit is just done to avoid having to worry about infinity in the Montgomery ladder, I believe. But if you handle infinity explicitly, doesn't that solve the problem?

Actually, the ladder code handles infinity just fine.  DJB put the ‘set the high-order bit’ logic there so that too-clever implementors wouldn’t be tempted to optimize the code by skipping initial 0’s (which would of course add a potential time-based side channel)

---

From: Richard Barnes <[email-masked]>
Date: Tue, 5 Feb 2019 09:01:26 -0500

On Mon, Feb 4, 2019 at 7:25 PM Adam Langley <[email-masked]> wrote:

> 'handle infinity explicitly' mean?". If (b), then I can see about knocking
> up an example tomorrow.)
>

I'm more in the (b) camp, in the sense that it's not clear to me what you
mean by that phrase.  As Scott says, it seems to me that the Montgomery
ladder works fine with infinities [0] as intermediate values.  It also
seems like setting the top bit doesn't guarantee that you don't get
infinity as output, since RFC 7748 still has you do an explicit check for
that.

In any case, I'm not sure it's worth spending a lot of time on this.  The
question underlying my question was whether it was possible to use
off-the-shelf Curve25519 libraries to implement a delta scheme, and it's
becoming pretty clear that the answer to that is "no".

--Richard

[0] I'm assuming that by "infinity" you mean the point at infinity, i.e.,
the identity of the curve group

---

From: Richard Barnes <[email-masked]>
Date: Tue, 5 Feb 2019 09:15:14 -0500

Hi Rene,

Interesting idea.  It might run into one protocol constraint I may not have
stated clearly, but there may be some utility here.

The constraint I'm worried about is that we need the delta-generating party
to be able to inform the public- and private-key holders of their
respective updates in one message, without the need for a follow-up message
from the private key holders.  (This is because MLS is designed to handle
highly asynchronous messaging.)

That said, it seems like you could run a scheme like the following:

0) Given a key pair (a, a*G) that we are updating...
1) Delta generator generates a random d in [1, n-1]
2) Delta generator encrypts `d` to the holder of `a` (e.g., with ECIES) and
sends it
3) Delta generator sends everyone else *both* d*a*G and (n-d)*a*G
4) Private key holders use whichever of d or (n-d) has its high-order bit
set
5) Public key holders use both public keys when encrypting to the private
key holders

That is, the private key holders can see which of d or (n-d) works, so they
can choose.  But the public-key holders can't see that, so they have to
enable either of the two values to be used.

With that mechanism in hand, it seems like the question for the WG is
whether the prefer to, on the one hand, make a pretty significant special
affordance for Curve25519, or on the other hand, use some newer, less
widely vetted / widely available elliptic curve math (either Ristretto or a
revised Curve25519).

Thanks,
--Richard

On Mon, Feb 4, 2019 at 8:53 PM Rene Struik <[email-masked]> wrote:

> If n is close to a power of two (i.e., n ~ 2^m), then either k>=2^{m-1} or
> n-k >= 2^{m-1}, except for cases that are highly unlikely to occur if k is
> truly uniform in [1,n-1] (prob ~ prob of guessing DLP in one try).
>
> would pick k from a "half space" (in that case, one could pick k in Z_{2*n}
> and modify the trick above if one cares).
>
> This also works for MLS, since the procedure above is described for any k
> in [1,n-1].
>
> On Mon, Feb 4, 2019 at 2:21 PM Richard Barnes <[email-masked]> <[email-masked]>
> wrote:
>
> Cfrg mailing [email-masked]://www.irtf.org/mailman/listinfo/cfrg
>
>
> --

---

From: Dan Brown <[email-masked]>
Date: Tue, 5 Feb 2019 17:20:12 +0000

Hi Richard,

Could you not just add delta to the private key (instead of multiplying the private key)?  (Add [delta]G to the public key.)  

This seems to meet your four bullet points, though I did no follow-up reading.

Adding delta is certainly NOT a morphism of the DH group, though it is a morphism of the curve, etc., etc.  Maybe you need the group morphism property for a sophisticated reason that you forgot to list?

Anyway, if delta is small enough, say delta<2^200, there is little chance of disturbing the top bit.  (If some bottom bits are fixed, set the few bottom bits of delta to zero.)

By the way, it is not yet clear to me why these key “updates” would be “useful”.  (Either added or multiplied).

Best regards,

Dan

From: Cfrg <[email-masked]> On Behalf Of Richard Barnes
Sent: Monday, February 4, 2019 5:21 PM
To: CFRG <[email-masked]>
Subject: [Cfrg] Curve25519 lacks private/public homomorphism?

Hi CFRG,

I'm trying to work through whether the MLS working group can use Curve25519 in a particular way, and was wondering if folks here had any insights.

MLS has a case where it would be useful to be able to be able to implement the following:

- Given a DH key pair whose private key is held by one set of parties and public key by another

- Have a third party (holding only the public key) be able to generate a "delta" such that:

  - The holders the private key can use the delta to update the private key to a new value

  - The holders of the public key can use the delta to compute the corresponding new public key

That is, we're looking to use a certain homomorphism in the DH group action that translates a change in private key to a change in public key.  For example, with traditional ECDH, you could generate a random number that the private key holders could multiply with the private key, and the public key holders could just do a DH operation to multiply the public key by the delta.  (A sketch in Go here [1].)

Is this surprising to people?  Is it a consequence of some property of Curve25519 that is good for security, or is it just collateral damage?  (Why does the penultimate bit need to be set?)  Do folks have other ideas for a "homomorphic" construction such as the above that would accommodate this quirk of Curve25519?

Thanks a lot,

--Richard

[1] https://play.golang.org/p/nyiRcJUDT-p <https://urldefense.proofpoint.com/v2/url?u=https-3A__play.golang.org_p_nyiRcJUDT-2Dp&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=hnuASub6WZC2yU-gN0ugWh-Kr8Pkiu8X95Nhs3Reebc&s=AO4-p_x3NlAk3S64sOFbVecbdF_UeI2GKxro-5gM2GM&e=> 

[2] https://tools.ietf.org/html/rfc7748#section-5 <https://urldefense.proofpoint.com/v2/url?u=https-3A__tools.ietf.org_html_rfc7748-23section-2D5&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=hnuASub6WZC2yU-gN0ugWh-Kr8Pkiu8X95Nhs3Reebc&s=BXy82rs-JetAjAhHvyYL8QEgrl8r9nHj4f2ItnvPhWw&e=>

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 5 Feb 2019 09:27:00 -0800

On Tue, Feb 5, 2019 at 9:20 AM Dan Brown <[email-masked]> wrote:

> Could you not just add delta to the private key (instead of multiplying
> the private key)?  (Add [delta]G to the public key.)
>

Using addition instead of multiplication is the BIP32 method, and it has
the same problems. See the Ed25519-BIP32 key recovery attack here:

-- 
Tony Arcieri

---

From: Dan Brown <[email-masked]>
Date: Tue, 5 Feb 2019 19:38:31 +0000

Hi Tony, Richard,

Hmm, I thought that this question was about X25519, but now it seems to be about EdDSA (Ed25519)?

I see that BIP32 talks about updating the “after hash” private key?

Is such modification the key generation generally considered compliant to CFRG spec RFC 8032? 

Best regards,

Dan

From: Tony Arcieri <[email-masked]> 
Sent: Tuesday, February 5, 2019 12:27 PM
To: Dan Brown <[email-masked]>
Cc: Richard Barnes <[email-masked]>; CFRG <[email-masked]>
Subject: Re: [Cfrg] Curve25519 lacks private/public homomorphism?

On Tue, Feb 5, 2019 at 9:20 AM Dan Brown <[email-masked] <mailto:[email-masked]> > wrote:

Using addition instead of multiplication is the BIP32 method, and it has the same problems. See the Ed25519-BIP32 key recovery attack here:

https://forum.web3.foundation/t/key-recovery-attack-on-bip32-ed25519/44 <https://urldefense.proofpoint.com/v2/url?u=https-3A__forum.web3.foundation_t_key-2Drecovery-2Dattack-2Don-2Dbip32-2Ded25519_44&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=mf6j6fOClApRsArWE9wqI1rEGUVkfxZ0aXWmn35nK_c&m=ZDhvIILc-chTe68I4OmZ1clkTv10k3nhZwQz2dLJ6H8&s=Cye0i2Un5eqpM21QPjLvpL7e1YJtsEwXDhj57FUgL9o&e=> 

-- 

Tony Arcieri

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 5 Feb 2019 12:05:03 -0800

> Hmm, I thought that this question was about X25519, but now it seems to be

Correct, where the original question was about D-H (X25519), Ed25519-BIP32
describes a similar scheme based on addition instead of scalar
multiplication, but in this case, for the purpose of signatures.

The basic idea is the same though, and underneath both schemes are
"Curve25519", with Ed25519-BIP32 using the "edwards25519" (RFC 8032
terminology) form. You could implement an Ed25519-BIP32 like scheme in
terms of X25519, or vice versa, but you will encounter the same problems.

> I see that BIP32 talks about updating the “after hash” private key? Is
> such modification the key generation generally considered compliant to CFRG
> spec RFC 8032?
>

This is indeed a big problem. I'm not going to attempt to play RFC lawyer,
but rather just say that in practice no Ed25519 library provides any of
this in the public API. In practice what I've seen, over and over again in
codebases where people try to extend Ed25519 with these features, is they
take the code from ed25519.c/go/etc, make the private APIs public, and muck
around with it at an extremely low level, sometimes just naively removing
clamping ("what is this for?"), or clamping repeatedly and therefore losing
key strength.

Without something like Ristretto, I'm not sure it's *possible* to define a
safe API that would allow an RFC 8032-compliant Ed25519 signer to derive a
unique private scalar based upon some agreed upon protocol which the
verifier can also do offline without coordination from the signer, in such
a way that is *misuse resistant* and "pluggable", i.e. not coupled to a
particular key derivation / blinding scheme.

Even if it were possible, I still don't think it's a good idea, and that's
kind of a shame, because it means Ed25519 signatures aren't composable in a
way, say, ECDSA signatures over a curve of prime order are, such as in the
original "BIP32" (which is used in conjunction with secp256k1).

-- 
Tony Arcieri

---

From: Dmitry Khovratovich <[email-masked]>
Date: Tue, 5 Feb 2019 22:18:02 +0100

> https://forum.web3.foundation/t/key-recovery-attack-on-bip32-ed25519/44

This is not an attack on Ed25519-BIP32, as it violates the protocol
description in having the hierarchy of 2^30 levels instead of permitted
2^20. In such a way a secret key publication can be called an "attack".