hack.lu CTF 2011 Wipe out the Klingons (400)

Category: crypto

We already made it. The evil Klingons agression is nearly fended. But their final mothership is well protected and even sacrifing a huge number of battleships caused only minor damage. Spies told us an unclear message caused most technical operators and the commander to leave the ship. Unfortunately we are unable to locate them. We need your help to decrypt the secret message in order to blow these little bastards up. Due to our attacks their RNG got damaged. Our mole reported us they use a manually chosen seed increased by one every time as a workaround.

nc ctf.hack.lu 2006
client.py
cryptor.py
ecc.py
capture.pcap

Summary: Elliptic curve Diffie-Hellman, several bugs in realization. 3 ways of solving

This task used Diffie-Hellman scheme too, but adapted for Elliptic Curves: ECDH. We have a client source and a dump of a session of client with a server.

The algorigthm for client is:

• connect to server and get curve parameters a, b, p (which are used in equation y^2 = x^3 + a*x + b (mod p))
• get generator (base point) G
• accept generator or reject it and suggest another one
• generate secret key a as random integer
• send to server aG (which stands for G+G+…+G)
• receive from server dG (d is server’s secret)
• calculate skey = a✕(dG) = daG – shared key
• use skey for encryption

Here, the shared key was used in a right way (it seeded the byte stream based on consequent md5). So, we need another tactics to solve the task.

Let’s look at the session: (follow stream in wireshark):

During the ctf, a solution was not obvious, but after a post-ctf discussion we found that there are 3 ways of solving it.

1. Discrete logarithm

You can notice that p here isn’t very big: 354990952970600489 ~ 59 bits. There are rather effective discrete logarithming algorithms. You can accept a challenge and try to implement it by yourself, but it’s easier and faster to use ready ones. sage is a really awesome tool for that:

Notice: sage package is ~400 mb and is compiling very long; but it’s worth it!

sage: p = 354990952970600489
sage: E = EllipticCurve(GF(p),[9326,1376127157])
sage: g = E(4093588398,494204038)
sage: v1 = E(308275810997226196, 36849413680804833)
sage: g.discrete_log(v1)
5585884147152331
sage: v2 = E(1853983502158609, 211178087614695596)
sage: g.discrete_log(v2)                         
20402189795777059

~30 seconds for the win! Check that both shared keys are the same:

sage: 20402189795777059 * v1
(175525038661221984 : 73511438028432478 : 1)
sage: 5585884147152331 * v2
(175525038661221984 : 73511438028432478 : 1)

Now we can easily decrypt messages, using cryptor from cryptor.py.

2. Generator suggestion

This way uses a server’s option to suggest user’s generator (base point) and a fact that server’s secret key d is incremented each new session (it can be understood from the task text). Indeed, if we suggest a server client’s public point aG, it will return (d + sess)✕aG =daG + sess✕aG. Then we can calculate shared secret daG of the captured session: we know aG and sess number is shown after connect to the server:

while True:
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) 
    s.connect(("ctf.hack.lu", 2006))

    readline(s)
    a, b, p = readcurve(s)
    prim_x, prim_y = readpoint(s)

    if a == 9326:  # our curve
        break

d = 1  # doesn't matter much

sendline(s, "n")
readline(s)
readline(s)

# client's point aG suggest as generator
Gx, Gy = 1853983502158609, 211178087614695596
sendpoint(s, Gx, Gy)

# usual session
client_x, client_y = ecc.pointMultiplication(Gx, Gy, d, a, p)
sendpoint(s, client_x, client_y)
server_x, server_y = readpoint(s)
priv_x, priv_y = ecc.pointMultiplication(server_x, server_y, d, a, p)

c = cryptor.cryptor(priv_x, priv_y, "client")

# get sess number
m = readline(s)
m = c.decrypt(m)
m = m[m.find("the ")+4:m.find(".")]
sess = int(m) - 2

# calculate sess*aG
sess_aGx, sess_aGy = ecc.pointMultiplication(Gx, Gy, sess, a, p)
# calculate daG = (d+sess)*aG - sess*aG
daGx, daGy = ecc.pointAddition(sess_aGx, -sess_aGy, server_x, server_y, a, p)

print daGx, daGy

Output:

175525038661221984 73511438028432478

3. Weak curves – factorizing the order

This way was suggested by the author of this awesome task.

The server chooses randomly one curve from 5 at connection. Some of them are weak – they have complex (not prime) order. So, we can make discrete_log by each factor of the order, and then rebuild full value with Chinese Remainder Theoreme. I won’t write python code for solving the task, just emulate the situation in sage (which is much more clear for understanding).

First, let’s find weak curves:

sage: curves = [
....: [[23749, 409741011, 426546346592070269], [729,28539]],
....: [[9326, 1376127157, 354990952970600489], [4093588398, 494204038]], 
....: [[30800, 1187016249, 546422503250358263], [1146878855, 243009781]], 
....: [[16057, 421810025, 322083043555692967], [2478569373, 360426459]], 
....: [[32593, 1864507527, 560147175803221327], [2309607047, 53492280]]
....:          ]
sage: for curve in curves:
....:     ((a, b, c), (gx, gy)) = curve
....:     E = EllipticCurve(GF(c), [a, b])
....:     ord = order(E)
....:     if is_prime(ord):
....:         continue
....:     print E, ord, factor(ord)
....:     

Elliptic Curve defined by y^2 = x^3 + 9326*x + 1376127157 over
Finite Field of size 354990952970600489
354990952938083880 2^3 * 3 * 5 * 11 * 23 * 149 * 78474625067

Elliptic Curve defined by y^2 = x^3 + 30800*x + 1187016249 over
Finite Field of size 546422503250358263
546422502625387317 3^2 * 43 * 31667 * 44587250173

Elliptic Curve defined by y^2 = x^3 + 32593*x + 1864507527 over
Finite Field of size 560147175803221327
560147174389219943 417828469 * 1340615147

Three from five, hmmm! Let’s take the last one, because it has only 2 factors. Notice: we can also take the first curve and use (2^3 * 11 * 23 * 149) as a single number and the algorithm won’t change.

sage: E
Elliptic Curve defined by y^2 = x^3 + 32593*x + 1864507527 over
Finite Field of size 560147175803221327
sage: G
(2309607047 : 53492280 : 1)
sage: factor(order(G))
417828469 * 1340615147

# we send this as alternative generators (two times)
sage: G1 = 417828469 * G
sage: G2 = 1340615147 * G   

# now server generates random key (we don't know it)
# and prints server's public points
sage: d = randint(2, order(G))
sage: p1 = d*G1
sage: p2 = (d+5)*G2  # let's say sess increased with 5

# now we subtract session difference (we know it)
sage: p2 -= 5*G2

# look at orders of points - it's double smaller than original
# so discrete_log is fast enough
sage: order(G1)
1340615147
sage: order(G2)
417828469

# do discrete_log
sage: G1.discrete_log(p1)
1158875530
sage: G2.discrete_log(p2)
176353534

# rebuild secret key with Chinese Remaider Theoreme
sage: crt([176353534, 1158875530], [417828469, 1340615147])
246363027508311051

# check with the secret :)
sage: d
246363027508311051

PS: if you want to try it yourself, here’s a source of the server script (thx to kyprizel)