hxpCTF 2020 - Hyper writeup

crypto
,

Server code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#!/usr/bin/env sage
import struct
from random import SystemRandom

p = 10000000000000001119

R.<x> = GF(p)[]; y=x
f = y + prod(map(eval, 'yyyyyyy'))
C = HyperellipticCurve(f, 0)
J = C.jacobian()

class RNG(object):

    def __init__(self):
        self.es = [SystemRandom().randrange(p**3) for _ in range(3)]
        self.Ds = [J(C(x, min(f(x).sqrt(0,1)))) for x in (11,22,33)]
        self.q = []

    def clk(self):
        self.Ds = [e*D for e,D in zip(self.es, self.Ds)]
        return self.Ds

    def __call__(self):
        if not self.q:
            u,v = sum(self.clk())
            rs = [u[i] for i in range(3)] + [v[i] for i in range(3)]
            assert 0 not in rs and 1 not in rs
            self.q = struct.pack('<'+'Q'*len(rs), *rs)
        r, self.q = self.q[0], self.q[1:]
        return r

    def __iter__(self): return self
    def __next__(self): return self()

flag = open('flag.txt').read().strip()
import re; assert re.match(r'hxp\{\w+\}', flag, re.ASCII)

text = f"Hello! The flag is: {flag}"
print(bytes(k^^m for k,m in zip(RNG(), text.encode())).hex())

The server constructs the hyperelliptic curve over , where .

Then it considers three points with coordinates of , and constructs the divisors corresponding to them on the Jacobian of (i.e. ).

There are three random values , which we want to recover, that are used as multipliers during one round of the PRNG.

In particular, the PRNG works in the following way: in the -th round it computes the divisor ; then it computes the Mumford representation of , and outputs the coefficients of those polynomials encoded as bytes.

Reconstruct the divisor

The first challenge, hyper, only asks us to recover by knowing : we have the first 24 bytes of both output and input, so we can recover the first 24 bytes of the PRNG, that are exactly the coefficients of .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p = 10000000000000001119

K = GF(p)
R.<x> = K[]; y=x
f = y + prod(map(eval, 'yyyyyyy'))
C = HyperellipticCurve(f, 0)
J = C.jacobian()

def get_u_from_out(output, known_input):
    res = []
    for i in range(24):
        res.append(output[i]^^known_input[i])
    res = bytes(res)
    u0, u1, u2 = struct.unpack("<QQQ", res)
    u = x^3+x^2*u2+x*u1+u0
    return u

To obtain , we look up the definition of Mumford representation, for example on “Handbook of Elliptic and Hyperelliptic Curves”.
Every divisor has a unique representation as , where and the following properties hold:

  • is monic

The last condition tells us that if is a root of in some extension of , then , so that .

Since we know , we can compute its roots , and for each choice of signs we get a system of equations , which can be solved via Lagrange interpolation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from itertools import product

def get_v_from_u(u):
    Kbar = GF(p^6)
    Rbar.<t> = Kbar["t"]
    u2 = u.change_ring(Rbar)
    roots = [x[0] for x in u2.roots()]
    ys = []
    for root in roots:
        ys.append(f(root).sqrt(0,1))
    res = []
    for perm in product(range(2), repeat=3):
        poly = Rbar.lagrange_polynomial([(roots[i], ys[i][perm[i]]) for i in range(3)])
        if poly[0] in K:
            res.append(R(poly))
    return res

def try_decode(output, u, v):
    rs = [u[0], u[1], u[2], v[0], v[1], v[2]]
    otp = struct.pack("<QQQQQQ", *rs)
    plain = []
    for i in range(len(output)):
        plain.append(output[i]^^otp[i])
    return bytes(plain)


output = bytes.fromhex("a0955c882185b50a69d9d19a24778519d6da23894e667d7130b495b645caac72163d242923caa00af845f25890")
known_input = b"Hello! The flag is: hxp{"
u = get_u_from_out(output, known_input)
vs = get_v_from_u(u)
for v in vs:
    print(try_decode(output,u,v))

Running this we get two valid s, but only one which decodes to the correct flag:

1
2
b'Hello! The flag is: hxp{:\x82\x88\x15\xd7\xa0b.\xf6\xc6H\x14\x88Gg\x01S\xcb\xc4\x0c\x87'
b'Hello! The flag is: hxp{ez_P4rT_i5_ez__tL0Cm}'

Get the next block

