//void

Author (challenge): Iacob Razvan Mihai

Flag format: CTF{...}

This writeup explains the full solve path “top to bottom”: reading the code, recognizing the crypto issue, turning it into equations, handling the extra obfuscation around the nonce relation, and implementing a working solver.

>1) Files and what they contain

Workspace files:

chall.py
out.txt
(My solver) solve.py

The provided out.txt is a captured run of chall.py.

>2) Understanding the scheme in chall.py

The core parts of chall.py:

2.1) Curve and ECDSA

python


O, G_PT = C.secp256k1.q, C.secp256k1.G

...

S=lambda m,d,k:(lambda R:(R,(pow(k,-1,O)*(H(m)+R*d))%O))((k*G_PT).x%O)

Curve: secp256k1.
O is the group order (usually called n in ECDSA descriptions).
S(m,d,k) is ECDSA signing implemented manually:
R = (k*G).x mod O (their r)
s = k^(-1) * (H(m) + r*d) mod O

2.2) The “message” being signed

python


m = bytes(J)

J is a 256-byte table computed from secp256k1 points:

python


for i in range(256):

    pt=(i+1)*G_PT

    J.append(H(str(pt.x).encode())&0xFF)

So the message is constant and fully reconstructible: it’s just the 256 derived bytes.

2.3) The nonce relation (the real vulnerability)

The code signs the same message twice:

python


a,b,k = Y(x,b'a'), Y(x,b'b'), Y(x,b'0')

r1,s1 = S(m,d,k)

k = (a*k + b) % O

r2,s2 = S(m,d,k)

This is the key observation:

First signature uses nonce $k_1 = k$.
Second signature uses nonce $k_2 = a k_1 + b \pmod{O}$.

That’s a linear relation between ECDSA nonces. ECDSA is extremely sensitive to nonce problems: if you can relate/guess nonces you can usually recover the private key.

2.4) What is leaked to the attacker

The output contains:

W(x) printed as 8 hex chars (32 bits)
Two ECDSA signatures (r1,s1), (r2,s2)
AES-ECB encryption of the flag with key SHA256(str(d))

python


print(f"{W(x):08x}")

...

print(A.new(hashlib.sha256(str(d).encode()).digest(),A.MODE_ECB)

        .encrypt(P(b"CTF{something}",16)).hex())

So: recover d → derive AES key → decrypt flag.

>3) Turning the ECDSA relation into a private key formula

ECDSA signing equation (modulo group order $O$):

[ s \equiv k^{-1}(h + r d) \pmod{O} ]

where:

$h = H(m)$ (SHA-256 interpreted as an integer)
$r = x(kG)$ $mod O$ (x-coordinate reduced mod 0)
$d$ is the private key

Rearrange to isolate k:

[ k \equiv (h + r d) s^{-1} \pmod{O} ]

Apply this to both signatures:

[

egin{aligned}

k_1 &\equiv (h + r_1 d) s_1^{-1} \pmod{O}\

k_2 &\equiv (h + r_2 d) s_2^{-1} \pmod{O}

\end{aligned}

]

But we also know:

$[ k_2 \equiv a k_1 + b \pmod{O} ]$

Substitute the two $k$ expressions:

[ (h + r_2 d)s_2^{-1} \equiv a(h + r_1 d)s_1^{-1} + b \pmod{O} ]

Expand and group terms in $d$:

[ h s_2^{-1} + r_2 d s_2^{-1} \equiv a h s_1^{-1} + a r_1 d s_1^{-1} + b \pmod{O} ]

Move all to one side:

[ d,(r_2 s_2^{-1} - a r_1 s_1^{-1}) \equiv (a h s_1^{-1} + b - h s_2^{-1}) \pmod{O} ]

So, if the denominator is invertible:

[

d \equiv (a h s_1^{-1} + b - h s_2^{-1}),(r_2 s_2^{-1} - a r_1 s_1^{-1})^{-1} \pmod{O}

]

This means:

If we know $(a,b)$, we can compute $d$ in one shot.
Then we decrypt the AES ciphertext.

So the entire problem reduces to: recover x (or at least derive a,b) from the leaked 32-bit W(x).

>4) Breaking the `W(x)` obfuscation to recover x

x is generated as 52 random bits:

python


x = int.from_bytes(os.urandom(7),'big') & 0xFFFFFFFFFFFFF

So $x < 2^{52}$.

They compute:

python


