DSA Again?
Challenge Description
Two field reports were signed with the agency DSA key. Something is wrong with the signatures. Find it. Forge a valid signature over the target message to obtain authorization.
Connecting to the server gives us everything we need:
nc dsa.strayerraptors.com 30000
+--------------------------------------------------------+
| DEADROP AUTHORIZATION SERVER - HANDLER KOVACS KEYRING |
+--------------------------------------------------------+
DSA PARAMETERS
p = 0xa0da07e1aeaf2731d9ffa9d8c72f595ee15ed0a5bb0efcb5ef3d5a87cde21e57a2ae6e05e515a7fd5a5d9c9090d584bba1162655494af0db58cd8a34c1e864dbf19c04b30b2dc1d222a8a48e78e446777ac219f7a84d334b25304c7dac4498ea469a47b8cfcdcf0b210cd9bd494d9594888e31d06f225a6cba33e4a77124e22b
q = 0xab0573fff4fcadffa9583688b2d8ba75433c1227
g = 0x105829953c811f66293c16cfb186542af2c2769b5cc5f6e50e4a37e3b5d55bd39044171785050d5c75b0b47a7246a899b862bf0fa2d0edf36ebf2f79e768f7cbe94304501fed5be298f075cbfc3f552a0376504bd1973b5db77cde619d9e7ac06ca9778b835f56c3129b639b738dbb79ac779f5448681d8ace34fdb9719c48e
PUBLIC KEY
y = 0x53f75a97a45e04179bea8845d730b7e2f2896ff159a8fe24e7698e8eee170b68c8738dae3cf0744d9efbf4576b404ee56fabf3dc03d1f4d1f2abb417a04f15356ba1ac1c92d15463b79049ab1baaa976dcf15179dca285593c24c5b65887abf89065fef6b9f0f154baca3be2b393412bbf71c0377bc6fcafafec8fdcdec62a03
SIGNED MESSAGES
[1] message : HANDLER KOVACS: asset NIGHTINGALE confirms extraction window
r : 0x382a69ace839bb3d41b077df8ca9ed5be9164e9b
s : 0x31ca564ec3e2bc49212805479b67826f4e630327
[2] message : HANDLER KOVACS: request authorisation for protocol seven activation
r : 0x382a69ace839bb3d41b077df8ca9ed5be9164e9b
s : 0xc7214970e643c073a0e7bd868c642e4b1120d59
TARGET MESSAGE
APPROVE: alien_intern_permanent_residency
> Enter r,s (hex, comma-separated):
Spotting the Vulnerability
The first thing to check with any pair of DSA signatures is whether r1 == r2. In DSA:
r = (g^k mod p) mod q
r is derived entirely from the nonce k. If two signatures share the same r, they used the same k. That's the vulnerability here and it's immediately visible, no tooling needed.
Background: DSA Signing
For a message m with private key x and nonce k:
r = (g^k mod p) mod q
s = k^-1 * (H(m) + x*r) mod q
The security of DSA depends entirely on k being unique per signature. If k is reused across two signatures, both r values are identical and the private key becomes recoverable with simple algebra.
Stage 1: Recover the Nonce k
Given two signatures (r, s1) and (r, s2) over messages m1 and m2:
s1 = k^-1 * (H(m1) + x*r) mod q
s2 = k^-1 * (H(m2) + x*r) mod q
Subtract:
s1 - s2 = [k^-1 * (H(m1) + x*r)] - [k^-1 * (H(m2) + x*r)] mod q
s1 - s2 = k^-1 * [(H(m1) + x*r) - (H(m2) + x*r)] mod q
s1 - s2 = k^-1 * [H(m1) + x*r - H(m2) - x*r] mod q
s1 - s2 = k^-1 * (H(m1) - H(m2)) mod q
Solve for k:
k * (s1 - s2) = H(m1) - H(m2) mod q
k = (H(m1) - H(m2)) * (s1 - s2)^-1 mod q
Stage 2: Recover the Private Key x
With k in hand, rearrange the signing equation:
s1 = k^-1 * (H(m1) + x*r) mod q
s1 * k = H(m1) + x*r mod q
s1*k - H(m1) = x*r mod q
x = r^-1 * (s1*k - H(m1)) mod q
Verify by checking g^x mod p == y.
Stage 3: Forge the Signature
With x recovered, sign the target using a fresh random nonce k_f:
r_f = (g^k_f mod p) mod q
s_f = k_f^-1 * (H(target) + x * r_f) mod q
Full Solve Script
import hashlib, secrets
# Parameters copied from the server banner
p = 0xa0da07e1aeaf2731d9ffa9d8c72f595ee15ed0a5bb0efcb5ef3d5a87cde21e57a2ae6e05e515a7fd5a5d9c9090d584bba1162655494af0db58cd8a34c1e864dbf19c04b30b2dc1d222a8a48e78e446777ac219f7a84d334b25304c7dac4498ea469a47b8cfcdcf0b210cd9bd494d9594888e31d06f225a6cba33e4a77124e22b
q = 0xab0573fff4fcadffa9583688b2d8ba75433c1227
g = 0x105829953c811f66293c16cfb186542af2c2769b5cc5f6e50e4a37e3b5d55bd39044171785050d5c75b0b47a7246a899b862bf0fa2d0edf36ebf2f79e768f7cbe94304501fed5be298f075cbfc3f552a0376504bd1973b5db77cde619d9e7ac06ca9778b835f56c3129b639b738dbb79ac779f5448681d8ace34fdb9719c48e
y = 0x53f75a97a45e04179bea8845d730b7e2f2896ff159a8fe24e7698e8eee170b68c8738dae3cf0744d9efbf4576b404ee56fabf3dc03d1f4d1f2abb417a04f15356ba1ac1c92d15463b79049ab1baaa976dcf15179dca285593c24c5b65887abf89065fef6b9f0f154baca3be2b393412bbf71c0377bc6fcafafec8fdcdec62a03
msg1 = b'HANDLER KOVACS: asset NIGHTINGALE confirms extraction window'
msg2 = b'HANDLER KOVACS: request authorisation for protocol seven activation'
r = 0x382a69ace839bb3d41b077df8ca9ed5be9164e9b
s1 = 0x31ca564ec3e2bc49212805479b67826f4e630327
s2 = 0xc7214970e643c073a0e7bd868c642e4b1120d59
target = b'APPROVE: alien_intern_permanent_residency'
def H(msg): return int(hashlib.sha1(msg).hexdigest(), 16)
# Stage 1: recover k
k = ((H(msg1) - H(msg2)) * pow(s1 - s2, -1, q)) % q
# Stage 2: recover private key x
x = (pow(r, -1, q) * (s1 * k - H(msg1))) % q
assert pow(g, x, p) == y, 'Key recovery failed'
print(f'Private key recovered: {hex(x)[:20]}...')
# Stage 3: forge signature over target
k_f = secrets.randbelow(q - 2) + 2
r_f = pow(g, k_f, p) % q
s_f = (pow(k_f, -1, q) * (H(target) + x * r_f)) % q
print(f'r = {hex(r_f)}')
print(f's = {hex(s_f)}')
Submit at the server prompt:
> Enter r,s (hex, comma-separated): 0x8d1b17b512237acb97f1669601af98bec522854c, 0x4586fc5246cf7ab430917c99e7153d26049492aa
[+] Signature valid. Authorization granted.
[+] FLAG: DEADROP{nonce_reuse_ends_careers_and_agencies}
Key Takeaways
1. Nonce reuse in DSA is catastrophic. Unlike RSA where encrypting the same message twice is merely inadvisable, DSA's security model makes every k a one-time secret. Reusing k even once leaks the private key completely, every past and future signature made with that key is compromised.
2. Identical r values are a direct signal. You don't need sophisticated analysis to spot this. Auditing a set of signatures for duplicate r values is a standard first check when investigating a potentially compromised signing key.
3. This has happened in the real world. Sony's PS3 signing key was recovered this way in 2010. They used a static k for every firmware signature, allowing researchers to sign arbitrary code. The same attack has broken numerous Bitcoin wallet implementations that used weak or reused nonces, leading to real fund theft. ECDSA has the identical vulnerability.
4. The fix is RFC 6979. RFC 6979 defines deterministic nonce generation: k is derived as HMAC-DRBG(private_key || H(message)), making it unique per message without relying on a CSPRNG at signing time. It also makes signing reproducible, which is useful for testing. Any serious DSA/ECDSA implementation should use it.
Flag
DEADROP{nonce_reuse_ends_careers_and_agencies}