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
40
41
42
43
44
45
46

from hashlib import sha256
from Crypto.Util.number import bytes_to_long, long_to_bytes
from random import randint
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import json

FLAG = b"FL1TZ{??????????????????????????}"
p = 0xa9fb57dba1eea9bc3e660a909d838d726e3bf623d52620282013481d1f6e5377
a = -3
b = 27
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
j = E.j_invariant()

def gen_random_number():
    while True:
        P = E.random_point()
        if P.order() > j:
            break
    return bytes_to_long(sha256(long_to_bytes(int(P.xy()[0]))).digest()[:8])

def derive_key_iv(secret):
    key = sha256(long_to_bytes(secret)).digest()[:32]
    iv = sha256(key).digest()[:16]
    return key, iv

SK = gen_random_number()
P = SK * G

print(G)
print(P)

key, iv = derive_key_iv(SK)
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(FLAG, 16))

output = {
    "iv": iv.hex(),
    "ct": ct.hex(),
    "Px": hex(int(P.xy()[0])),
    "Gx": hex(int(G.xy()[0])),
}

with open("lights.json", "w") as f:
    json.dump(output, f)

This is the only Elliptic Curves challenge in the ctf. All things considered, I think it was one of the easier ones, which made surprised to see that only 2 teams managed to solve it 😕

Analysis

Functionality

You’re given a lights.sage file that has a custom ECC implementation

• Custom curve parameters (which should make you raise an eyebrow immediately whenever you see it), even though the order $p$ corresonds to the curve $BRAINPOOLp512r1$
• We generate a random secret key using a suspicious method
• We compute the public key $P$ in classic fashion
• We drive the AES key and iv from the secret key using a hash function
• We encrypt the flag with AES using those parameters
• We spit out the ciphertext, iv, and the x coordinated of the publig key and generator

Red Herring

I assume most of the players looked at the ger_random_number() function and lost their mind xd

WHAT IS A j INVARIANT????

What’s so special about a point with an order above it????

The funny thing is, most points on a relatively secure curve have orders below $j$, so picking one above it makes the point not more special than any other random point, which make it no more special than any randomly generated number! (technically, this method does introduce some bias, but it will be irrelevant in this case)

So we could assume that S is nothing but a randomly generated 64 bit integer

Modified Pohlig-Hellman

The classic Pohlig-Hellman algorithm aims to solve ECDLD through divide and conquer war tactics. To put it in perspective, you can’t calculate to discrete log of some point in a group with a large order straight away. But if the order isn’t a prime number, we could theoretically calculate mini DLs over the subgroups with an order equal to the factors of the curve, and then combine our findings using the Chinese remainder theorem.

However, if you try that in this case, you’ll find that some of the factors of the curve’s order are unreasonably large. But here’s the thing…

First let’s do a quick recap of how CRT works:

Given a system of simultaneous congruences for an integer $x$:

Where the moduli $n_1, n_2, \dots, n_k$ are pairwise coprime (i.e., $\gcd(n_i, n_j) = 1$ for $i \neq j$), the Chinese Remainder Theorem states there is a unique solution for $x$ modulo $N = n_1 n_2 \cdots n_k$.

The solution is found by:

where $N = \prod_{i=1}^{k} n_i$, $N_i = N/n_i$, and $y_i$ is the modular multiplicative inverse of $N_i$ modulo $n_i$, such that $N_i y_i \equiv 1 \pmod{n_i}$.

In our case, we’re looking for $S \approx 64$ bits, so all we need is to find $x$ mod some $N \ge 64$ bits.

In short, we only need factors whose product comes out to $64$ bits or above, and we have plenty of them!

Solution

Plan

• Find the order $n$ of the curve
• Find its factors and consider those whose product comes to 64 bits, discard the others.
• Perform Pohlig-Hellman using said factors

Doing that will give us the secret key, the rest is obvious

Note: Since I only gave you the $x$ coordinate of $P$ and $G$, and since elliptic curves are symmetric in proportion to the x-axis, you should consider both $Px$ and $-Px \mod p$, same goes for $G$

Solver

 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

from hashlib import sha256
from Crypto.Util.number import bytes_to_long, long_to_bytes
from random import randint
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import json
p = 0xa9fb57dba1eea9bc3e660a909d838d726e3bf623d52620282013481d1f6e5377
a = -3
b = 27
Fp = GF(p)
E = EllipticCurve(Fp, [a,b])

with open("lights.json", "r") as f:
    data = json.load(f)
iv = bytes.fromhex(data["iv"])
ct = bytes.fromhex(data["ct"])
Px = int(data["Px"], 16)
Gx = int(data["Gx"], 16)

P = -E.lift_x(Fp(Px))
G = E.lift_x(Fp(Gx))

def derive_key_iv(secret):
    key = sha256(long_to_bytes(secret)).digest()[:32]
    iv = sha256(key).digest()[:16]
    return key, iv
n = G.order()
factors = n.factor()
count_factors_needed = 0
new_order = 1
for f, e in factors:
    new_order *= f^e
    count_factors_needed += 1
    if new_order.nbits() >= 64:
        print("Found enough factors! The rest are not needed")
        break
factors = factors[:count_factors_needed]

subsolutions = []
subgroup = []
for f, e in factors:
    quotient_n = (n // f ^ e)
    G0 = quotient_n * G
    P0 = quotient_n * P
    k = P0.log(G0)
    subsolutions.append(k)
    subgroup.append(f ^ e)

found_key = crt(subsolutions, subgroup)
print(G)
print(P)
print(found_key)
assert found_key * G == P
print("success!")

key, iv = derive_key_iv(found_key)
aes = AES.new(key, AES.MODE_CBC, iv)
pt = aes.decrypt(ct)
print("Decrypted flag:", pt)

FL1TZ{n0t_4LL_th4t_Gl1Tt3rs_15_G0LD}