Breaking Ed25519 Discrete Logarithm with Degenerate Curve Attack

J Medeiros

1/28/24, 3:05 AM

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:

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

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.

188

1 + 2

elliptic-curves

ed25519

attack

Myria

2/1/24, 1:24 AM

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?

J Medeiros

2/1/24, 4:17 AM

@Myria That is 100% correct. Standard point decompression avoids invalid curve attacks. Although in my case (attack) point decompression was not being used.

Score:4

Crypto

Samuel Neves

1/30/24, 11:33 PM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Breaking Ed25519 Discrete Logarithm with Degenerate Curve Attack

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.