2
$\begingroup$

I'm replicating an invalid point attack on ECC using Short Weierstrass curves. For this I have written a "dumb" implementation that does not validate points are on the curve before going into the scalar multiplication. For the outline of the attack, I'm heavily borrowing from Samuel Neves' excellent descrption which he gave here: Understanding Twist Security with respect to short Weierstrass curves

I can replicate this without any issue when $d = -1$ is a quadratic non-residue in $\mathbb{F}_p$, then everything works out-of-the-box. However, when $p$ is so that $-1$ is a quadratic residue and therefore I need to choose a different value for $d$, everything falls apart.

For simplicity, in the first run I am not using curves in $\mathbb{F}_{p^2}$ because for small $p$ exhaustive enumeration to find low-order points is not an issue.

As an example, say my curve is defined over $\mathbb{F}_{101}$; here, $-1$ is a quadratic residue mod $p$, since $10 \cdot 10 = -1 \mod 101$. My curve is given by

$E: y^2 = x^3 + 13x + 29$

And with $d = 2$, a quadratic non-residue mod 101,

$E^d: y^2 = x^3 + 52x + 30$

The order of $E^d$ is $111 = 3 \cdot 37$. I have chosen two points on $E^d$ which have orders 3 and 37, respectively:

$P_1 = (28, 62)$

$P_2 = (8, 7)$

When I run these values through my scalar multiplication without point validation (for private key $d = 58$, I get the following output:

$S_1 = (94, 53)$

$S_2 = (32, 14)$

Neither $S_1$ nor $S_2$ is a point on the quadratic twist $E^d$. I can lift either X coordinate in $E^d$, but then the orders of the points are wrong.

Here's my example code:

Fp = GF(101)
D = Fp(2)
    
print(D, "is square?", D.is_square())
(a, b) = (13, 29)

E = EllipticCurve(Fp, [a, b])
Et = EllipticCurve(Fp, [ a*D^2, b*D^3 ])

print("Et.order()", factor(Et.order()))

attack_points = [
    Et(28, 62),
    Et(8, 7),
]
print(E)
print(Et)
for P in attack_points:
    print(P, P.order())

# private key d = 58
mul_results = [ 
    Et(94, 53), 
    Et(32, 14), 
]
#print(Et.lift_x(94).order())
#print(Et.lift_x(32).order())

Which outputs:

2 is square? False
Et.order() 3 * 37
Elliptic Curve defined by y^2 = x^3 + 13*x + 29 over Finite Field of size 101
Elliptic Curve defined by y^2 = x^3 + 52*x + 30 over Finite Field of size 101
(28 : 62 : 1) 3
(8 : 7 : 1) 37
TypeError: Coordinates [94, 53, 1] do not define a point on Elliptic Curve defined by y^2 = x^3 + 52*x + 30 over Finite Field of size 101

How can I perform this attack for a quadratic twist where $d \neq -1$?

$\endgroup$
9
  • $\begingroup$ It might not be your problem. The original code is also not working on SageMath anymore. High probably there is a change in the library that prevents such calculations... $\endgroup$
    – kelalaka
    Mar 17 at 21:19
  • $\begingroup$ I don't have enough reputation to comment in the other post, but the solution by Neves works, just not out of the box: The print statements need parenthesis and the .lift_x(randint(...)) calls needs to be replaced by .lift_x(K(randint(...))), then everything works like a charm. I could reproduce it perfectly with d = -1, but as I wrote -1 is a quadratic residue in some fields (like GF(101), as shown here). $\endgroup$ Mar 17 at 22:42
  • $\begingroup$ I've modified the answer, could you also check that? $\endgroup$
    – kelalaka
    Mar 17 at 22:54
  • $\begingroup$ Thanks, the code over there works now, but still doesn't address my question (i.e., it explicitly uses d = -1) -- any idea how to get it running with a different d? $\endgroup$ Mar 18 at 6:20
  • $\begingroup$ Yes, I know. Algebraic geometry ( elliptic curves are part of it ) should be done on the algebraic closure. Samuel Neves's answer, as you can see, works on the closure, you are not. $\endgroup$
    – kelalaka
    Mar 18 at 9:25

1 Answer 1

0
$\begingroup$

This is not a problem of d being a QNR that is not -1.

Instead, it is a problem of small moduli. I can demonstrate this reliably using a modified script of Samuel Neves: Invalid point attack yields wrong results for low order points

This does not answer at all why it does not work, but at least this demonstrates that $d \neq -1$ is not the root cause of my issue.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.