4
$\begingroup$

Following this question ed25519 attacks and also this paper on degenerate curve attacks https://eprint.iacr.org/2015/1233.pdf, I tried to implement my own attack: Given a point (0, y) and a scalar (k), the computed point should be (0, y^k).

This attack worked successfully with affline points (X:Y), with point addition formulas such as:

enter image description here

Although, when implementing the same attack with extended coordinates using this point addition formula, it seems to fail.

image 1

Y will always revert to 1 or some big number. (I have kept y = Y/Z in mind).

Here is the code I used to implement the attack:

using H4x2_TinySDK.Ed25519;
using System.Numerics;

var p = new Point(BigInteger.Parse("0"), BigInteger.Parse("2"));
var q = new Point(BigInteger.Parse("0"), BigInteger.Parse("3"));

var t = p + q;

var qy = t.GetY(); // Expecting 6 <- (2*3). Actual result is 57896044618658097711785492504343953926634992332820282019728792003956564819947

The paper linked above states

An obvious but important observation is that, while we have described our attack in affine coordinates, it also works in the (likely) case when the device performs its computation in projective coordinates, using the projective versions of the same group operations. It is straightforward to check, for example, that (0 : Y1 : 1) + (0 : Y2 : 1) = (0 : Y1Y2 : 1)

Although this doesn't seem to be the case.

It would be great if someone could show an example of how to implement the degenerate curve attack with extended coordinates, or provide some insight into what I might be doing wrong.

The following code is what is being used to do ed25519 point addition (full code @ https://github.com/tide-foundation/Tide-h4x2-2/blob/main/H4x2-TinySDK/H4x2-TinySDK/Ed25519/Point.cs):

public static Point operator +(in Point point1, in Point point2)
        {
            // TODO: check to see if point is on curve and on the prime order subgroup
            // Algorithm taken from https://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html.

            BigInteger A = Mod((point1.Y - point1.X) * (point2.Y + point2.X));
            BigInteger B = Mod((point1.Y + point1.X) * (point2.Y - point2.X));
            BigInteger F = Mod(B - A);
            if (F.Equals(BigInteger.Zero)) return Double(point1);
            BigInteger C = Mod(point1.Z * Curve.Two * point2.T);
            BigInteger D = Mod(point1.T * Curve.Two * point2.Z);
            BigInteger E = D + C;
            BigInteger G = B + A;
            BigInteger H = D - C;
            BigInteger X3 = Mod(E * F);
            BigInteger Y3 = Mod(G * H);
            BigInteger T3 = Mod(E * H);
            BigInteger Z3 = Mod(F * G);
            return new Point(X3, Y3, Z3, T3);
        }

EDIT We have found that the paper states the attack works against projective coordinates, while we're using extended coordinates. I don't see how this should affect my results as x = X / Z and y = Y /Z for both types of coordinates.

$\endgroup$
2
  • $\begingroup$ I'm curious how an invalid curve attack would work on Ed25519 at all, when the process of decoding a signature involves using the curve equation to determine $x$ given $y$. An implementation would have to fail to validate that a square root actually exists, I guess? Also, I thought that Ed25519's design choices mean that if you did try to use a $y$ for which no valid $x$ exists, it'd be on a "twist" of the curve whose order is very large like the real curve, negating this attack? $\endgroup$
    – Myria
    Commented Feb 1, 2023 at 1:24
  • 1
    $\begingroup$ @Myria That is 100% correct. Standard point decompression avoids invalid curve attacks. Although in my case (attack) point decompression was not being used. $\endgroup$
    – J Medeiros
    Commented Feb 1, 2023 at 4:17

1 Answer 1

5
$\begingroup$

The formula you mention corresponds to the incomplete affine addition formula (3) (specialized to $a = -1$) from Section 2 of Twisted Edwards Curves Revisited: $$ \left(x_3, y_3\right) = \left(\frac{x_1y_1 + x_2y_2}{y_1y_2 - x_1x_2}, \frac{x_1y_1 - x_2y_2}{x_1y_2 - y_1x_2}\right)\,. $$ Upon cursory observation, the same trick used for the complete Edwards addition formulas does not work here, since we're hitting an exceptional case—if both $x_1 = x_2 = 0$, we end up with $0$ and a division by $0$.

However, these alternative formulas are independent from the $d$ parameter of the (twisted) Edwards curve $ax^2 + y^2 = 1 + dx^2y^2$. This case is mentioned in Section 3.2 of the degenerate curve attack paper. That means that you can find an Edwards curve with differing $d$ and smooth order—whose discrete logarithm can be easily computed with Pohlig-Hellman—and apply the more classic invalid curve attack that also applies to Weierstrass curves. One such curve is for example $-x^2+y^2=1+1672x^2y^2$ over the same field as Curve25519, which has order $$ 2^2\cdot 3\cdot 5^4\cdot 427597\cdot 16552651\cdot 22289317\cdot 4822727227\cdot 112768713691\cdot 3876129039441419\cdot 23211815501884937\,, $$ and given its largest factor is of size $\approx 2^{54}$ it can be broken in $\approx 2^{27}$ operations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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