WOTS Up
WOTS Up
Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: forward_only_hash_advance, private_key_chain_linkage, signature_to_aes_key, wots_forgery
Summary
Task: forge a Winternitz one-time signature (WOTS) for b'Sign for flag' given only one published signature for a different message, then use the forged signature's first bytes as an AES-CBC key to decrypt the flag. Solution: WOTS chains are one-way (hash forward only), so a second signature is normally impossible where target digest bytes are smaller; but this keygen LINKS the 32 private keys into a single hash chain (priv_key[i+1]=hash(priv_key[i])), so a known later signature element reveals earlier private values. For each index, find a known sig1[j] (j>=i) whose chain level relative to priv_key[i] is <= the needed target level, then hash it forward to reach the required position; the forged first bytes give the AES key.
WOTS Up — cryptohack (Hashes)
Description
Winternitz One-Time Signature (WOTS) over KEY_LEN = 32 independent hash chains, each of length 256
(BYTE_MAX = 255), with H = sha256:
python read-only • copy allowedclass Winternitz: def __init__(self, priv_seed=urandom(32)): self.priv_key = [] for _ in range(32): priv_seed = self.hash(priv_seed) # <-- LINKED: priv_key[i+1] = H(priv_key[i]) self.priv_key.append(priv_seed) self.gen_pubkey() def gen_pubkey(self): self.pub_key = [H^256(priv_key[i]) for i in range(32)] # H once, then 255 more def sign(self, data): h = H(data) return [ H^(255 - h[i])(priv_key[i]) for i in range(32) ] # advance (255 - byte) steps def verify(self, signature, data): h = H(data) return pub_key == [ H^(h[i]+1)(signature[i]) for i in range(32) ]
We are given (src/wots_up_data.json): the public key, one signature for message1 = b"WOTS Up???", and an AES-CBC iv/enc of the flag. The flag's AES key is
bytes([s[0] for s in signature2]) where signature2 signs message2 = b"Sign for flag". So we
must forge the WOTS signature for message2.
Analysis
In a correct WOTS, each chain is independent and one-way: sig[i] = H^(255 - h[i])(priv_key[i])
sits at "level" a_i = 255 - h[i] above the private key. From a known signature you can only hash
forward (increase the level). To forge for message2 you would need, at every index i,
255 - h2[i] >= 255 - h1[i], i.e. h2[i] <= h1[i] — generally false for some indices, so one
signature should not let you forge another.
The vulnerability is in keygen: the 32 private keys are not independent — they form a single hash
chain, priv_key[i+1] = H(priv_key[i]). Equivalently, priv_key[i+k] is priv_key[i] advanced
k levels. Combined with a known sig1[j] = priv_key[j] advanced a1_j = 255 - h1[j] levels, we
get a value that, relative to priv_key[i] for any i <= j, sits at level
src_level(j, i) = (j - i) + a1_j = (j - i) + (255 - h1[j])
(hash priv_key[i] forward j-i times to reach priv_key[j], then a1_j more to reach sig1[j]).
The target we need is sig2[i] = priv_key[i] advanced target_i = 255 - h2[i] levels. Since hashing
is forward-only, we can reach it from any known sig1[j] (with j >= i) whose src_level(j,i) is
<= target_i, by hashing forward target_i - src_level(j,i) extra times. The private-key
linkage guarantees such a j exists for every index, so the whole signature2 is forgeable.
Solution
Forge per index, then decrypt (full solver solve_wots1.py):
python read-only • copy allowedimport hashlib, json from Crypto.Cipher import AES H = lambda d: hashlib.sha256(d).digest() KEY_LEN, BYTE_MAX = 32, 255 data = json.load(open("src/wots_up_data.json")) pub = [bytes.fromhex(x) for x in data["public_key"]] sig1 = [bytes.fromhex(x) for x in data["signature"]] iv, enc = bytes.fromhex(data["iv"]), bytes.fromhex(data["enc"]) h1 = H(b"WOTS Up???") h2 = H(b"Sign for flag") def advance(x, n): for _ in range(n): x = H(x) return x sig2 = [None]*KEY_LEN for i in range(KEY_LEN): target = BYTE_MAX - h2[i] # level relative to priv_key[i] for j in range(i, KEY_LEN): # exploit linkage: priv_key[j] derived from priv_key[i] a_j = BYTE_MAX - h1[j] src_level = (j - i) + a_j # level of sig1[j] relative to priv_key[i] if src_level <= target: # forward-reachable sig2[i] = advance(sig1[j], target - src_level) break assert sig2[i] is not None, f"index {i} not forgeable" # verify against published public key def verify(sig, h): return all(advance(sig[i], h[i] + 1) == pub[i] for i in range(KEY_LEN)) assert verify(sig2, h2) aes_key = bytes([s[0] for s in sig2]) print(AES.new(aes_key, AES.MODE_CBC, iv).decrypt(enc))
The forged signature2 verifies against the public key, and its first bytes form the AES-CBC key
that decrypts the flag.
Cross-reference: wots_up_2
The sibling challenge wots_up_2 (ECSC{0ne_m0r3_t1m3_s1gn4tur3_ff}) uses independent private
keys (no chain linkage), but leaks the OTS by publishing 20 sample signatures of different
messages. Per index i, pick any sample j with h_j[i] >= h2[i] (so its level
255 - h_j[i] <= 255 - h2[i]) and hash that sample's element forward to the target. With 20 samples,
for every byte index at least one sample byte is large enough, so the message is forgeable
(solve_wots2.py, src/wots_up_2_data.json).
Takeaways
Use this technique when:
- A WOTS / hash-based one-time signature reuses or leaks chain values: any known signature
element lets you hash forward to any equal-or-higher chain position, so you can forge a
message whose digest bytes are all
>=a known message's digest bytes at the reachable positions. - The keygen links the per-index private keys into one chain (
priv[i+1] = H(priv[i])) — a later index's signature reveals earlier private material, removing the per-index independence that makes WOTS one-time-secure. This single bug makes every index forgeable. - Multiple sample signatures are available (wots_up_2): take the per-index maximum digest byte across samples to always find a forward-reachable source.
- The forged signature feeds a downstream key (here
bytes([s[0] for s in sig])-> AES-CBC key) — forging the signature directly yields the decryption key.