Signature Residue

Challenge Description

During incident response, one exhausted engineer attempted to authenticate an emergency override using an old DSA-based control channel. In their rush, they left behind everything needed to reconstruct the signed message. Recover the original message. Understand the DSA failure.

Flag: Raptor{99fe202b410a018710cf61a0a8a5edad424b22d01633614a7b8681ee83e27ae6}

First Look

Hex-decoding msg:

6c6f77206e6f6e6365206d616b65732063727970746f20736164
→ "low nonce makes crypto sad"

The challenge is telling us exactly what went wrong. This is a low-nonce DSA attack, the signing nonce k was chosen poorly, and that breaks the entire scheme.

DSA Background

DSA signatures are generated using a secret per-message random value k. The signature pair (r, s) is computed as:

r = (g^k mod p) mod q
s = k^-1 * (H(m) + x*r) mod q

Where x is the private key. The security of DSA depends entirely on k being: - Random - Secret - Never reused

If k is small enough to brute force, a "low nonce", then r = (g^k mod p) mod q can be verified for each candidate k until it matches the given r. Once k is known, x (the private key) falls out directly from the signature equation:

x = (k*s - H(m)) * r^-1 mod q

The decoded message is practically shouting the attack vector. No online tools handle this directly, it requires understanding the math.

The Script

import hashlib

msg_hex = "6c6f77206e6f6e6365206d616b65732063727970746f20736164"
msg_bytes = bytes.fromhex(msg_hex)
print(f"Message: {msg_bytes.decode('ascii')}")

p = 97835664342822650315177183116974511961356680049481229900115415178519596032221442792896010014703445466762250151733873504769960438213533052138118198129962375492312569190187637022706091540002808406177516290947322258970330852877333095787544666234014800980859558177830444536925402345233139053871653439897552374419
q = 20479547956469907937000912164224697845249772908382024201697508481637
g = 73136435645720186066514156368162273900833384759798337779279592382311267572699038720498153736316799905928813740497337787054323708303310836208212059046854149275011090355506013951134010207160051970531853410942353772652332570547399773118270222868067379951320226436094066462078233244078070809550883036648224602621
r = 5316204873327104780416828622624588698988047246348735234194634614913
s = 13607687636978805094901549341517080728988536296754389042212260887364

# Step 1: Brute force k
# If k is small, g^k mod p mod q will equal r at the correct value
print("Brute forcing k...")
k = None
for candidate in range(1, 100000):
    if pow(g, candidate, p) % q == r:
        k = candidate
        print(f"Found k = {k}")
        break

# Step 2: Hash the message (DSA uses SHA-256 here)
h = int(hashlib.sha256(bytes.fromhex(msg_hex)).hexdigest(), 16)

# Step 3: Recover the private key x
# Rearranging s = k^-1 * (H(m) + x*r) mod q:
# x = (k*s - H(m)) * r^-1 mod q
r_inv = pow(r, -1, q)          # Modular inverse of r mod q
x = ((k * s - h) * r_inv) % q
print(f"Private key x = {x}")

# Step 4: Derive the flag
flag = hashlib.sha256(str(x).encode()).hexdigest()
print(f"Flag: Raptor{{{flag}}}")

Step by step:

1. Brute force k. Since r = (g^k mod p) mod q, we iterate candidate values of k and compute both sides until they match. A properly chosen k would be a random 160-bit number, completely impossible to brute force. Here it's small enough to land within 100,000 iterations.

2. Hash the message. DSA signs the hash of the message, not the message directly. H(m) uses SHA-256 on the raw message bytes.

3. Recover x. With k known, the signature equation s = k^-1 * (H(m) + x*r) mod q has only one unknown. Solving for x: multiply both sides by k, subtract H(m), multiply by r^-1 mod q. Python's pow(r, -1, q) computes the modular inverse directly.

4. Derive the flag. The challenge notes say to SHA-256 the private key x as a string and wrap it in the flag format.

Why Low Nonce Is Catastrophic

DSA's security proof assumes k is drawn from the full range [1, q-1] uniformly at random. The moment k is predictable or small, the private key x, which should be permanently secret, is directly computable from public values and the signature alone.

This isn't a theoretical concern. Real-world DSA key recovery from weak nonces has been demonstrated against Sony's PlayStation 3 (which used a constant k for all signatures) and various TLS implementations. The ECDSA variant of this attack against Bitcoin signing has led to real wallet compromises.

The decoded message said it plainly: "low nonce makes crypto sad."

Key Takeaways

DSA and ECDSA are exceptionally sensitive to nonce quality. The nonce k must be cryptographically random and unique per signature. Using a deterministic but secure nonce derivation (RFC 6979) is the modern best practice as it eliminates the randomness requirement while remaining provably secure.

For CTF purposes: when you see DSA with parameters given and a hint about weak randomness, the low-nonce brute force is the standard attack. The range to check is usually small (under a few hundred thousand), and the private key recovery formula is mechanical once k is found.