KAPOLRI CUP 2026: Coppersmith Curve

KAPOLRI CUP 2026 • 2026-08-01 • Cryptography

#KAPOLRI CUP 2026 #Coppersmith #Elliptic Curve #RSA #Crypto

coppersmith-curve — polriCTF 2026 (writeup lengkap)

Kategori: Crypto (RSA broadcast attack + ECDSA nonce recovery)
Akses: nc 18.143.187.232 9008
Flag: polriCTF26{hastad_broadcast_leaks_the_ecdsa_nonce_and_the_curve_falls}

1. Challenge

”Zero-Trust Identity” — login sebagai admin = menyodorkan tanda tangan ECDSA secp256k1 (r, s) yang valid atas pesan persis b"admin=true". Tapi layanan Cuma mau menandatangani heartbeat-nya sendiri. Menu:

1. mirror seed to replicas    -> N1,e,C1 / N2,e,C2 / N3,e,C3  (RSA, e=3)
2. leak heartbeat signature   -> msg, r, s                    (ECDSA)
3. admin login                -> submit (r,s) atas "admin=true"
4. show pubkey Q + PRNG source

Tujuan: recover private key d → tanda tangani admin=true → submit.

class NonceRNG:
    MASK = (1<<128)-1
    def __init__(self, seed):
        h = sha256(long_to_bytes(seed)).digest()
        self.s = bytes_to_long(h[:16]) | 1
    def _step(self):
        x = self.s
        x ^= (x << 13) & MASK
        x ^= (x >> 7)
        x ^= (x << 17) & MASK
        self.s = x & MASK
        return self.s
    def next_scalar(self):
        hi = self._step(); lo = self._step()
        return ((hi<<128)|lo) % N

Nonce heartbeat = hasil next_scalar() pertama.
Seed per-koneksi dibagikan lewat RSA-broadcast: m = int(b"ZTRUST-IDENTITY-SEED-v1::" || seed(32B) || b"\x00"*8 || (b"ZT")*80) — identik di tiga node.

3. Langkah 1 — Håstad broadcast (e=3)

Tiga ciphertext RSA berisi pesan m yang sama persis dengan e = 3:

C_i = m^3 mod N_i        (i = 1,2,3)

Kenapa bisa di-recover?

Selama m^3 < N1·N2·N3, nilai m^3 itu unik mod N1·N2·N3. Jadi rekonstruksi m^3 pakai CRT, bukan brute-force per modulus:

M   = N1 · N2 · N3
M_i = M / N_i
T   = Σ C_i · M_i · inv(M_i, N_i)   (mod M)
m   = iroot3(T)                      → akar kubik eksak

Menjadi seed

m di-parse jadi bytes, slice 32 byte seed-nya:

bytes(m) = "ZTRUST-IDENTITY-SEED-v1::" (26B) || seed (32B) || "\x00"*8 || "ZT"*80
                              ↑ seed = m[26 : 26+32]

⚠️ Gotcha: seed = field 32 byte, bukan seluruh m. Kalau pakai int(m) langsung sebagai seed, sha256(long_to_bytes(seed)) menghitung hash dari 225+ byte, bukan 32 byte → nonce salah → d salah.

4. Langkah 2 — Prediksi nonce

Dengan seed yang sudah di-recover, jalankan PRNG persis seperti source:

h  = sha256(long_to_bytes(seed)).digest()
s0 = bytes_to_long(h[:16]) | 1     # |1 cuma mastiin s ganjil, gak ngaruh determinisme

def step(x):
    x ^= (x << 13) & MASK
    x ^= x >> 7
    x ^= (x << 17) & MASK
    return x & MASK

hi = step(s0)
k  = ((hi << 128) | step(hi)) % N   # next_scalar() pertama = nonce heartbeat

PRNG-nya fully deterministic — begitu seed ketemu, nonce k langsung diketahui.

5. Langkah 3 — Recover private key (ECDSA)

Tanda tangan heartbeat (r, s) memenuhi:

s = k⁻¹ · (z + r·d)  (mod n)      z = int(sha256(msg)),  n = order kurva

Karena k sudah kita tahu, balik rumusnya → dapat d:

d = (s·k − z) · r⁻¹  (mod n)

Verifikasi penting biar gak ngirim signature salah diam-diam:

d·G == Q    (Q = pubkey dari menu 4)

Kalau cocok, d pasti benar.

Referensi teori: ECDSa Private Key Extraction (kf106.medium.com)

6. Langkah 4 — Sign `admin=true` & submit

Punya d, tanda tangani b"admin=true" dengan nonce baru sembarang:

z2 = int(sha256(b"admin=true"))
k2 = (nonce pilihan, misal fixed 0xDEADBEEF1234567)
R  = k2 · G
r2 = R.x  mod n
s2 = k2⁻¹ · (z2 + r2·d)  mod n

Submit (r2, s2) di menu 3 → access granted. flag: ...

7. Rantai serangan (ringkasan)

RSA broadcast (e=3) ──CRT+iroot3──▶ seed
seed ──NonceRNG.next_scalar()──▶ nonce k
(k, r, s) ──d=(s·k−z)·r⁻¹──▶ private key d   [cek d·G==Q]
d ──sign "admin=true"──▶ (r2, s2) ──submit──▶ FLAG

8. Catatan tambahan (hasil observasi live)

