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

[Richard Barnes <[e-mail]>]

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 <[e-mail]> wrote:

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