Home > Reverse Engineering > Hyperelliptic curve crypto — Dcoder’s keygenme #2

## Hyperelliptic curve crypto — Dcoder’s keygenme #2

Apparently ordinary elliptic curves in crackmes are getting boring, so Dcoder decided to make things interesting with hyperelliptic curves. Due to intricate nature of HE curves, performing computations on them is more expensive, than for ordinary curves, but on the other hand HE curves provide superior bitstrength security, with regard to size of the base field, they are defined over.

In this blog post, I will try to introduce HE curves, and how to use them in crypto. Using that knowledgle, it will be easy to analyze and break a signature scheme implemented in keygenme #2 by Dcoder. Note that this won’t be a rigorous mathematical dissertation, but a “tutorial” for mathematically inclined programmer :).

# Hyperelliptic curves

The most general definition of an elliptic curve, is

$E = \{(x,y): y^2+a_1xy = a_2x^3+a_3x^2+a_4x+a_5\}$.

$E$ is just a set of points fulfilling an equation that is quadratic in terms of $y$ and cubic in $x$. By introducting a special point $O$ (point at infinity) it’s possible to equip $E$ with “point addition“, turning it into an abelian group.

Hyperelliptic curves are more complicated. HE curve of genus $g$ over a field $K$ is defined as:

$H: y^2+h(x)y = f(x)$

where $f(x),h(x) \in K[x]$, $deg(h) \leq g$, $deg(f) = 2g+1$, and $f$ monic. Elliptic curves are hyperelliptic curves with $g=1$. To define addition on $H$, we need to jump through few mathematical hoops :).

### Zeros and poles

Consider rational functions over algebraically closed field. Let $f(x)=\frac{(x+1)^3}{(x-1)^2}$. It’s easy to see, that $x=-1$ is a zero of $f$. It’s also evident, that $f(1)=\infty$.

If for a given $a$, $r(a)=\pm\infty$, we will say that $r$ has a pole at $a$. When $\lim_{x\to\infty}r(x) = \infty$, we will say that $r$ has a pole at infinity. This is to provide intuition, just remember that pole at infinity == function is not bound at infinity. To be able to compute order of such pole, compute order of pole $x=0$ of $r(\frac{1}{x})$.

$a$ is a zero of order $n$ for $r(x)$, if $n$ is the largest integer, such that $r(x)=(x-a)^{n}s(x)$, where $s(x)$ is a rational function. Order of a pole is similar: $b$ is a pole of order $n$ if $n$ is the largest integer, such that $r(x)=\frac{s(x)}{(x-b)^{n}}$. Notice we are allowed to factor $r(x)$ this way, because we are working over an algebraically closed field, and because of fundamental theorem of algebra.

In our example, $f(x)$ has a zero of order 3 at $x=-1$, a pole of order 2 at $x=1$ and a pole of order 1 at infinity.

Another example. Let $f(x)=(x-1)^5$. $x=1$ is a zero of order 5. We also have a pole at infinity. To compute its order, we need to know the order of $x=0$ of $f(\frac{1}{x})=(\frac{1-x}{x})^5$, so order = 5.

### Divisors

Consider set of rational functions over $K[x,y]$, where HE curve $H$ is defined over $K$. “Over” means our function acts on points of $H$, so for $r(x,y)$, arguments $x$ and $y$ satisfy $y^2+h(x)-f(x)=0$ “for free”.

To keep track of zeros and poles of a function, we can use a divisor. You can think about them as multisets allowing negative number of elements. For example, let $r(x,y)$ have a zero of order 2 at $P_0$, zero of order 1 at $P_1$, pole of order 2 at $P_3$ and pole of order 1 at infinity. Divisor of $r$ is $div(r)=2P_0+1P_1-2P_3-1O$. Note that divisors aren’t supposed to be evaluated (plus and minus signs are not for point addition/subtraction), they are just “lists”, or “multisets” of zeros/poles. You can look at $div(r)$ like it’s a list: $[2P_0, P_1, -2P_3, -1O]$.

More formally, for a nonzero rational function $r$ on $H$, its divisor is given by

$div(r) = \sum_{P\in H}{}ord_P(r)P$

where almost all of $ord_P(r)$ coefficients are zero (there are finitely many nonzero). $ord_P(r)$ is defined as:

•  $n$,  if $P$ is a zero of order $n$,
•  $-n$, if $P$ is a pole of order $n$,
•  0, if $P$ is neither a zero, nor a pole.

$ord_P(r)$ is “order of vanishing of function $r$ at point $P$“. For details see [1] (page 8). You can assume that computing orders works like for ordinary rational functions, so it’s ok to factor nominator / denominator, etc (this isn’t 100% true, but that’s not imporant).

To continue, we need

Theorem 1

Let $r$ be a rational function on $H$, then $\sum_{P\in H}{}ord_P(r)P = 0$.

