23
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ You can use the elligator2 encoding to avoid this $\endgroup$ Aug 27, 2018 at 19:33

1 Answer 1

23
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ The projection onto the prime order subgroup should give another 3 bits per attempt, if the standard implementation of curve25519 is used. $\endgroup$ Aug 27, 2018 at 19:35
  • $\begingroup$ For details, see "Elligator: Elliptic-curve points indistinguishable from uniform random strings" by DJB et al elligator.cr.yp.to/elligator-20130828.pdf $\endgroup$ Aug 19, 2022 at 7:46

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.