Score:1

Invalid point attack yields wrong results for low order points

ma flag

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?

pe flag
I think one missing component of this question is what $x$-only ladder are you using to get those points?
ma flag
Hi Samuel, I'm using the Brier and Joye implementation "Weierstraß Elliptic Curves and Side-Channel Attacks", Fig. 3 with formulas (6) and (7). I've also found in a different paper a multiplicative point X coordinate addition formula, but it yields the exact same results as the additive formula of Brier and Joye. Is there any other algorithm that I shoulds use? And which would be the correct way, usinig the X coordinate of E_t or E_p² as input? I'm just confused as my approach works for all high-order points, it only fails for these very low order points.
pe flag
I cannot verify this right now, but I seem to recall that the Brier-Joye formulas are not exception-free, and with low-order points you are likely to run into one such exception that renders the result incorrect (e.g., dealing with the point at infinity).
ma flag
Dang! Spot on! I did some detailed debugging and what you described is exactly the case. Specifically, there are cases in which intermediate values become the point at infinity and if not handled as a special case, the computation is garbage. Also spot on that this likelihood is increased by low-order points. Thank you so much, you're a legend! All works perfectly now!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.