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_*$.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Note that I don't see how this question is distinct from the last link. $\endgroup$
    – kelalaka
    Jan 12 at 19:47
  • $\begingroup$ +1 agree it is either , very identical, or a small change, - @BenZ how is the question distinct ? $\endgroup$
    – William Martens
    Jan 12 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$
    – Ben Zelnick
    Jan 13 at 2:40
  • 1
    $\begingroup$ @BenZ. Ohh okay, put that in the question :) so we know exactly that what it means $\endgroup$
    – William Martens
    Jan 13 at 10:55
  • 1
    $\begingroup$ Done—thank you for the feedback! $\endgroup$
    – Ben Zelnick
    Jan 14 at 17:32

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
-1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ What about the lower bits? $\endgroup$
    – kelalaka
    Jan 12 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 ♦
    Jan 12 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
    Jan 12 at 19:25

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.