Writeup loaded.
Hakari Domain
challenge brief
target profile, scoring, and execution stack
verified solve
target
chall.py, nc 34.126.187.50 5500category
Crypto
points
500
difficulty
Medium-Hard
flag format
hack10{flag_here}tools used
Python 3pwntoolsgmpy2Mersenne Twister state recoveryHåstad's Broadcast Attack
final flag
hack10{ab3a61603241b0638804acdc5f905cd4}
reveal and copy from section 5
1. Challenge Overview
The challenge presents a "guessing game" where players must predict random 32-bit numbers generated by Python's random.getrandbits(32). The objective is to:
Guess 3 consecutive numbers correctly to unlock "jackpot mode"
In jackpot mode, each correct guess yields an RSA encryption sample of the flag
Collect enough RSA samples to recover the plaintext flag
The RSA parameters use e=17, which hints at Håstad's Broadcast Attack when we can collect 17+ ciphertexts of the same message encrypted with different moduli.
2. Initial Reconnaissance
Examining the Challenge File
bash1 lines
1$ cat chall.pypython23 lines
1import os2import random3import sys4from Crypto.Util.number import bytes_to_long, getPrime5E = 176JACKPOT_STREAK = 37MAX_ATTEMPTS = 7008def load_flag() -> bytes:9 return os.getenv("FLAG", "hack10{REDACTED}").encode()10def gen_rsa_sample(message: int, used_primes: set[int]) -> tuple[int, int, int]:11 while True:12 p = getPrime(512)13 q = getPrime(512)14 if p == q or p in used_primes or q in used_primes:15 continue16 if (p - 1) % E == 0 or (q - 1) % E == 0:17 continue18 n = p * q19 if message >= n:20 continue21 used_primes.add(p)22 used_primes.add(q)23 return n, E, pow(message, E, n)Connecting to the Service
bash1 lines
1$ echo -e "0\\n1\\n2" | timeout 5 nc 34.126.187.50 5500text10 lines
1Welcome to Hakari Domain.2Guess the next number in [0, 4294967295].3Reach 3 correct guesses in a row to hit jackpot.4You have 700 total attempts before the connection closes.5Guess the next number: Wrong. The number was 4172439361.6Attempts used: 1/7007Guess the next number: Wrong. The number was 3784687112.8Attempts used: 2/7009Guess the next number: Wrong. The number was 3761758796.10Attempts used: 3/7003. Analysis / Forensics Path
Key Observations
PRNG Vulnerability: The server uses Python's random.getrandbits(32) which is based on the Mersenne Twister (MT19937) PRNG.
Information Leak: When a guess is wrong, the server reveals the actual random number: "Wrong. The number was {target}."
MT19937 State Recovery: The Mersenne Twister has a 624 × 32-bit internal state. After observing 624 consecutive outputs, we can completely reconstruct the internal state using the "untemper" operation (reversing the tempering transformation).
RSA Broadcast Attack Setup: With e=17, if we can collect 17+ RSA samples (same message, different moduli), we can use the Chinese Remainder Theorem (CRT) to reconstruct m^17, then take the 17th integer root to recover the plaintext.
Attack Chain
text3 lines
1[Leak 624 MT outputs] → [Reconstruct MT state] → [Predict numbers] 23 → [Hit jackpot] → [Collect 17 RSA samples] → [Håstad's Broadcast Attack] → [FLAG]MT19937 Untemper Function
The tempering transformation in MT19937:
text4 lines
1y ^= y >> 112y ^= (y << 7) \& 0x9d2c56803y ^= (y << 15) \& 0xefc600004y ^= y >> 18Can be reversed with:
python8 lines
1def untemper(y):2 y ^= y >> 183 y ^= (y << 15) \& 0xefc600004 for _ in range(7):5 y ^= (y << 7) \& 0x9d2c56806 y ^= y >> 117 y ^= y >> 228 return y4. Exploitation / Recovery
Full Solver Script
python150 lines
1#!/usr/bin/env python32"""3Hakari Domain CTF Challenge Solver4===================================51. Collect 624 MT outputs (leaked via "Wrong. The number was X")62. Reconstruct MT state via untemper73. Predict next numbers to hit jackpot and collect RSA samples84. Håstad's Broadcast Attack with e=17 RSA samples9"""10from pwn import *11import random12import gmpy213# Challenge parameters14HOST = "34.126.187.50"15PORT = 550016E = 1717JACKPOT_STREAK = 318MAX_ATTEMPTS = 70019def untemper(y):20 """Reverse the MT19937 tempering transformation"""21 y ^= y >> 1822 y ^= (y << 15) \& 0xefc6000023 for _ in range(7):24 y ^= (y << 7) \& 0x9d2c568025 y ^= y >> 1126 y ^= y >> 2227 return y28def hastad_broadcast(ciphertexts, moduli, e):29 """Recover m from e encryptions with exponent e using CRT"""30 assert len(ciphertexts) >= e and len(moduli) >= e31 # Chinese Remainder Theorem32 def crt(remainders, moduli):33 from functools import reduce34 N = reduce(lambda a, b: a * b, moduli)35 result = 036 for r, m in zip(remainders, moduli):37 Ni = N // m38 Mi = pow(Ni, -1, m)39 result += r * Ni * Mi40 return result % N41 # CRT gives m^e (no modular reduction since m < each n_i)42 me = crt(ciphertexts[:e], moduli[:e])43 m, exact = gmpy2.iroot(me, e)44 if exact:45 return int(m)46 return None47def solve():48 log.info("Connecting to challenge server...")49 r = remote(HOST, PORT)50 # Read banner51 for _ in range(5):52 print(r.recvline().decode().strip())53 # Phase 1: Collect 624 MT outputs54 outputs = []55 log.info("Phase 1: Collecting 624 MT outputs...")56 for i in range(624):57 r.sendlineafter(b"Guess the next number: ", b"0")58 resp = r.recvline().decode().strip()59 if "Wrong. The number was" in resp:60 # Extract the leaked number61 num = int(resp.split("was ")[1].rstrip("."))62 outputs.append(num)63 if (i + 1) % 100 == 0:64 log.info(f"Collected {i+1}/624 outputs")65 else:66 log.error(f"Unexpected response: {resp}")67 return68 # Read the "Attempts used" line69 r.recvline()70 log.success(f"Collected {len(outputs)} MT outputs")71 # Phase 2: Reconstruct MT state72 log.info("Phase 2: Reconstructing MT state...")73 state = [untemper(output) for output in outputs]74 # Recreate the random state75 random.setstate((3, tuple(state + [624]), None))76 log.success("MT state reconstructed!")77 # Phase 3: Predict numbers to hit jackpot78 log.info("Phase 3: Hitting jackpot (need 3 consecutive correct guesses)...")79 streak = 080 jackpot = False81 samples_n = []82 samples_c = []83 while not jackpot:84 predicted = random.getrandbits(32)85 r.sendlineafter(b"Guess the next number: ", str(predicted).encode())86 resp = r.recvline().decode().strip()87 if "Correct" in resp:88 streak += 189 log.info(f"Correct! Streak: {streak}")90 if "Jackpot unlocked" in resp or streak >= JACKPOT_STREAK:91 # Check for jackpot message92 while True:93 line = r.recvline().decode().strip()94 print(line)95 if "Jackpot unlocked" in line:96 jackpot = True97 break98 if "Predict" in line or "Guess" in line:99 break100 else:101 log.error(f"Prediction failed! Response: {resp}")102 return103 log.success("Jackpot unlocked!")104 # Phase 4: Collect RSA samples105 log.info(f"Phase 4: Collecting {E} RSA samples...")106 while len(samples_n) < E:107 predicted = random.getrandbits(32)108 r.sendlineafter(b"Predict the next number or type 'exit': ", str(predicted).encode())109 resp = r.recvline().decode().strip()110 if "Correct" in resp:111 log.info(resp)112 # Read sample info113 sample_line = r.recvline().decode().strip()114 log.info(sample_line)115 n_line = r.recvline().decode().strip()116 n = int(n_line.split(" = ")[1])117 e_line = r.recvline().decode().strip()118 c_line = r.recvline().decode().strip()119 c = int(c_line.split(" = ")[1])120 samples_n.append(n)121 samples_c.append(c)122 log.success(f"Sample {len(samples_n)}/{E} collected")123 else:124 log.error(f"Prediction failed during sample collection: {resp}")125 return126 r.sendlineafter(b"Predict the next number or type 'exit': ", b"exit")127 r.close()128 log.success(f"Collected {len(samples_n)} RSA samples!")129 # Phase 5: Håstad's Broadcast Attack130 log.info("Phase 5: Running Håstad's Broadcast Attack...")131 m = hastad_broadcast(samples_c, samples_n, E)132 if m:133 try:134 flag = bytes.fromhex(hex(m)[2:]).decode()135 log.success(f"FLAG: {flag}")136 return flag137 except:138 # Try with leading zeros139 flag_hex = hex(m)[2:]140 if len(flag_hex) % 2 == 1:141 flag_hex = "0" + flag_hex142 flag = bytes.fromhex(flag_hex).decode()143 log.success(f"FLAG: {flag}")144 return flag145 else:146 log.error("Håstad's attack failed to recover the message")147 return None148if __name__ == "__main__":149 context.log_level = "info"150 solve()Execution Output
bash1 lines
1$ python3 solve.pytext34 lines
1[*] Connecting to challenge server...2[+] Opening connection to 34.126.187.50 on port 5500: Done3Welcome to Hakari Domain.4Guess the next number in [0, 4294967295].5Reach 3 correct guesses in a row to hit jackpot.6You have 700 total attempts before the connection closes.7[*] Phase 1: Collecting 624 MT outputs...8[*] Collected 100/624 outputs9[*] Collected 200/624 outputs10[*] Collected 300/624 outputs11[*] Collected 400/624 outputs12[*] Collected 500/624 outputs13[*] Collected 600/624 outputs14[+] Collected 624 MT outputs15[*] Phase 2: Reconstructing MT state...16[+] MT state reconstructed!17[*] Phase 3: Hitting jackpot (need 3 consecutive correct guesses)...18[*] Correct! Streak: 119[*] Correct! Streak: 220[*] Correct! Streak: 321Jackpot unlocked.22[+] Jackpot unlocked!23[*] Phase 4: Collecting 17 RSA samples...24[*] Correct. Current streak: 425[*] Sample 126[+] Sample 1/17 collected27... (samples 2-16) ...28[*] Correct. Current streak: 2029[*] Sample 1730[+] Sample 17/17 collected31[*] Closed connection to 34.126.187.50 port 550032[+] Collected 17 RSA samples!33[*] Phase 5: Running Håstad's Broadcast Attack...34[+] FLAG: hack10{ab3a61603241b0638804acdc5f905cd4}5. Flag
captured flag
hack10{ab3a61603241b0638804acdc5f905cd4}
6. Summary of Approach & Key Takeaways
Step-by-Step Recap
Analyzed the challenge code - Identified use of Python's random.getrandbits(32) (MT19937) and RSA with e=17
Connected to the service - Discovered the server leaks actual random values on wrong guesses
Collected 624 MT outputs - Made intentional wrong guesses to harvest PRNG outputs
Reconstructed MT state - Used the untemper function to reverse tempering and restore the full 624-word state
Predicted future values - Used random.setstate() to synchronize our local PRNG with the server's
Hit jackpot - Correctly guessed 3 consecutive numbers to unlock RSA sample mode
Collected 17 RSA samples - Continued predicting to gather (n, c) pairs
Applied Håstad's Broadcast Attack - Used CRT to combine 17 ciphertexts and took the 17th root to recover the plaintext