8
$\begingroup$

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.

$\endgroup$

1 Answer 1

8
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you! Also the sage code made it pretty clear. I didn't think about twist in Fp^2. I've tested with P-224 and I was able to find a point on twist Et, map it on E2, get the result of kP in E2, map it to Et and find the discrete log on Et. I wasn't able to work directly on E2, probably due to complexity for sage to get its cardinality, I don't know and honestly don't care since I can work in Et. Thanks again. $\endgroup$
    – Ruggero
    Oct 30, 2014 at 10:47
  • $\begingroup$ I've modified the source to work with new SageMath print as now it uses Python3 and randint(0, p) turned into K(randint(0, p)) to work. Please check. $\endgroup$
    – kelalaka
    Mar 17, 2022 at 22:53

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.