In the hyperhyper challenge, we can reconstruct as above the divisor ; but now we want to know the divisor , and the strategy is finding each individual .

1
2
3
4
5
6
7
8
9
output2 = bytes.fromhex("fca3dd468e9f6f0e5e70046af7a6e4355fd8b15f8523980933dd9d1385884929fd0a67517c30fa7af82c07c45769d5216dd5721898f1c219c4753021b7f1bc6db2ee5c450a9efa4da6c40df913fb113bcd5193ba3135351e55db3ba23c")
known_input = b"Hello! The flag is: hxp{"
u = get_u_from_out(output2, known_input)
vs = get_v_from_u(u)
for v in vs:
    print(try_decode(output2, u, v))

v = vs[0]
Q = J(u,v)

The first things to notice is that ; this is not a completely random try, because for elliptic curves over the multiplication by can signal some special behaviour of the curve:

  • if , then we probably are dealing with an anomalous curve
  • if , then we probably are on a supersingular curve

This means that we are dealing with the supersingular analogous of hyperelliptic curves, so that we probably can apply the MOV attack on supersingular curves by extending the base field to and taking Weil pairings.

In particular, if is the Jacobian over , and is a random point, then we can compute Weil pairings with and find an equation in of the kind

Moreover, if we take the discrete logarithms , since has order , we get the equation .

This is where I stopped during the CTF, since I had no idea how to compute the different and I was running out of time. Then, after the CTF, I got the hint that the group is a product of many copies of , and that are not in the same cyclic subgroup of order , so using different random s should generate independent equations modulo !

I then tried this approach using MAGMA (since Sage refused to compute Weil pairings on hyperelliptic curves), and was able to generate three independent equations!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
p:=10000000000000001119;
K:=GF(p);
R<x>:=PolynomialRing(K);
f:=x^7+x;
C:=HyperellipticCurve(f);
J:=Jacobian(C);
P0:=Points(C,11)[2];
P1:=Points(C,22)[1];
P2:=Points(C,33)[2];
inf:=PointsAtInfinity(C)[1];
D0:=J![P0,inf];
D1:=J![P1,inf];
D2:=J![P2,inf];

u:=x^3 + 8279968990525893430*x^2 + 1550302165483132214*x + 6507629860866868916;
v:=8477847110799285964*x^2 + 1343483448898642569*x + 1883833843420163421;
Q:=J![u,v];
print Q;

Jext:=BaseExtend(J,2);
Qe:=Jext!Q;
D0e:=Jext!D0;
D1e:=Jext!D1;
D2e:=Jext!D2;
for i:=1 to 3 do
        R:=Random(Jext);
        gen:=WeilPairing(Qe, R, p+1);
        a0:=WeilPairing(D0e, R, p+1);
        a1:=WeilPairing(D1e, R, p+1);
        a2:=WeilPairing(D2e, R, p+1);
        l0:=Log(gen, a0);
        l1:=Log(gen, a1);
        l2:=Log(gen, a2);
        print l0, l1, l2;
end for;

Having the three triples I got back to Sage, solved the linear system and decoded the flag:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
M=IntegerModRing(p+1)
A=Matrix(M,[[8456637504717104773, 644133729621365327, 7060694052512827322],[4881556192156233109, 7367516523653099255, 6746795449489230423], [24069496990635245, 2569299995974183471, 5990686822681667460]])
b=vector(M,[1,1,1])
ee=A.solve_right(b)
e0, e1, e2 = ZZ(ee[0]), ZZ(ee[1]), ZZ(ee[2])

D0, D1, D2 = [J(C(x, min(f(x).sqrt(0,1)))) for x in (11,22,33)]
assert e0*D0+e1*D1+e2*D2 == Q
otp1 = struct.pack("<QQQQQQ", *[u[0],u[1],u[2],v[0],v[1],v[2]])

uu, vv = e0^2*D0+e1^2*D1+e2^2*D2
otp2 = struct.pack("<QQQQQQ", *[uu[0],uu[1],uu[2],vv[0],vv[1],vv[2]])
otp = otp1+otp2
flag = ""
for i in range(len(output2)):
    flag += chr(otp[i]^^output2[i])
print(flag)

This returns Hello! The flag is: hxp{n0w_c0m3th_th3_h4rD_P4rT__TsMXaeGJsTkdokHKhIjZDtAkc1NuiLP2__gOod_j0b}, which should be the flag.