For proof, see theorem 4.6, page 9 in [1]. This theorem is useful for computing divisors. For $r(x,y)=f/g$, compute zeros of $f$ and $g$ (poles of $r$) and check if their orders (using definition of $ord$ above) sum to 0. If not, add / subtract point at infinity.

We can add / subtract divisors, by adding / subtracting like terms. For example, let $H: y^2 = f(x)$ (over complex numbers), where $deg(f)=3$ (genus 1 curve), $f(x,y)=\frac{y}{x+1}$, $g(x,y)=\frac{x+1}{x+2}$.

To find $div(f)$ we need to know zeros and poles of $f$. Since $deg(f)=3$, there are 3 points on $H$ with $y=0$: $P_1,P_2,P_3$. There are two points with $x=-1$: $Q_1,Q_2$. Points $P_i$ are zeros and $Q_i$ are poles, so $div(f)=P_1+P_2+P_3-Q_1-Q_2-O$ ($-O$ was added to satisfy theorem 1). Similary $div(g)=Q_1+Q_2-R_1-R_2$ ($x(R_1)=x(R_2)=-2$).

Now, $div(f)+div(g)=P_1+P_2+P_3-R_1-R_2-O=div(h)$, where $h(x,y)=\frac{y}{x+2}$. You might notice, that $h=fg$. Indeed, it’s true that:

• $div(fg)=div(f)+div(g)$
• $div(f/g)=div(f)-div(g)$

From the above properties, it follows that set of divisors of rational functions (we will call them principal divisors) $Prin(H)$ form a subgroup of all divisors $Div(H)$. We will denote subgroup of divisors of degree 0 (with sum of coefficients equal to zero) as $Div_0(H)$. Theorem 1 implies that $Prin \subseteq Div_0$.

Here comes the magic part.

We define quotient group $Pic^0(H)$ as:

$Pic^0(H) = Div_0(H) / Prin(H)$

$Pic^0(H)$ is called the degree zero part of the Picard (or divisor class) group of $H$.

For a hyperelliptic curve $H$ of genus $g$, there exists an abelian variety $J(H)$ of dimension $g$ which is isomorphic to $Pic_0(H)$. $J(H)$ is called the Jacobian of $H$.

You can safely disregard the magic part above. The important thing to know is that with HE curves, we perform operations on its Jacobian. $J(H)$ has its own group law, that uses reduced divisors in their Mumford representation.

If you want to just implement HE crypto, you can treat Cantor’s algorithm and Mumford representation as blackboxes given by mathematicians, but I think it’s useful to know how divisors work and what Mumford polynomials represent.

It’s time to analyze our target and show some examples.

### Keygenme

Dcoder implemented polynomial operations on his own, so we are forced to identify them by hand, by looking at the disassembly. This part is easy, so I’ll skip it :).

What’s not easy is identifying the protection scheme, without knowing how HE crypto works. There are many clues that the keygenme implements elliptic curve crypto. For example, here’s a top level view of a part of the verification procedure:

    decode_serial(&part4, &part3, &part2, &part1);
serial_part12 = __PAIR__(part2 << 32 >> 32, part1);
v20 = part3;
f1(&k1_Px, &k1_Py, &f, &h, &Px, &Py, part3 + (part4 << 32));
f1(&k2_Qx, &k2_Qy, &f, &h, &Qx, &Qy, serial_part12);
f2(&k1_Px, &k1_Py, &f, &h, &k1_Px, &k1_Py, &k2_Qx, &k2_Qy);

Looking inside f1, we see:

  do
{
f2(&a3a, &v13, f, h, &a3a, &v13, &a3a, &v13);
if ( k & (1i64 << v7) )
f2(&a3a, &v13, f, h, &a3a, &v13, in_x, in_y);
--v7;
}
while ( v7 >= 0 );

This looks like double and add algorithm for elliptic curves, so our hypothesis is that f1 is point multiplication and f2 point addition. We can verify this by feeding values to these functions and checking their output. For example, computing P+P and 2*P should produce the same result. Quick check shows that’s indeed the case.

With high level functions identified, it’s easy to see that we are dealing with Nyber-Rueppel signature scheme. In order to emit correct signatures, we need to solve an instance of discrete logarithm problem.

Even without knowing that we are dealing with HE curves, we can just rip the code for point addition and use it as a blackbox in Pollard’s kangaroo (lambda) algorithm. Kangaroo attack works in all groups and uses only addition and multiplication in that group. Running time is $O(\sqrt{b-a})$, where $[a,b]$ is the interval containing the discrete log.. Notice that we can’t use Pollard’s rho (which is faster by a constant), because rho requires group’s order as a parameter and we have no means to compute it without knowing what group we are dealing with.

Even with Pollard’s kangaroo, we still need to know how large the order is. If it’s too big, then perhaps we need to be smarter about finding this DLOG. We can obtain a rough estime, by observing what kind of points we are getting out of point addition/multiplication procedures.