Q & private key per-session. Semua data (N1,C1, heartbeat, Q) harus dari satu koneksi; jangan campur session lain, kalau tidak d·G == Q gagal.
Panjang m bisa 225 byte, bukan 226 (byte high bisa hilang di long_to_bytes). Seed-nya tetap m[26:58] (32 byte) — jangan dipotong dari ujung.

9. Solver (auto, satu koneksi)

import socket, time, re, hashlib
from Crypto.Util.number import long_to_bytes, bytes_to_long

P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
     0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

def inv(a, m): return pow(a, -1, m)

def ec_add(p1, p2):
    if p1 is None: return p2
    if p2 is None: return p1
    x1, y1 = p1; x2, y2 = p2
    if x1 == x2 and (y1 + y2) % P == 0: return None
    lam = (3*x1*x1) * inv(2*y1, P) % P if p1 == p2 else (y2-y1) * inv(x2-x1, P) % P
    x3 = (lam*lam - x1 - x2) % P
    return (x3, (lam*(x1-x3) - y1) % P)

def ec_mul(k, G=G):
    k %= N; r, a = None, G
    while k:
        if k & 1: r = ec_add(r, a)
        a = ec_add(a, a); k >>= 1
    return r

def iroot3(x):
    lo, hi = 0, 1
    while hi**3 <= x: hi *= 2
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if mid**3 <= x: lo = mid
        else: hi = mid
    return lo

class Conn:
    def __init__(self):
        self.s = socket.create_connection(("18.143.187.232", 9008), timeout=10)
        self.s.settimeout(6); self.buf = b""
    def read(self, wait=0.3):
        time.sleep(wait); end = time.time() + 3
        while time.time() < end:
            try: d = self.s.recv(65536)
            except socket.timeout: d = b""
            if d: self.buf += d
            out = self.buf.decode("latin1", "replace")
            if "> " in out: self.buf = b""; return out
            if not d: time.sleep(0.05)
        return self.buf.decode("latin1", "replace")
    def send(self, x): self.s.sendall(x.encode() + b"\n")
    def cmd(self, opt, wait=0.4): self.send(str(opt)); return self.read(wait)

def num(regex, text): return int(re.search(regex, text).group(1))

def main():
    c = Conn(); c.read(0.2)
    Qx = num(r"Qx\s*=\s*(\d+)", c.cmd(4)); Qy = num(r"Qy\s*=\s*(\d+)", c.cmd(4))

    r1 = c.cmd(1)
    N1, C1 = num(r"N1\s*=\s*(\d+)", r1), num(r"C1\s*=\s*(\d+)", r1)
    N2, C2 = num(r"N2\s*=\s*(\d+)", r1), num(r"C2\s*=\s*(\d+)", r1)
    N3, C3 = num(r"N3\s*=\s*(\d+)", r1), num(r"C3\s*=\s*(\d+)", r1)

    r2 = c.cmd(2)
    msg = re.search(r"msg\s*=\s*(\S+)", r2).group(1)
    rh, sh = num(r"r\s*=\s*(\d+)", r2), num(r"s\s*=\s*(\d+)", r2)

    # 1) Håstad broadcast
    M = N1*N2*N3; T = 0
    for Ni, Ci in ((N1,C1),(N2,C2),(N3,C3)):
        Mi = M // Ni; T += Ci * Mi * inv(Mi, Ni)
    m = iroot3(T % M); assert m**3 == T % M
    mb = long_to_bytes(m)
    seed = mb[len(b"ZTRUST-IDENTITY-SEED-v1::"):][:32]

    # 2) nonce dari PRNG
    MASK = (1 << 128) - 1
    h = hashlib.sha256(long_to_bytes(bytes_to_long(seed))).digest()
    s = bytes_to_long(h[:16]) | 1
    def step(x):
        x ^= (x << 13) & MASK; x ^= x >> 7; x ^= (x << 17) & MASK
        return x & MASK
    hi = step(s)
    k = ((hi << 128) | step(hi)) % N

    # 3) private key
    z = bytes_to_long(hashlib.sha256(msg.encode()).digest())
    d = ((sh * k - z) * inv(rh, N)) % N
    assert ec_mul(d) == (Qx, Qy), "public key check failed"

    # 4) sign admin=true
    z2 = bytes_to_long(hashlib.sha256(b"admin=true").digest())
    k2 = 0xDEADBEEF1234567
    R = ec_mul(k2)
    r2s, s2s = R[0] % N, (inv(k2, N) * (z2 + R[0]*d)) % N

    c.cmd(3); c.send(str(r2s)); c.read(0.2); c.send(str(s2s))
    print(c.read(0.6)); c.s.close()

if __name__ == "__main__":
    main()

Output:

access granted. flag: polriCTF26{hastad_broadcast_leaks_the_ecdsa_nonce_and_the_curve_falls}

10. Kenapa challenge ini “jatuh”

e=3 + pesan identik → Håstad, seed bocor.
PRNG nonce deterministik & berbasis seed publik → nonce k bisa diprediksi.
Satu signature + nonce bocor → private key bisa dihitung (ECDSA gak aman kalau nonce-nya bukan rahasia).

Itu kenapa namanya hastad_broadcast_leaks_the_ecdsa_nonce_and_the_curve_falls — semua alurnya ada di nama flagnya.