← Z0D1AK writeups
Cryptography ⚡ 112 pts 👥 209 solves ✎ Abhi404 ✓ independently re-verified

Siren

Breaking ECDSA via a Hidden Number Problem lattice attack on a biased nonce.

Challenge brief

The Siren will sing any sailor's words back to him, sealed in her own hand. There is only one phrase she will never voice: the phrase that lifts the tide gate over her hoard.

Give her enough verses and the silence in every breath spells her name.

Flag`zdk{4_F3w_BL7S_per_51gna7uR3_SlNKs_tHE_key}`

Flag: zdk{4_F3w_BL7S_per_51gna7uR3_SlNKs_tHE_key}

TL;DR

The server's ECDSA nonce leaks its top 10 bits through a publicly computable function of the message. A handful of signatures is enough to recover the private key via a lattice-based Hidden Number Problem (HNP) attack, forge a signature on a message the server refuses to sign directly, and unlock the flag.

Target

siren-268feb4305c4.chals.z0d1ak.org:1337 (TLS), secp256k1 ECDSA signer.

Vulnerability

Each nonce k used to sign a message m is constructed as:

k = pitch(m) << 246 | rand(246 bits)
pitch(m) = SHA256(SONG_ID + ":" + m) >> 246   # top 10 bits

SONG_ID is handed out alongside the public key, so pitch(m) — and therefore the top 10 bits of every nonce — is computable by anyone, before a signature is even requested. The server will verify a signature on the restricted message PRIV_MSG, but refuses to sign it directly — the opening for a forgery.

Exploit

Classic HNP reduction. From the ECDSA signing equation s = k⁻¹(z + r·d) mod N:

x ≡ a + b·d  (mod N)
b = s⁻¹r mod N
a = s⁻¹z − pitch(m)·2²⁴⁶ mod N
x = unknown low 246 bits of k,  0 ≤ x < 2²⁴⁶

Lattice construction (dimension m+1, one row per signature sample plus a target row), normalized against the first sample (cᵢ = bᵢ·b₁⁻¹ mod N):

row 0:      (1, c₂, ..., c_m, 0)
row i:      N·eᵢ                    for i = 2..m
row target: (−a₁', ..., −a_m', S)   Kannan embedding, S = 2²⁴⁵ (centered)

LLL-reduce the basis and scan the reduced rows for one ending in ±S. That row's leading coordinate gives x₁ directly, and the private key follows algebraically: d = (x₁ − a₁)·b₁⁻¹ mod N.

Key implementation detail: never embed d itself as a lattice coordinate — it's full-size (~256 bit) and swamps the norm. A first attempt that scaled d into the basis failed to reduce even with 150 signatures and BKZ. Solving only for the small residual x and recovering d afterward is what makes the lattice converge with plain LLL.

Results

Setting Signatures Reduction Result
Local validation (known ground-truth key) n=30 plain LLL 5/5 fresh keys recovered, 100%
Live target n=45 plain LLL Solved end-to-end in ~18s

With the recovered private key, forged a valid signature on unlock:release-the-tide offline and submitted it via the unlock endpoint to obtain the flag.

Tools & Files

Takeaway

Any construction that ties nonce bits to a value derivable before the signature request turns "how many signatures do you need" into a pure lattice-dimension question — 10 leaked bits per signature is more than enough for HNP to bite at n≈30–45.

Solve scripts

attack.py
⇩ Download 
import argparse
import os
import random
import string
import sys

sys.path.insert(0, os.path.dirname(__file__))

from siren_client import SirenClient
from hnp_solve import build_samples, solve_hnp, verify_privkey


def rand_msg(n=16):
    return "".join(random.choices(string.ascii_letters + string.digits, k=n))


def gather(host, port, use_tls, num_sigs):
    c = SirenClient(host, port, use_tls=use_tls)
    pk = c.pubkey()
    Qx = int(pk["Qx"], 16)
    Qy = int(pk["Qy"], 16)
    N = int(pk["n"], 16)
    song_id = pk["song_id"]
    pitch_bits = pk["pitch_bits"]
    priv_msg = pk["priv_msg"]
    print(f"[+] song_id={song_id} pitch_bits={pitch_bits} priv_msg={priv_msg!r}")

    sigs = []
    seen = set()
    while len(sigs) < num_sigs:
        m = rand_msg()
        if m == priv_msg or m in seen:
            continue
        seen.add(m)
        try:
            r, s = c.sign(m)
        except RuntimeError as e:
            print(f"[!] skip {m!r}: {e}")
            continue
        sigs.append((m, r, s))
        if len(sigs) % 20 == 0:
            print(f"[+] collected {len(sigs)}/{num_sigs}")

    return c, Qx, Qy, N, song_id, pitch_bits, priv_msg, sigs


