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

[Tony Arcieri <[e-mail]>]

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

> 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].)


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/


> 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 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.
>

> 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?
>

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