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.
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
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