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

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

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

On Mon, Feb 4, 2019 at 2:21 PM Richard Barnes <[e-mail]<mailto:[e-mail]>> 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)