Distinguishing x25519 public keys from random?

Question

I recently read a piece of protocol that avoided sending ephemeral x25519 keys in the clear as an effort to foil deep-packet inspection.

I understand that x25519 public keys are effectively 255 bits, which must be serialized as 256 bits, leaving one unused bit that libraries typically fix as 0. For the purposes of this question, I'd like to leave this out and focus on the 255 used bits.

Alice generates a random private key K, and 255-bit public key K'. She generates R, a 255-bit random string. She flips a fair coin, and if heads, she sends a message M = K'. Otherwise, she sends M = R.

Eve receives this message and does not know K. She must guess whether M = K'. Can she do this with better than the 50% success rate she'd get by guessing? (In other words, can she distinguish the significant bits of a x25519 public key from random?)

edit: in response to a question, Eve has knowledge of the curve parameters.

Answer 1

A valid point of an elliptic curve in Weierstrass form satisfies the equation $$ y^2 = x^3 + ax + b\,. $$ We can rewrite this as $y = \pm \sqrt{x^3 + ax + b}$, which has either 2 solutions when $x^3 + ax + b$ is a square, 1 solution when $x^3 + ax + b = 0$, or 0 solutions when $x^3 + ax + b$ is not a square.

In X25519, we only see the $x$ coordinate, but we can still make use of the above. The curve equation is $$ y^2 = x^3 + 486662x^2 + x \bmod 2^{255}-19\,, $$ from which we have that given a valid public key $x$, $x^3 + 486662x^2 + x$ must have a square root modulo $2^{255}-19$. On the other hand, a random string will be a square only around $1/2$ of the time. By inspecting $n$ candidate public keys, we can improve our certainty to $1 - 1/2^n$.