**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)

## 4 comments

## Jiss says:

September 22, 2011 at 03:24 (UTC 3)

Hello ! Really nice solutions.

Here is another hint to find private stuffs without using

sagebut using Pari/GP a french free solution dedicated to mathematics operations :(01:23) gp > p=354990952970600489;

time = 0 ms.

(01:23) gp > ?ellinit

ellinit(x,{flag=0}): x being the vector [a1,a2,a3,a4,a6] defining the curve Y^2 + a1.XY + a3.Y = X^3 + a2.X^2 + a4.X + a6, gives the vector:

[a1,a2,a3,a4,a6,b2,b4,b6,b8,c4,c6,disc,j,e1,e2,e3],w1,w2,eta1,eta2,area]. If the curve is defined over a p-adic field, the last six components are replaced by root,u^2,u,q,w,0. If optional flag is 1, omit them altogether. x can also be a string, in this case the coefficients of the curve with matching name are looked in the elldata database if available.

(01:23) gp > E=ellinit([0,0,0,Mod(9326,p),Mod(1376127157,p)]);

time = 0 ms.

(01:23) gp > A=[Mod(4093588398,p),Mod(494204038,p)];

time = 0 ms.

(01:24) gp > B=[Mod(308275810997226196,p),Mod(36849413680804833,p)];

time = 0 ms.

(01:24) gp > ellisoncurve(E,A)

time = 0 ms.

%14 = 1

(01:24) gp > ellisoncurve(E,B)

time = 0 ms.

%15 = 1

(01:24) gp > ?elllog

elllog(E,P,G,{o}): return the discrete logarithm of the point P of the elliptic curve E in base G. If present, o represents the order of G. If not present,

assume that G generates the curve.

`(01:24) gp > ord=[ellorder(E,A),factor(ellorder(E,A))]`

time = 60 ms.

%16 = [23666063529205592, [2, 3; 11, 1; 23, 1; 149, 1; 78474625067, 1]]

(01:24) gp > elllog(E,B,A,ord)

time = 5,256 ms.

%17 = 5585884147152331

Congratz for your performances !

Jiss

## kyprizel (@kyprizel) says:

September 22, 2011 at 08:42 (UTC 3)

Wow! explicit solution :)

Pari/gp is a backend for Sage’s elliptic curves.

## hellman says:

September 22, 2011 at 11:03 (UTC 3)

Cool, didn’t know! Thx for the information

## hellman says:

November 2, 2011 at 22:00 (UTC 3)

Looks like the 3rd way and the 1st are the same, because sage factorizes order of G, and it’s some kind of Pohlig-Hellman’s algorithm for elliptic curves