W=lambda x:(G(x&0x3FFFFFF)^G((x>>26)&0x3FFFFFF))

Let:

$u = x & (2^{26}-1)$ (low 26 bits)
$v = (x >> 26) & (2^{26}-1)$ (high 26 bits)

Then:

$[ W(x) = G(u) \oplus G(v) ]$

where G(·) maps a 26-bit input to a 32-bit output.

4.1) Why this is solvable

Brute-forcing 52 bits directly is impossible.

But the split structure gives a classic meet-in-the-middle:

$[ G(u) = W \oplus G(v) ]$

So:

Enumerate all $u \in [0,2^{26})$ and store G(u).
Enumerate all $v \in [0,2^{26})$ and look up whether G(v) ^ W is present.

That’s about $2^{26}$ work (per side) and is feasible with some care.

4.2) Practical detail: don’t store everything as a Python dict

A naive Python dictionary holding ~67 million keys is too slow and memory-heavy.

My approach in solve.py is a “bucketed MITM”:

For each side, write records (key, value) to 256 bucket files based on the top 8 bits of key.
Then process each bucket independently:
load that bucket from disk
sort and match equal keys

This avoids a single giant in-memory table.

>5) Full solve pipeline

Putting it all together:

Rebuild the J table exactly as the challenge does.
Parse out.txt to get W, the two signatures, and the AES ciphertext.
Meet-in-the-middle to get candidate x values that satisfy W(x).
For each candidate x:

compute a=Y(x,'a'), b=Y(x,'b')
compute private key d using the derived formula
decrypt AES-ECB with key SHA256(str(d))
accept plaintext that matches CTF{...}

>6) Local success (provided out.txt)

6.1) Install dependencies

The challenge uses fastecdsa and pycryptodome.

Install (at minimum):

bash


python3 -m pip install --user fastecdsa

6.2) Run solver

bash


python3 solve.py

If your terminal visually wraps the long flag, extract it as a single token:

bash


python3 solve.py | tr -d '

' | sed -n 's/.*\\(CTF{[^}]*}\\).*//p'

>7) Remote success (typical CTF deployment)

Only local files were provided here, but remote crypto challenges usually behave like:

Connect via nc HOST PORT
The service prints the same 4 lines as out.txt
You recover the flag

7.1) One-shot remote

Grab the output:

bash


nc HOST PORT | tee remote_out.txt

Solve it:

bash


cp remote_out.txt out.txt

python3 solve.py

>8) Why this approach is the right one

The key “Aha” moments:

ECDSA is written explicitly in the code, so standard algebra applies.
The nonce is not random twice: it is linearly related across signatures ($k_2 = a k_1 + b$). This is a known catastrophic failure mode for ECDSA.
The only remaining obstacle is deriving (a,b), which depends on x, and W(x) splits cleanly into two 26-bit halves with XOR — perfect for meet-in-the-middle.

>9) Full solver code (verbatim)

python


#!/usr/bin/env python3

import hashlib

import os

import struct

from pathlib import Path

import numpy as np

from Crypto.Cipher import AES

from Crypto.Util.Padding import unpad

from fastecdsa import curve

def sha256_int(data: bytes) -> int:

    return int.from_bytes(hashlib.sha256(data).digest(), "big")

def inv_mod(a: int, m: int) -> int:

    return pow(a, -1, m)

def build_J() -> np.ndarray:

    # Mirrors chall.py:

    # J[i] = H(str(((i+1)*G).x).encode()) & 0xFF

    C = curve.secp256k1

    G = C.G

    J = np.empty(256, dtype=np.uint32)

    for i in range(256):

        pt = (i + 1) * G

        hx = sha256_int(str(pt.x).encode())

        J[i] = hx & 0xFF

    return J

def G_func(x: np.ndarray, J: np.ndarray) -> np.ndarray:

    # x: uint32 array

    # G(x) from chall.py, with x assumed already masked to 26 bits

    b0 = x & np.uint32(0xFF)

    b1 = (x >> np.uint32(8)) & np.uint32(0xFF)

    b2 = (x >> np.uint32(16)) & np.uint32(0xFF)

    b3 = (x >> np.uint32(24)) & np.uint32(0x3)

    t = (

        J[b0]

        ^ (J[b1] << np.uint32(5))

        ^ (J[b2] << np.uint32(10))

        ^ (J[b3] << np.uint32(15))

    ).astype(np.uint32)

    return (t * np.uint32(0x9E3779B1)).astype(np.uint32)

