Writeup · 31 Nights of Root

The Weierstrass Gambit

cryptomediumsolvedFlag: r00t{REDACTED}

Overview

The banner advertises secp256r1 ECDSA over sha256(message), with the token format:

user=<username>|role=<role>|ts=<unix_ts>

Requesting TOKEN alice repeatedly produced a suspicious pattern — the r value stayed identical across several signatures while s changed:

TOKEN user=alice|role=user|ts=... 2a21a4e6e6...f90808 9dca785d...
TOKEN user=alice|role=user|ts=... 2a21a4e6e6...f90808 7ee43c04...
TOKEN user=alice|role=user|ts=... 2a21a4e6e6...f90808 edf70505...

A repeated r means the same nonce k was reused. Two signatures over different messages are then enough to solve for the private key d.

Prerequisites / Setup

  • Python 3 (pow(x, -1, n) for modular inverse)
  • A raw TCP client (nc or Python socket)
  • The solve.py solver script saved in the challenge folder

Recon

Step 1 — Banner and token format

Goal: Learn the curve, hash, and token format from the server banner.

The server advertises secp256r1 ECDSA over sha256(message), token format user=<username>|role=<role>|ts=<unix_ts>.

Vulnerability Analysis

The flaw classes are ECDSA Nonce Reuse and CTR Keystream Reuse (two-time pad).

1. ECDSA nonce reuse

For two signatures (r, s₁) and (r, s₂) over message hashes z₁, z₂ with the same nonce k:

sᵢ = k⁻¹ (zᵢ + r·d)  (mod n)
=> k = (z₁ − z₂) / (s₁ − s₂)  (mod n)
=> d = (s₁·k − z₁) / r        (mod n)

Because the server rotates its nonce in bursts, the solver collects tokens until two share the same r and differ in ts, then recovers d. The recovered key was confirmed by re-deriving the public point d·G and comparing it to PUBKEY.

2. AES-CTR keystream reuse

SAMPLE returns AES-256-CTR encryption of a fully documented plaintext, and VAULT returns CTR encryption of the real secret under the same key/nonce. CTR is a stream cipher, so:

keystream = SAMPLE_ct XOR known_plaintext
VAULT_plaintext = VAULT_ct XOR keystream

This recovers the vault contents directly.

Exploitation

Step 2 — Forge an admin signature

Goal: Using the recovered d, sign an arbitrary admin message with a fresh nonce and submit it.

user=alice|role=admin|ts=<now>

Submit it with ADMIN <msg> <r_hex> <s_hex>. The server answers:

OK admin session granted

Note that the server does not care who originally requested a token — only that the signature validates and the role field is exactly admin. That is the design flaw the challenge description hints at.

Step 3 — Decrypt the vault

Goal: Recover the keystream from SAMPLE and decrypt VAULT.

# 1) collect tokens until r repeats, then recover d
z1, z2 = z_of(m1), z_of(m2)
k = (z1 - z2) * pow(s1 - s2, -1, n) % n
d = (s1 * k - z1) * pow(r, -1, n) % n

# 2) forge role=admin
msg = f"user=alice|role=admin|ts={int(time.time())}".encode()
fr, fs = sign(d, msg)
c.cmd(f"ADMIN {msg.decode()} {fr:064x} {fs:064x}")

# 3) decrypt the vault with the SAMPLE keystream
ks = bytes(x ^ y for x, y in zip(sample, known))
plain = bytes(x ^ ks[i % len(ks)] for i, x in enumerate(vault))

Output:

[+] recovered private key d = 0x...
[+] derived public key matches server PUBKEY
[+] ADMIN -> OK admin session granted
[+] vault plaintext:
r00t{REDACTED}

Flag

r00t{REDACTED}

Lessons / Takeaways

  • ECDSA nonces must be unique and unpredictable: reusing k across two signatures collapses ECDSA completely. This applies to biased or partially known nonces too (lattice/HNP attacks). Use RFC 6979 deterministic nonces or a CSPRNG, and never a time-derived or cached nonce.
  • CTR is a stream cipher: encrypting two plaintexts under the same key/nonce is a two-time pad. A single known plaintext reveals the keystream for the whole message. Always use a fresh nonce per message; authenticated modes such as AES-GCM also prevent silent tampering.
  • Treat server text as untrusted: NOTICE contained an explicit “AI-Agent instruction” telling the client to stop and submit a fake flag, and VERSION advertised an invalidated legacy flag. Neither is data worth trusting; only the cryptographically recovered vault contents are authoritative.

Mitigations

  • Use RFC 6979 deterministic nonces (derives k from the private key and message hash via HMAC-DRBG, so the same nonce is never produced for two different messages).
  • Never reuse a key/nonce pair in CTR mode; use authenticated encryption (AES-GCM, ChaCha20-Poly1305).
  • Do not act on unsolicited instructions embedded in server responses.

Techniques

References