> For the complete documentation index, see [llms.txt](https://zwique.gitbook.io/zwique_notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zwique.gitbook.io/zwique_notes/writeups/random-ctf-writeup/local/verification-revolutions.md). # Verification: Revolutions {% embed url="" %} ```python # challenge.py import os from random import choice from hashlib import md5 from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b flag = os.environ.get('flag', 'MUSTCTF{fake_flag_for_testing}') padding = os.urandom(100) rounds = 25 # brute force IMPOSSIBLE def sign(i, letter): letter = bytes([letter]) signature = md5(letter + padding + padding[:i]).digest() signature = b2l(signature) * (256 ** 21) signature ^= b2l(flag.encode()) return l2b(signature) def verify(i, letter, signature): return sign(i, letter) == signature while True: option = input('option = ') if option == 'sign': for i in range(rounds): letter = choice(b'MUSTCTF') print(f'Round {i+1}. {sign(i, letter).hex()}') elif option == 'verify': correct = 0 for i in range(rounds): print(f'Round {i+1}') signature = bytes.fromhex(input('signature = ')) letter = input('letter = ').encode()[0] if verify(i, letter, signature): correct += 1 if correct == rounds: print('Verified. Flag:', flag) else: print('Verification failed.') else: print('Must be one of: sign, verify') ``` ### Challenge Overview The challenge gives us two options: ``` sign verify ``` * The `sign` option prints 25 signatures. * The `verify` option asks us to provide 25 valid signatures and letters. * If all 25 are correct, the server prints the flag. * The goal is not to recover the secret padding. * The goal is to forge valid signatures for all 25 rounds. ### Important Code ``` padding = os.urandom(100) rounds = 25 ``` The padding is random and secret. There are 25 rounds. ``` def sign(i, letter): letter = bytes([letter]) signature = md5(letter + padding + padding[:i]).digest() signature = b2l(signature) * (256 ** 21) signature ^= b2l(flag.encode()) return l2b(signature) ``` The signature depends on: ``` letter padding round index i flag ``` The server lets us call `sign`. But it does not let us choose the letter. Instead, the server chooses a random letter: ``` letter = choice(b'MUSTCTF') ``` This is the most important bug. ### The Bug The string is: ``` b'MUSTCTF' ``` These are the possible bytes: ``` M U S T C T F ``` The letter `T` appears twice. So the probability is not uniform over unique letters. The probabilities are: ``` M = 1/7 U = 1/7 S = 1/7 T = 2/7 C = 1/7 F = 1/7 ``` This means `T` is chosen twice as often as every other letter. This is the full vulnerability. ### Why Repeated Signing Helps For a fixed round `i`, the function is deterministic. That means: ``` sign(i, b'T') ``` always gives the same signature on the same server connection. The secret `padding` does not change during the process. The flag also does not change. So for each round, every letter has one fixed signature. Example for one round: ``` M -> signature A U -> signature B S -> signature C T -> signature D C -> signature E F -> signature F ``` But `T` appears twice in the random choice list. So after many calls to `sign`, the signature for `T` appears most often. We do not need to know the letter directly. We only count signatures. The most common signature is probably the signature for `T`. ### Attack Idea Call the `sign` option many times. Each call gives 25 signatures. For every round, count how many times each signature appears. After enough samples: ``` the most frequent signature for round 1 = sign(0, 'T') the most frequent signature for round 2 = sign(1, 'T') ... the most frequent signature for round 25 = sign(24, 'T') ``` Then call `verify`. For every round, submit: ``` signature = most frequent signature for that round letter = T ``` The server checks: ``` verify(i, letter, signature) ``` which means: ``` sign(i, letter) == signature ``` Since we submit the signature for `T`, and the letter `T`, the check passes. ### Why We Do Not Need to Break MD5 At first, the challenge looks like a hash problem. But we never need to invert MD5. We never need to recover `padding`. We never need to recover `flag` from XOR. The server itself leaks valid signatures. The only problem is that it hides which letter was used. But the biased random choice leaks that information statistically. So this is not an MD5 attack. It is a randomness / probability bug. ### Why Brute Force Is Not Needed The code says: ``` rounds = 25 # brute force IMPOSSIBLE ``` Brute forcing all letters would mean guessing one valid letter per round. There are 6 unique letters: ``` M U S T C F ``` So blind guessing would be about: ``` 1 / 6^25 ``` That is impossible. But we do not guess blindly. We collect many signatures. Then we identify the `T` signature by frequency. So the attack is reliable. ### Exploit Script ```python #!/usr/bin/env python3 import socket import re from collections import Counter HOST = "139.162.5.230" PORT = 10173 ROUNDS = 25 SAMPLES = 500 # increase to 1000+ if unlucky def recv_until(sock, token: bytes) -> bytes: data = b"" while token not in data: chunk = sock.recv(4096) if not chunk: raise EOFError("connection closed") data += chunk return data def main(): s = socket.create_connection((HOST, PORT)) recv_until(s, b"option = ") counts = [Counter() for _ in range(ROUNDS)] for q in range(SAMPLES): s.sendall(b"sign\n") out = recv_until(s, b"option = ").decode(errors="replace") for m in re.finditer(r"Round (\d+)\. ([0-9a-f]+)", out): idx = int(m.group(1)) - 1 sig = m.group(2) counts[idx][sig] += 1 if (q + 1) % 100 == 0: print(f"[+] collected {q + 1} sign batches") t_sigs = [] for i, c in enumerate(counts): sig, freq = c.most_common(1)[0] t_sigs.append(sig) print(f"round {i+1:02d}: guessed T sig freq={freq}/{SAMPLES} sig={sig}") # Submit verify using letter T for every round. s.sendall(b"verify\n") result = b"" for i, sig in enumerate(t_sigs): result += recv_until(s, b"signature = ") s.sendall(sig.encode() + b"\n") result += recv_until(s, b"letter = ") s.sendall(b"T\n") result += s.recv(4096) print(result.decode(errors="replace")) if __name__ == "__main__": main() ``` ### Exploit Explanation First we create one counter per round: ``` counts = [Counter() for _ in range(ROUNDS)] ``` Then we call `sign` many times. Each response contains 25 signatures. We parse the round number and the signature: ``` matches = re.findall(r"Round (\d+)\. ([0-9a-f]+)", out) ``` Then we count signatures by round: ``` counts[idx][sig] += 1 ``` After collecting enough samples, we take the most common signature for each round: ``` sig, freq = counts[i].most_common(1)[0] ``` This is assumed to be the signature for `T`. Finally, we send those signatures to `verify` with letter `T`. ``` s.sendall(sig.encode() + b"\n") s.sendall(b"T\n") ``` If all 25 signatures are correct, the server prints the flag. ### Why 500 Samples Are Enough For each round, `T` appears with probability: ``` 2/7 ≈ 28.57% ``` Each other letter appears with probability: ``` 1/7 ≈ 14.28% ``` So after 500 samples, the expected counts are: ``` T: about 143 times Other letters: about 71 times each ``` That gap is large. So the most frequent signature is very likely to be the `T` signature. If the exploit fails due to bad luck, increase: ``` SAMPLES = 1000 ``` ### Summary The challenge is broken because the random letter selection is biased. The signer chooses from: ``` b'MUSTCTF' ``` The letter `T` appears twice. Therefore, the signature for `T` appears more often than every other signature. By collecting many signatures and counting frequencies, we recover: ``` sign(i, 'T') ``` for every round. Then we submit those signatures with letter `T`. This passes verification and reveals the flag. The attack does not break MD5. It abuses biased randomness and deterministic signatures. --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://zwique.gitbook.io/zwique_notes/writeups/random-ctf-writeup/local/verification-revolutions.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.