def parse_out(path: Path):

    lines = [ln.strip() for ln in path.read_text().splitlines() if ln.strip()]

    w = int(lines[0], 16)

    def parse_sig(s):

        r, ss = s.split(":")

        return int(r, 16), int(ss, 16)

    r1, s1 = parse_sig(lines[1])

    r2, s2 = parse_sig(lines[2])

    ct = bytes.fromhex(lines[3])

    return w, (r1, s1), (r2, s2), ct

def derive_Y(x: int, tag: bytes, O: int) -> int:

    xb = x.to_bytes(7, "big")

    return sha256_int(xb + tag) % O

def try_x(

    x: int,

    O: int,

    h: int,

    r1: int,

    s1: int,

    r2: int,

    s2: int,

    ct: bytes,

):

    a = derive_Y(x, b"a", O)

    b = derive_Y(x, b"b", O)

    invs1 = inv_mod(s1, O)

    invs2 = inv_mod(s2, O)

    denom = (r2 * invs2 - (a % O) * r1 * invs1) % O

    if denom == 0:

        return None

    numer = (b - h * ((invs2 - (a % O) * invs1) % O)) % O

    d = (numer * inv_mod(denom, O)) % O

    # Derive AES key, decrypt, and check flag format

    key = hashlib.sha256(str(d).encode()).digest()

    pt_padded = AES.new(key, AES.MODE_ECB).decrypt(ct)

    try:

        pt = unpad(pt_padded, 16)

    except ValueError:

        return None

    # Tighten validity checks to avoid false positives.

    # The original chall encrypts ASCII bytes; reject embedded whitespace/newlines.

    if not (pt.startswith(b"CTF{") and pt.endswith(b"}")):

        return None

    if any(c in pt for c in (b"\\n", b"\\r", b"\\t")):

        return None

    if not all(32 <= c <= 126 for c in pt):

        return None

    return pt.decode(errors="strict")

    return None

def generate_bucket_files(

    *,

    J: np.ndarray,

    W: int,

    tmpdir: Path,

    which: str,

    chunk_size: int = 2_097_152,

):

    """Generate bucketed (key,val) records.

    which='u': key=G(u), val=u

    which='v': key=G(v)^W, val=v

    Buckets by top 8 bits of key (256 files).

    """

    assert which in {"u", "v"}

    outdir = tmpdir / which

    outdir.mkdir(parents=True, exist_ok=True)

    handles = []

    for b in range(256):

        f = open(outdir / f"b{b:02x}.bin", "ab", buffering=1024 * 1024)

        handles.append(f)

    rec_dtype = np.dtype([("key", "<u4"), ("val", "<u4")])

    limit = 1 << 26

    W_u32 = np.uint32(W)

    for start in range(0, limit, chunk_size):

        end = min(limit, start + chunk_size)

        vals = np.arange(start, end, dtype=np.uint32)

        g = G_func(vals, J)

        if which == "v":

            keys = (g ^ W_u32).astype(np.uint32)

        else:

            keys = g

        buckets = (keys >> np.uint32(24)).astype(np.uint8)

        # Bucket-sort indices (fast C implementation in NumPy)

        order = np.argsort(buckets, kind="stable")

        keys_s = keys[order]

        vals_s = vals[order]

        counts = np.bincount(buckets, minlength=256)

        offsets = np.empty(257, dtype=np.int64)

        offsets[0] = 0

        np.cumsum(counts, out=offsets[1:])

        rec = np.empty(len(vals_s), dtype=rec_dtype)

        rec["key"] = keys_s

        rec["val"] = vals_s

        # Write contiguous runs per bucket

        run_starts = offsets[:-1]

        for b in range(256):

            n = int(counts[b])

            if n == 0:

                continue

            s = int(run_starts[b])

            handles[b].write(rec[s : s + n].tobytes(order="C"))

    for f in handles:

        f.close()