Quick inspection in debugger shows, that coordinate $x$ is always a monic polynomial of degree at most 4, and $y$ a polynomial of degree at most 3. Since we are working with polynomials over $F_p$ with $p=8191=2^{13}-1$, there can be at most $2^{13*4}*2=2^{53}$ (we expect our curve to be symmetric, thus the additional 2 factor) such points in our mysterious group :). It’s a lot, but remember that kangaroo attack has a running time of $\sqrt{b-a}$, so in our case $\sqrt{2^{53}}=2^{26.5}$ which is low enough for kangaroo to be practical.

### The curve

Knowing we are dealing with hyperelliptic curve, we can be more specfic about group’s order — we can actually compute it exactly and this will allow us to use Pollard’s rho, instead of kangaroo.

Here are the params, in SAGE format:

x = GF(8191)['x'].gen()
f = 3076 + 1177*x + 6969 * x^2 + 294*x^3 + 6512*x^4 + 7340*x^5 + 5891*x^6 + 3050*x^7 + 0*x^8 + 1*x^9
H = HyperellipticCurve(f)
J = H.jacobian()
X = J(GF(8191))
Px = 1875 + 1721*x + 5809*x^2 + 5647*x^3 + 1*x^4
Py = 6019 + 3070*x + 1666*x^2 + 688*x^3
Qx = 4134 + 2027*x + 4475*x^2 + 4255*x^3 + 1*x^4
Qy = 6525 + 928*x + 1361*x^2 + 6937*x^3
P = X([Px,Py])
Q = X([Qx,Qy])
O = P-P
frob = H.frobenius_polynomial()
order = frob(1)
dlog = 3414275298009790
print order*P == O, dlog*P == Q

Running the above in SAGE will produce True, True on output, which means order of jacobian and the dlog are indeed correct.

The HE we are working on is $H: y^2 + h(x)y = f(x)$, where $h(x)=0$ and $deg(f)=2*4+1$, so genus $g=4$. Since we are working with polynomials over $F_p$, with $p=8191$, jacobian will be defined over $F_{p^4}$.

Order of jacobian is given explicitly by $\chi(1)$, where $\chi$ is its characteristic (Frobenius) polynomial (page 6, [2]).

The exact order is 4518471260972087 (~2^52), which is 2 times smaller than our rough estimate of 2^53, so knowing the exact order decreases the running time of kangaroo by a factor of $\sqrt{2}$.

We can also bound the order using Hasse-Weil theorem. In our case, theorem states that order lies in the interval $[(\sqrt{8191}-1)^8,(\sqrt{8191}+1)^8]$. The upper bound is 1.08 times larger than the exact order, so it’d be a very good estimate.

Kangaroo implemented with FLINT solves the DLP in under an hour, using one 2GHz core. The solution is  3414275298009790.

### Summary

For hyperelliptic curves, group law is defined for their Jacobians. To “add points” use Mumford representation and Cantor’s algorithm. For solving DLP over HE curves, you can use general purpose algorithms like Pollard’s rho/lambda, Pohlig Hellman, or index calculus. Note that curves of high genus are insecure in the sense that index calculus runs in  subexponential time for them (see here for a discussion). For bounding/computing order, use Hasse-Weil theorem, or Frobenius polynomial.

Sources available on github, as usual.

Few serials, to prove correctness :):

pa_kt
38531D6B8FDF2A884166423D58B125B2
-
trololo
C356A2AB43CA6ACCEF72CCEE0C3FD40A
-
crackmes.us
076C49CC3AFF9D25CE8B7CA783B72430

P.S.

Dcoder pointed out I should mention the Riemann-Roch theorem. Thanks to R-R it’s possible to construct the isomorphism between $Pic^0(H)$ and $J(H)$ (it ensures the existence of reduced divisors).

References

[1] Leonard S. Charlap, David P. Robbins, An Elementary Introduction to Elliptic Curves

[2] Pierrick Gaudry, Robert Harley, Counting Points on Hyperelliptic Curves over Finite Fields

Categories: Reverse Engineering
1. 10/08/2013 at 19:15

How did u get so good at this? Great writeup, im into math but I havent yet gotten as far as understanding elliptic curves

• 12/08/2013 at 08:09

Read “Handbook of applied cryptography” 🙂

2. 22/05/2017 at 20:18

F = GF(next_primt(2^80))
x = F[‘x’].gen()
f = x^5 + x^3 + 1
H = HyperellipticCurve(f, 0)
J = H.jacobian()(F)
P = H.lift_x(F(3))
D = J(P) # divisor
===============================================================
To compare time
ECC => %timeit (Integer(randrange(1, 2^160))) * base point
HECC => %timeit (Integer(randrange(1, 2^80))) * divisor`
==============================================================
is this correct?
and if this correct, how ECC time = 13.2 millisecond;
HECC time = 185 millisecond