def try_solve(sigs, N, song_id, pitch_bits, Qx, Qy, block_size):
    suffix_bits = N.bit_length() - pitch_bits
    samples = build_samples(sigs, song_id, N, pitch_bits, suffix_bits)
    candidates = solve_hnp(samples, N, suffix_bits, block_size=block_size)
    for d in candidates:
        if d and verify_privkey(d, Qx, Qy, N):
            return d
    return None


def forge_and_unlock(client, d, priv_msg, N):
    from ecdsa import SECP256k1
    import hashlib

    G = SECP256k1.generator
    z = int.from_bytes(hashlib.sha256(priv_msg.encode()).digest(), "big") % N
    k = random.randrange(1, N)
    R = k * G
    r = R.x() % N
    s = (pow(k, -1, N) * (z + r * d)) % N
    print(f"[+] forged signature r={hex(r)} s={hex(s)}")
    resp = client.unlock(r, s)
    print(f"[+] unlock response: {resp}")
    return resp


def main():
    ap = argparse.ArgumentParser()
    ap.add_argument("--host", required=True)
    ap.add_argument("--port", type=int, required=True)
    ap.add_argument("--tls", action="store_true")
    ap.add_argument("--num-sigs", type=int, default=150)
    ap.add_argument("--block-size", type=int, default=20)
    ap.add_argument("--known-d", type=int, default=None,
                     help="ground truth D for local validation runs only")
    args = ap.parse_args()

    c, Qx, Qy, N, song_id, pitch_bits, priv_msg, sigs = gather(
        args.host, args.port, args.tls, args.num_sigs
    )

    print(f"[+] solving with {len(sigs)} signatures, BKZ block_size={args.block_size} ...")
    d = try_solve(sigs, N, song_id, pitch_bits, Qx, Qy, args.block_size)

    if d is None:
        print("[-] FAILED to recover private key with current sample count/block size.")
        if args.known_d is not None:
            print(f"    (ground truth D was {hex(args.known_d)})")
        sys.exit(1)

    print(f"[+] RECOVERED PRIVATE KEY d = {hex(d)}")
    if args.known_d is not None:
        ok = (d == args.known_d)
        print(f"[+] matches ground truth D: {ok}")
        if not ok:
            sys.exit(1)

    forge_and_unlock(c, d, priv_msg, N)


if __name__ == "__main__":
    main()
hnp_solve.py
⇩ Download 
"""
Hidden Number Problem solver for SIREN's biased-nonce ECDSA.

Per signature i on message m_i:
    s_i = k_i^-1 (z_i + r_i * d) mod N
    k_i = A_i * 2^SUFFIX_BITS + x_i,   0 <= x_i < 2^SUFFIX_BITS
    A_i = public_pitch(m_i)  -- known/computable from SONG_ID + m_i

  =>  x_i == a_i + b_i * d   (mod N)
      b_i = s_i^-1 * r_i mod N
      a_i = s_i^-1 * z_i - A_i * 2^SUFFIX_BITS mod N

L = { (y_1,...,y_m) in Z^m : y_i == d*b_i (mod N) for some integer d }
  is a rank-m lattice. Using sample 1 as pivot (c_i = b_i * b_1^-1 mod N):
      row0 = (1, c_2, ..., c_m)
      row_i = N * e_i          for i = 2..m
  is a valid basis of L (standard HNF-style normalization).

We center x_i -> x_i' = x_i - 2^(t-1) so the target is symmetric, then
solve CVP(L, u) with u = (-a_1', ..., -a_m') via Kannan embedding
(append (u, S) as one more basis row, S ~ 2^(t-1), search the reduced
basis for a vector (e_1,...,e_m, +-S)). Recovering x_1 from any hit
lets us solve for d directly: d = (x_1 - a_1) * b_1^-1 mod N.
No unbounded coordinate (d itself) ever enters the lattice, which is
what makes this construction well-conditioned.
"""
import hashlib
from fpylll import IntegerMatrix, LLL, BKZ


def public_pitch(song_id, msg, pitch_bits, nbits):
    material = (song_id + ":" + msg).encode()
    h = int.from_bytes(hashlib.sha256(material).digest(), "big")
    return h >> (nbits - pitch_bits)


def msg_hash(msg, N):
    h = int.from_bytes(hashlib.sha256(msg.encode()).digest(), "big")
    return h % N


