Challenge: Easy DSA · CTF: GPN CTF 2026 · Category: Crypto · Difficulty: Easy

Summary

A P-521 ECDSA signing oracle derives its per-signature nonce k deterministically from uuid3(namespace, message), which is MD5-based. Two messages with an MD5 collision yield the same nonce, leaking the private key via classic ECDSA nonce reuse — then we forge a signature for a fresh recipe to claim the flag.

Solution

Step 1: Spot the deterministic, MD5-derived nonce

The nonce comes from secure_random, which mixes a constant key_id with msg_id = uuid3(secure_namespace, message).bytes:

1
2
3

key_id = uuid3(secure_namespace, sk.export_key(...)).bytes   # constant per session
msg_id = uuid3(secure_namespace, message).bytes              # depends only on message
k = int.from_bytes(sha256(key_id || msg_id).digest()) % (n-1) + 1

uuid3(ns, name) is literally md5(ns.bytes + name) with 6 version/variant bits overwritten. So any MD5 collision on kitchenexplosion || message produces the same msg_id, hence the same k. The hash truncation (z = e & ~(1 << n.bit_length())) is a no-op here because SHA-256 is only 256 bits while n is 521 bits, so z = e = sha256(message).

With two signatures sharing k (so the same r) but different z:

1
2

k = (z1 - z2) / (s1 - s2) mod n
d = (s1*k - z1) / r mod n

Step 2: Generate the collision, recover d, forge a fresh signature

fastcoll (Marc Stevens) produces an identical-prefix MD5 collision against the 16-byte namespace kitchenexplosion. The two colliding files share their MD5 (so identical uuid3) but differ in SHA-256 (so different z).

1
2
3
4
5
6
7
8
9

# Build fastcoll once
sudo apt-get install -y libboost-all-dev
git clone https://github.com/brimstone/fastcoll && cd fastcoll
g++ -O2 -DBOOST_TIMER_ENABLE_DEPRECATED -o fastcoll *.cpp \
    -lboost_system -lboost_filesystem -lboost_program_options

# Generate a collision with the namespace as prefix
printf 'kitchenexplosion' > prefix.bin
./fastcoll -p prefix.bin -o coll1.bin coll2.bin

 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

from pwn import *
from hashlib import sha256
from Crypto.PublicKey import ECC

# Recipes = collision files minus the 16-byte namespace prefix
m1 = open("coll1.bin", "rb").read()[16:]
m2 = open("coll2.bin", "rb").read()[16:]
assert m1 != m2

curve = ECC._curves["p521"]
n, G = int(curve.order), curve.G
z_of = lambda msg: int.from_bytes(sha256(msg).digest()) & ~(1 << n.bit_length())

io = remote("steamed-foie-gras-marinated-in-juiced-black-garlic-nozp.gpn24.ctf.kitctf.de",
            443, ssl=True)

def sign(msg):
    io.sendlineafter(b"> ", b"sign " + msg.hex().encode())
    io.recvuntil(b"s1: "); s1 = int(io.recvline().strip(), 16)
    io.recvuntil(b"s2: "); s2 = int(io.recvline().strip(), 16)
    return s1, s2

r1, s1 = sign(m1)
r2, s2 = sign(m2)
assert r1 == r2          # same nonce -> same r
r, (z1, z2) = r1, (z_of(m1), z_of(m2))

k = (z1 - z2) * pow(s1 - s2, -1, n) % n
d = (s1 * k - z1) * pow(r, -1, n) % n      # private key

# Sanity-check d against the published public key
io.sendlineafter(b"> ", b"get pkey")
io.recvuntil(b"x: "); px = int(io.recvline().strip())
io.recvuntil(b"y: "); py = int(io.recvline().strip())
Q = d * G
assert int(Q.x) == px and int(Q.y) == py

# Forge a signature for a never-signed recipe
msg3, kf = b"flag-please-forged", 1337
z3 = z_of(msg3)
rf = int((kf * G).x) % n
sf = pow(kf, -1, n) * (z3 + rf * d) % n

io.sendlineafter(b"> ", b"flag please")
io.sendlineafter(b"recipe (hex): ", msg3.hex().encode())
io.sendlineafter(b"s1 (hex): ", hex(rf).encode())
io.sendlineafter(b"s2 (hex): ", hex(sf).encode())
io.recvuntil(b"flag: ")
print(io.recvline().decode().strip())

Output:

1

GPNCTF{May83 W3 Sh0U1D H4ve h1r3D A pRof3s5ION4L?}

Flag

1

GPNCTF{May83 W3 Sh0U1D H4ve h1r3D A pRof3s5ION4L?}