3
$\begingroup$

Suppose that Alice has an X25519 key pair $\{S_A,P_A\}$ (secret and public key, respectively). Using randomly selected X25519 public keys $\{P_*\}$ (such that $P_A\notin \{P_*\}$), Alice calculates several values $X_* = \operatorname{X25519}(S_*,P_*)$.

She then repeatedly flips a (fair) coin. Each time, if the result is heads, she sends a (truly) random 256-bit string to Bob. If the result is tails, she sends some value in $\{X_*\}$ to Bob. Bob does not know the result of the coin flip.

I know that the output of the ECDH function is not uniformly random, so how can Bob determine—with more than 50% accuracy—whether Alice has sent him a random string or a value from the set $\{X_*\}$?

Bob knows $P_A$ and the curve parameters, but he does not know the elements of the set $\{X_*\}$.


This question is distinct from Distinguishing x25519 public keys from random?, which asks about distinguishing X25519 public keys from random. This question asks about distinguishing the output of the X25519 function (i.e., the shared secret computed with the ECDH function) from random. Given two secret, public key pairs $\{S_A,P_A\}$ and $\{S_B,P_B\}$, that is, this question asks how to distinguish $\operatorname{X25519}(S_A,P_B)$ (or, equivalently, $\operatorname{X25519}(S_B,P_A)$) from random, while the other question asks how to distinguish $P_A$ and $P_B$ from random.


Edit: Fixed names of variables. $S_*$ was intended to be $X_*$.

$\endgroup$
6
  • 1
    $\begingroup$ Note that I don't see how this question is distinct from the last link. $\endgroup$
    – kelalaka
    Commented Jan 12, 2023 at 19:47
  • $\begingroup$ +1 agree it is either , very identical, or a small change, - @BenZ how is the question distinct ? $\endgroup$ Commented Jan 12, 2023 at 19:53
  • $\begingroup$ @WilliamMartens The other question asks about distinguishing X25519 public keys from random. This question asks about distinguishing the output of the X25519 function (i.e., the shared secret computed with the ECDH function) from random. Given two secret, public key pairs $\{S_A,P_A\}$ and $\{S_B,P_B\}$, that is, this question asks how to distinguish $\operatorname{X25519}(S_A,P_B)$ (or, equivalently, $\operatorname{X25519}(S_B,P_A)$) from random, while the other question asks how to distinguish $P_A$ and $P_B$ from random. $\endgroup$ Commented Jan 13, 2023 at 2:40
  • 1
    $\begingroup$ @BenZ. Ohh okay, put that in the question :) so we know exactly that what it means $\endgroup$ Commented Jan 13, 2023 at 10:55
  • 1
    $\begingroup$ Done—thank you for the feedback! $\endgroup$ Commented Jan 14, 2023 at 17:32

2 Answers 2

3
$\begingroup$

Alice generates several $X_* = \operatorname{X25519}(S_*,P_*)$.

If Alice uses the X25519 function, the output will belong to $\mathbb{F_{2^{255}-19}}$ and will represent a $X$-coordinate of a point in the large prime-order subgroup of curve25519. This information can be used by Alice to distinguish from random 256 bit strings.

  1. Bob can look at the most significant bit $MSB(X_*)$, that due to little endian representation of X25519 this will be the eight bit from the right. This is zero for all public keys generated with $\operatorname{X25519}$ function. So if $MSB(X_*) = 1$ then Bob knows this is the random string.
  2. Given $X_*$ with $MSB(X_*)=0$ Bob can compute the square root of the value $X_*^3 + 486662X_*^2 + X_*$ in $\mathbb{F_{2^{255}-19}}$. If $X_*$ doesn't have a square root in the field then Bob knows this is the random string. On average, about half the value won't have a valid square root.

This two combined information allows Bob to distinguish with certainty that about $\frac{3}{4}$ of the random string are indeed random strings. This can be used to have an overall guessing accuracy of 75%.

Please note that the proper way of doing what the user is asking, without giving any advantage to Bob, would be to use the elligator scheme to encode public key points, but then there is a restriction on the usable public keys.

$\endgroup$
-1
$\begingroup$

The 248'th bit (big-endian) in the scalar multiplication is always set to zero.

$\endgroup$
3
  • $\begingroup$ What about the lower bits? $\endgroup$
    – kelalaka
    Commented Jan 12, 2023 at 18:23
  • $\begingroup$ I see no reasons why the 248'th bit (big-endian) of the result of a scalar multiplication would be 0, in whatever common coordinate system. And I see no other well-defined meaning to the statement made. $\endgroup$
    – fgrieu
    Commented Jan 12, 2023 at 18:35
  • $\begingroup$ See 1st point in Ruggero's answer. An eighth bit from the right is 248th bit from the left. $\endgroup$
    – mcore
    Commented Jan 12, 2023 at 19:25

Your Answer

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

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