def iter_bucket_matches(u_path: Path, v_path: Path):

    rec_dtype = np.dtype([("key", "<u4"), ("val", "<u4")])

    if not u_path.exists() or not v_path.exists():

        return

    u = np.fromfile(u_path, dtype=rec_dtype)

    v = np.fromfile(v_path, dtype=rec_dtype)

    if len(u) == 0 or len(v) == 0:

        return

    u = u[np.argsort(u["key"], kind="quicksort")]

    v = v[np.argsort(v["key"], kind="quicksort")]

    u_keys = u["key"]

    v_keys = v["key"]

    u_uniq, u_first, u_counts = np.unique(u_keys, return_index=True, return_counts=True)

    v_uniq, v_first, v_counts = np.unique(v_keys, return_index=True, return_counts=True)

    # Intersect unique keys and yield cartesian products of vals for each key

    common = np.intersect1d(u_uniq, v_uniq, assume_unique=True)

    if len(common) == 0:

        return

    # Map key -> (start,count) via searchsorted since u_uniq / v_uniq are sorted

    u_pos = np.searchsorted(u_uniq, common)

    v_pos = np.searchsorted(v_uniq, common)

    for i in range(len(common)):

        us = int(u_first[u_pos[i]])

        uc = int(u_counts[u_pos[i]])

        vs = int(v_first[v_pos[i]])

        vc = int(v_counts[v_pos[i]])

        u_vals = u["val"][us : us + uc]

        v_vals = v["val"][vs : vs + vc]

        for uu in u_vals:

            for vv in v_vals:

                yield int(uu), int(vv)

def main():

    here = Path(__file__).resolve().parent

    W, (r1, s1), (r2, s2), ct = parse_out(here / "out.txt")

    C = curve.secp256k1

    O = C.q

    print("[+] Building J table...")

    J = build_J()

    m = bytes([int(x) for x in J.tolist()])

    h = sha256_int(m)

    tmpdir = here / ".buckets"

    tmpdir.mkdir(exist_ok=True)

    # Generate bucket files if not already present

    marker_u = tmpdir / "u" / "DONE"

    marker_v = tmpdir / "v" / "DONE"

    if not marker_u.exists():

        print("[+] Generating u-side buckets (key=G(u))...")

        generate_bucket_files(J=J, W=W, tmpdir=tmpdir, which="u")

        marker_u.write_text("ok")

    else:

        print("[+] Reusing existing u-side buckets")

    if not marker_v.exists():

        print("[+] Generating v-side buckets (key=G(v)^W))...")

        generate_bucket_files(J=J, W=W, tmpdir=tmpdir, which="v")

        marker_v.write_text("ok")

    else:

        print("[+] Reusing existing v-side buckets")

    print("[+] Searching for x candidates and decrypting...")

    tested = 0

    for b in range(256):

        u_path = tmpdir / "u" / f"b{b:02x}.bin"

        v_path = tmpdir / "v" / f"b{b:02x}.bin"

        for uu, vv in iter_bucket_matches(u_path, v_path):

            x = uu | (vv << 26)

            tested += 1

            flag = try_x(x, O, h, r1, s1, r2, s2, ct)

            if flag is not None:

                print(f"[+] Found after {tested} candidates: {flag}")

                return

        if b % 16 == 15:

            print(f"    ...bucket {b:02x}/ff done, tested {tested}")

    print("[-] No flag found. (Unexpected)")

if __name__ == "__main__":

    main()

>10) Flag

Recovered from the provided out.txt:

CTF{35e670c3abbc4a58c0de89d04123465b5a0708fc0ffeec48cc2a406284258881}

>11) Notes / troubleshooting

First run creates a .buckets/ directory containing bucket files for the meet-in-the-middle step. Subsequent runs are much faster.
Delete .buckets/ if you want to force regeneration.

>12) References

ECDSA overview and equations: https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
NIST DSS (ECDSA standard): https://csrc.nist.gov/publications/detail/fips/186/4/final
Meet-in-the-middle technique: https://en.wikipedia.org/wiki/Meet-in-the-middle_attack
SECG SEC2 (secp256k1 parameters are commonly listed in SEC2): https://www.secg.org/sec2-v2.pdf

//void

>1) Files and what they contain

>2) Understanding the scheme in chall.py

2.1) Curve and ECDSA

2.2) The “message” being signed

2.3) The nonce relation (the real vulnerability)

2.4) What is leaked to the attacker

>3) Turning the ECDSA relation into a private key formula

>4) Breaking the W(x) obfuscation to recover x

4.1) Why this is solvable

4.2) Practical detail: don’t store everything as a Python dict

>5) Full solve pipeline

>6) Local success (provided out.txt)

6.1) Install dependencies

6.2) Run solver

>7) Remote success (typical CTF deployment)

7.1) One-shot remote

>8) Why this approach is the right one

>9) Full solver code (verbatim)

>10) Flag

>11) Notes / troubleshooting

>12) References

>4) Breaking the `W(x)` obfuscation to recover x