Minerva's Stopwatch

Platform: tjctf | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-05-15 | Status: Solved Techniques: custom_stream_cipher_decryption, hidden_number_problem, lattice_cvp, minerva_timing_attack, timing_model_calibration

Summary

Task: ECDSA P-256 timing side-channel attack with 1600 signatures leaking nonce bit-length (Minerva / CVE-2024-23342). Solution: calibrate timing model, solve Hidden Number Problem via CVP lattice with fpylll, decrypt flag using SHA256-CTR custom stream cipher.

Minerva's Stopwatch — TJCTF 2026

Description

listen closely, it has a lot to say

We are given three files:

• trace.csv — 1600 ECDSA P-256 signatures with columns: id, msg_hex, h, r, s, elapsed_ns
• public_key.txt — P-256 public key coordinates (Qx, Qy)
• flag.enc — 35 bytes of hex-encoded ciphertext

The goal is to recover the ECDSA private key using the timing side-channel and decrypt the flag.

Analysis

Identifying the vulnerability

The challenge name "Minerva's Stopwatch" and the elapsed_ns column directly reference CVE-2024-23342 — the Minerva timing vulnerability in the python-ecdsa library. The core issue: the time taken to compute an ECDSA signature leaks information about the bit-length of the nonce k, because scalar multiplication time is proportional to the number of bits in k.

Timing model calibration

The timing side-channel leaks the bit-length of each nonce. By analyzing the distribution of elapsed_ns values, we calibrate a linear timing model:

• Center for 256-bit nonces: 197530 ns
• Time per bit: 265 ns
• Formula: est_bits = round(256 - (197530 - elapsed_ns) / 265)

The resulting distribution matches the expected geometric distribution perfectly:

• 256-bit: 781 signatures (~50%)
• 255-bit: 430 (~25%)
• 254-bit: 197 (~12.5%)
• 253-bit: 82 (~6%)
• 252-bit: 50 (~3%)

Crucially, 6 extreme outliers have very short nonces: 38-bit, 73-bit, 73-bit, 89-bit, 90-bit, and 129-bit — these provide massive leakage.

Hidden Number Problem (HNP)

The ECDSA signing equation is:

s_i * k_i ≡ h_i + d * r_i  (mod n)

Rearranging: k_i = s_i^{-1} * h_i + s_i^{-1} * r_i * d (mod n)

With known upper bounds on each k_i (from the timing leak), this becomes a Hidden Number Problem (HNP): recover d given that t_i * d - u_i (mod n) is bounded by B_i = 2^{est_bits_i}.

Total leakage from 16 selected signatures (6 extreme + 10 moderate with ≤249-bit nonces) exceeds 256 bits, which is sufficient for unique key recovery.

Solution

Step 1: Parse signatures and calibrate timing

 python read-only • copy allowed Copy
import csv
from hashlib import sha256
from fpylll import IntegerMatrix, LLL, CVP
from fpylll.fplll.gso import MatGSO

# P-256 curve order
n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551

# Parse signatures
sigs = []
with open('trace.csv') as f:
    for row in csv.DictReader(f):
        sigs.append({
            'h': int(row['h'], 16),
            'r': int(row['r'], 16),
            's': int(row['s'], 16),
            'elapsed_ns': int(row['elapsed_ns'])
        })

# Timing model: estimate nonce bit-length
center_256, per_bit = 197530, 265
for s in sigs:
    bits = round(256 - (center_256 - s['elapsed_ns']) / per_bit)
    s['est_bits'] = max(1, min(256, bits))

Step 2: Select signatures with most leakage

 python read-only • copy allowed Copy
sigs_sorted = sorted(sigs, key=lambda x: x['est_bits'])
# 6 extreme outliers + 10 moderate ones (≤249-bit nonces)
selected = sigs_sorted[:6]
selected += [s for s in sigs_sorted[6:] if s['est_bits'] <= 249][:10]
m = len(selected)  # 16 signatures

Step 3: Build and solve HNP lattice via CVP

The lattice construction uses column scaling to normalize expected magnitudes:

 python read-only • copy allowed Copy
# Compute HNP parameters
ts, us, Bs = [], [], []
for s in selected:
    s_inv = pow(s['s'], -1, n)
    ts.append((s_inv * s['r']) % n)
    us.append((-s_inv * s['h']) % n)
    Bs.append(2 ** s['est_bits'])

