I've recently tried to replicate the results of the question Ruggero asked and which Samuel Neves answered here: Understanding Twist Security with respect to short Weierstrass curves
In my attempt to replicate this, I found that the attack does not work for some points. Initially my assumption was that this was because the twist factor $d$ in my case was not $-1 \mod p$. Hence, I asked this question: Invalid point attack on quadratic twist of Elliptic Curve when -1 is a quadratic residue. However, as I've explored further it became clear to me that this is not the reason the attack does not work. Instead, with the very code of the original answer I can also reliably demonstrate that a real implementation of an X-only ladder works for points of order 100+, but does not (reliably) work for points of lower order.
I've modified Samuel's script here to deterministically show this behavior for a point of order 7:
# 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 = 123456789123456789123456789
P = E([0, 26743016104147931148362869907315104519])
Q = s * P
P_ = E2.lift_x(K(163965092228135290549051973720749297665))
fact = 7
P_ *= Et.order() // fact
print(P_)
Q_ = s * P_ # query -- pretend this is done with an x-only ladder
# solve the log directly on E2
x1 = P_[0]
print("x1_p2", x1)
x2 = Q_[0]
s_ = E2.lift_x(x1).discrete_log(E2.lift_x(x2))
# map to Et (optional) and solve
x1 = d * P_[0]
print("x1_t", x1)
x2 = d * Q_[0]
s__ = Et.lift_x(x1).discrete_log(Et.lift_x(x2))
for result in [ 153050600407045353908344231774077597412, 109343643823296263382915152331234715795 ]:
for x in [ K(result), K(result) * d ]:
for c in [ Et, E2 ] :
try:
P = c.lift_x(x)
except ValueError as e:
print(e)
continue
print(P, P.order())
print (s % fact)
print (s_, -s_ % fact) # either one or the other
print (s__, -s__ % fact) # either one or the other
The values 15305... and 1093... are those that an X-only ladder implementation gives when given the coordinates x1_p1 or x1_t.
Note that this code and my X-only ladder implementation works perfectly for all points with order 73 or above. It just does not work for orders 3 or 7. Here is the output of the script:
170141183460469231713519983870624230867
3 * 7^2 * 73 * 207464639 * 4221589732069 * 18102941371909
3 * 7^2 * 73 * 207464639 * 4221589732069 * 18102941371909 * 170141183460469231713519983870624230867
(31638283026303721859929793126783073834 : 8180858091114185696092778095200036260*z + 4090429045557092848046389047600018130 : 1)
x1_p2 31638283026303721859929793126783073834
x1_t 138502900434165509871757510589101031893
No point with x-coordinate 153050600407045353908344231774077597412 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(153050600407045353908344231774077597412 : 120638375417041763806996747829917991029*z + 145389779438755497769342025772901048378 : 1) 56713727820156410583284874520381326863
(17090583053423877823343071941806508315 : 41244633631159509998704366741778119200 : 1) 56713727820156410583284874520381326863
(17090583053423877823343071941806508315 : 28961826547573943769330362324255518848 : 1) 170141183460469231713519983870624230867
No point with x-coordinate 109343643823296263382915152331234715795 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(109343643823296263382915152331234715795 : 127120934962706688155967022405858199927 : 1) 170141183460469231713519983870624230867
No point with x-coordinate 60797539637172968348772151384649389932 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(60797539637172968348772151384649389932 : 17145369941110587676988010143957064222 : 1) 170141183460469231713519983870624230867
1
1 6
1 6
Why does this attack work in theory (as the multiplication Q_ = s * P_ simulates) but works in practice only for reasonably high order points?