def build_samples(sigs, song_id, N, pitch_bits, suffix_bits):
    """sigs: list of (msg, r, s). Returns list of (a_i, b_i)."""
    samples = []
    for msg, r, s in sigs:
        z = msg_hash(msg, N)
        A = public_pitch(song_id, msg, pitch_bits, N.bit_length())
        s_inv = pow(s, -1, N)
        b_i = (s_inv * r) % N
        a_i = (s_inv * z - (A << suffix_bits)) % N
        samples.append((a_i, b_i))
    return samples


def _center(v, N):
    return v - N if v > N // 2 else v


def solve_hnp(samples, N, suffix_bits, block_size=0, pivot=0):
    """
    samples: list of (a_i, b_i) with x_i = a_i + b_i*d mod N, 0 <= x_i < 2^suffix_bits.
    Returns list of candidate d values (int) to verify against the pubkey.
    block_size: 0 disables BKZ (LLL only); otherwise runs BKZ with that block size.
    pivot: index of the sample used to normalize the basis (must have b_pivot != 0).
    """
    m = len(samples)
    if m < 3:
        return []

    half = 1 << (suffix_bits - 1)  # centering offset, also the embedding factor S

    order = [pivot] + [i for i in range(m) if i != pivot]
    a = [samples[i][0] for i in order]
    b = [samples[i][1] for i in order]

    a_c = [(ai - half) % N for ai in a]  # centered targets a_i'

    b1_inv = pow(b[0], -1, N)
    c = [(bi * b1_inv) % N for bi in b[1:]]  # c_2..c_m

    dim = m + 1  # m (lattice L) + 1 (Kannan embedding)
    Mat = IntegerMatrix(dim, dim)

    # row 0: (1, c_2, ..., c_m, 0)
    Mat[0, 0] = 1
    for j, cj in enumerate(c):
        Mat[0, 1 + j] = cj
    # rows 1..m-1: N * e_i for coords 2..m
    for i in range(1, m):
        Mat[i, i] = N
    # row m (target/embedding row): (-a_1', ..., -a_m', S)
    for j in range(m):
        Mat[m, j] = (-a_c[j]) % N
        Mat[m, j] -= N if Mat[m, j] > N // 2 else 0  # keep entries small/signed
    Mat[m, m] = half

    LLL.reduction(Mat)
    if block_size and block_size > 2:
        try:
            BKZ.reduction(Mat, BKZ.Param(block_size=block_size))
        except Exception:
            pass

    candidates = []
    b1 = b[0]
    a1 = a[0]
    for row in range(dim):
        last = Mat[row, m]
        if abs(last) != half:
            continue
        sign = 1 if last == half else -1
        e1 = sign * Mat[row, 0]
        x1_centered = -e1
        x1 = (x1_centered + half) % N
        d_candidate = ((x1 - a1) * pow(b1, -1, N)) % N
        candidates.append(d_candidate)
    return candidates


def verify_privkey(d, Qx, Qy, N):
    from ecdsa import SECP256k1

    G = SECP256k1.generator
    P = d * G
    return P.x() == Qx and P.y() == Qy
siren_client.py
⇩ Download 
"""
Client for the SIREN JSON-line protocol.
Works against both a plaintext local test instance and the real TLS target.
"""
import json
import socket
import ssl


class SirenClient:
    def __init__(self, host, port, use_tls=True, timeout=15):
        self.host = host
        self.port = port
        raw = socket.create_connection((host, port), timeout=timeout)
        if use_tls:
            ctx = ssl.create_default_context()
            ctx.check_hostname = False
            ctx.verify_mode = ssl.CERT_NONE
            self.sock = ctx.wrap_socket(raw, server_hostname=host)
        else:
            self.sock = raw
        self.rfile = self.sock.makefile("r", encoding="utf-8", newline="\n")
        banner = self.rfile.readline()
        self.banner = json.loads(banner) if banner.strip() else {}

    def _send(self, obj):
        line = (json.dumps(obj) + "\n").encode()
        self.sock.sendall(line)
        resp = self.rfile.readline()
        if not resp:
            raise ConnectionError("connection closed by server")
        return json.loads(resp)

    def pubkey(self):
        return self._send({"cmd": "pubkey"})

    def sign(self, msg):
        resp = self._send({"cmd": "sign", "msg": msg})
        if "error" in resp:
            raise RuntimeError(f"sign error: {resp['error']}")
        return int(resp["r"], 16), int(resp["s"], 16)

    def unlock(self, r, s):
        return self._send({"cmd": "unlock", "r": hex(r), "s": hex(s)})

    def close(self):
        try:
            self.sock.close()
        except Exception:
            pass