# Build CVP lattice with scaling
dim = m + 1
scales = [n // B for B in Bs] + [1]

M = IntegerMatrix(dim, dim)
for i in range(m):
    M[i, i] = n * scales[i]
for i in range(m):
    M[m, i] = int(ts[i]) * scales[i]
M[m, m] = 1

target = [int(us[i]) * scales[i] for i in range(m)] + [0]

# LLL reduction + CVP
LLL.reduction(M)
gs = MatGSO(M)
gs.update_gso()
closest = CVP.closest_vector(M, target)

# Extract private key
d = abs(closest[-1]) % n
print(f"d = {hex(d)}")
# d = 0x58286af25b10220cf0f979081becc352de791dabdf90205b84a92537e18a78d1

Step 4: Verify the key

The recovered key was verified by:

1. Checking d * G = Q (public key matches)
2. Verifying all 1600 signatures: r_i = (k_i * G).x mod n where k_i = s_i^{-1} * (h_i + d * r_i) mod n
3. Confirming nonce bit-lengths match timing estimates

Step 5: Decrypt the flag

The encryption uses a custom SHA256-CTR stream cipher — not standard AES-CTR:

1. base_key = SHA256(d.to_bytes(32, 'big'))
2. keystream_block[i] = SHA256(base_key || i.to_bytes(4, 'big'))
3. plaintext = ciphertext XOR keystream[:35]

 python read-only • copy allowed Copy
ct = bytes.fromhex('dd2cd0de3cd889b3f09660cd3170ec4b05d6d3831f5edb423f4202b03a05482c73de60')
base_key = sha256(d.to_bytes(32, 'big')).digest()

keystream = b''
for ctr in range(10):
    keystream += sha256(base_key + ctr.to_bytes(4, 'big')).digest()

flag = bytes(a ^ b for a, b in zip(ct, keystream[:len(ct)])).decode()
print(flag)  # tjctf{REDACTED}

Full solve script

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""Minerva's Stopwatch — TJCTF 2026: ECDSA timing side-channel + HNP lattice attack"""

import csv
from hashlib import sha256
from fpylll import IntegerMatrix, LLL, CVP
from fpylll.fplll.gso import MatGSO

# P-256 curve order
n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551

# Parse signatures
sigs = []
with open('trace.csv') as f:
    for row in csv.DictReader(f):
        sigs.append({
            'h': int(row['h'], 16),
            'r': int(row['r'], 16),
            's': int(row['s'], 16),
            'elapsed_ns': int(row['elapsed_ns'])
        })

# Timing model calibration
center_256, per_bit = 197530, 265
for s in sigs:
    bits = round(256 - (center_256 - s['elapsed_ns']) / per_bit)
    s['est_bits'] = max(1, min(256, bits))

# Select signatures with most leakage
sigs_sorted = sorted(sigs, key=lambda x: x['est_bits'])
selected = sigs_sorted[:6]  # 6 extreme outliers
selected += [s for s in sigs_sorted[6:] if s['est_bits'] <= 249][:10]
m = len(selected)

# Build HNP parameters
ts, us, Bs = [], [], []
for s in selected:
    s_inv = pow(s['s'], -1, n)
    ts.append((s_inv * s['r']) % n)
    us.append((-s_inv * s['h']) % n)
    Bs.append(2 ** s['est_bits'])

# CVP lattice with column scaling
dim = m + 1
scales = [n // B for B in Bs] + [1]
M = IntegerMatrix(dim, dim)
for i in range(m):
    M[i, i] = n * scales[i]
for i in range(m):
    M[m, i] = int(ts[i]) * scales[i]
M[m, m] = 1

target = [int(us[i]) * scales[i] for i in range(m)] + [0]

LLL.reduction(M)
gs = MatGSO(M)
gs.update_gso()
closest = CVP.closest_vector(M, target)
d = abs(closest[-1]) % n

# Decrypt flag with SHA256-CTR
ct = bytes.fromhex('dd2cd0de3cd889b3f09660cd3170ec4b05d6d3831f5edb423f4202b03a05482c73de60')
base_key = sha256(d.to_bytes(32, 'big')).digest()
keystream = b''
for ctr in range(10):
    keystream += sha256(base_key + ctr.to_bytes(4, 'big')).digest()
flag = bytes(a ^ b for a, b in zip(ct, keystream[:len(ct)])).decode()
print(flag)  # tjctf{REDACTED}