7
$\begingroup$

I have no mathematical knowledge about this, but I just read in RFC 7748 the following:

Designers using these curves should be aware that for each public key, there are several publicly computable public keys that are equivalent to it, i.e., they produce the same shared secrets. Thus using a public key as an identifier and knowledge of a shared secret as proof of ownership (without including the public keys in the key derivation) might lead to subtle vulnerabilities

Does that mean that multiple Curve25519 public keys can produce the same shared key produced by X25519? I just don't understand.

Does this mean that key servers (let's say that such key servers even verify the ownership of these public key using sending an encrypted challenge to the claimant) using Curve25519 are not a good idea?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
12
$\begingroup$

There are two independent sources of equivalent public keys for the X25519 function.

The first is rather simple: A public key is an integer u between $0$ and $2^{255}-1$ that represents an element of the finite field $\mathrm{GF}(2^{255}-19)$. Hence, for all $i\in\{0,\dots,18\}$, the integer $2^{255}-19+i$ represents the same field element as the integer $i$.

The second source of equivalence is a bit more specific. In a nutshell, the X25519(k,u) function is defined as follows:

  • Clamp the secret key k, forcing bits $\{0,1,2,255\}$ to zero and bit $254$ to one.
    In particular, note that this means the clamped scalar $k'$ is a multiple of $8$.
  • Compute the scalar product $[k']P$, where $P$ is a Curve25519 point with $x$‑coordinate u.
  • Return the $x$-coordinate of $[k']$P.

Now Curve25519 has cofactor $8$, hence there exist nonzero points $Q$ of order dividing $8$. For any such point, the public key $P+Q$ is equivalent to the public key $P$: Since $k'$ is a multiple of $8$, we have $$ [k']Q = [k'/8][8]Q = [k'/8]\infty = \infty $$ and therefore (using the distributive law) $$ [k'](P+Q) = [k']P + [k']Q = [k']P+\infty = [k']P \text. $$

For a concrete example, the two public keys

629fb7d4a50e0339edfdfae1464fedb848dd35f25c5fecd3d3f5af61654a691d
b53677c430779b050cd6db7e1f4ca6735e07b30a61711f45a88e710790af772a

will, for every secret key, give identical shared secrets using X25519.

Improve this answer
$\endgroup$
1
  • $\begingroup$ As an extra detail on this answer, if you wanted to prevent these P+Q public keys, the best way is to either require proof of possession of the associated private key when accepting a public key, or to include the actual public key in the KDF info/context. If you wanted to reject such keys through validation I'm not aware of anything better than performing (unclamped) scalar multiplication with the order of the generator point, n. For a normal public key, $[n]P = \infty$ whereas in this case we'll have $[n]P + [n]Q = \infty + [n]Q \neq \infty$. This is expensive, so prefer the other options. $\endgroup$
    – Neil Madden
    Nov 26, 2022 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.