Understanding Twist Security with respect to short Weierstrass curves

Question

I'm trying to understand the "Invalid-curve attacks against ladders" section of SafeCurves Twist Security page and I have difficulties to apply it to short Weierstrass curves.

That section claims that in order to thwart invalid curve attacks an efficient technique is to use a single coordinate ladder to compute the scalar multiplication. Then the section goes on in describing twists and explicitly refers to Montgomery Curves, particularly when it says "The Montgomery ladder formulas for $By^2=x^3+Ax^2+x$ also compute scalar multiplication for the twisted curve $(B/u)y^2=x^3+Ax^2+x$".

Now, I understand this is a problem because during an ECDH, implemented with a single coordinate ladder on a Montgomery curve, I can provide a public key on the curve's twist and, if the twist's order is "weak", gain information on the other peer's private key.

But, does this apply to short Weierstrass curves ? If so, how ?

It is my understanding that a nontrivial quadratic twists on a Weierstrass curve has the form $y^2=x^3+c^2ax +c^3b$ where $c$ is a non-square in $F_p$. So the twist modifies both $a$ and $b$ parameter of the curves. For the attack to work I would assume that it is required to have a scalar multiplication ladder that works on both curves (normal and twisted). Is this assumption correct ?

Does such a ladder exists for short Weierstrass curves ?

As far as I know all $x$-coordinate only ladders for short Weierstrass make use of $a$ and $b$ in the computation, such as the one of Brier and Joye. How could this work on the twist which as different values for $a$ and $b$ ?

I'm asking this question because if such an algorithm doesn't exist, then I don't see how to apply the measure of twist security to short Weierstrass curves such as NIST P-224 and brainpoolP256t1 as djb did on that page.

Answer 1

The twist attack is best explained in Fouque et al's paper.

While the (quadratic) twist of the curve $E : y^2 = x^3 + ax + b \in \mathbb{F}_p$ is indeed of the form $E^t : y^2 = x^3 + d^2ax + d^3b \in \mathbb{F}_{p}$ for nonsquare $d$, you can also think of the twist as the set of points $(x, y)$ in $E^2 : y^2 = x^3 + ax + b \in \mathbb{F}_{p^2}$ where $x$ is exclusively in $\mathbb{F}_p$ but $y$ is either $0$ or only defined in $\mathbb{F}_{p^2}$ (plus the point at infinity, obviously). You can map such points from $E^2$ to $E^t$ as $(dx, d^{3/2}y)$. But you don't have to—you can simply solve the logarithm directly in $E^2$.

Here's a Sage example that demonstrates a twist attack on a Weierstrass curve over the integers modulo $2^{127}-1$:

# Setup fields
p  = 2^127-1
d  = -1 # non square in the field
K  = GF(p)
K2.<z> = GF(p^2)

# this curve has prime order, but a 2^44-smooth twist
a  = -3
b  = 2045
E  = EllipticCurve(K, [a, b])
Et = EllipticCurve(K, [d^2*a, d^3*b])
E2 = EllipticCurve(K2, [a, b])

# precompute orders
print (E.order().factor());
print (Et.order().factor());
print (E2.order().factor());

# generate a discrete logarithm to solve
s  = randint(0, E.order())
P  = E([0, 26743016104147931148362869907315104519])
Q  = s * P

# query target with an invalid point
# of order 207464639
P_ = E2.lift_x(K(randint(0, p)))
while P_.order() != Et.order():
  P_ = E2.lift_x(K(randint(0, p)))

P_ *= Et.order() // 207464639

Q_ = s * P_ # query -- pretend this is done with an x-only ladder

# solve the log directly on E2
x1 = P_[0]
x2 = Q_[0]
s_ = E2.lift_x(x1).discrete_log(E2.lift_x(x2))

# map to Et (optional) and solve
x1  = d * P_[0]
x2  = d * Q_[0]
s__ = Et.lift_x(x1).discrete_log(Et.lift_x(x2))

print (s % 207464639)
print (s_, -s_ % 207464639) # either one or the other
print (s__, -s__ % 207464639) # either one or the other

So you can see that there is no manipulation of the $a$ and $b$ parameters of the curve: the only thing required in a twist attack is to send an $x$-coordinate for which $x^3 + ax + b$ is not a square in $\mathbb{F}_p$. Note that since both $x$, $a$, and $b$ are well-defined in $\mathbb{F}_p$, an $x$-only ladder for $E$ will also work for points of the twist defined in $E^2$. Perhaps an easier way to understand why it works is to rewrite $y^2 = x^3 + d^2x + d^3b$ as $dy^2 = x^3 + ax + b$.