# Writeup – RANDOM SEED RANDOM ## Author @m1kit ## Problem Statement (en) Randomly random is more random. --- med, 17 solves ## Extra Hints - <details>randomly random is not so random</details> - <details>find a seed with the least randomness</details> - <details>you can predict r(k) for all k</details> ## Step 1. Find a good seed There is a seed which makes `r(k)` taking only a few values. By applying Floyd's cycle detection algorithm to `[20231105, 20231105 * 10)`, you can find one of followings: ``` | seed | # of r(k) | # of r(k) % len(cs) | | 40538547 | 42 | 34 | | 37635707 | 182 | 81 | | 79190593 | 111 | 61 | | 169256700 | 12 | 11 | | 92574978 | 6 | 5 | | 151006513 | 6 | 6 | | 152413113 | 15 | 15 | | 66523739 | 3 | 3 | | 156920728 | 3 | 3 | ``` ## Step 2. Restore the flag We can restore the flag by making a few queries with the "good" seeds. ```python= import random import string import sys from pwn import * cs = string.printable[:-6] good_seeds = [66523739, 92574978, 151006513, 152413113, 169256700] expected_flag = 'TSGCTF{D4NCE_R0BOT_D4NCE_8caa8d05ff7f}' flag_len = len(expected_flag) def get_offsets(seed): random.seed(seed) x = None offsets = set() while x != seed: random.seed(x := random.randrange(20231104, 20231104 * 10)) offsets.add(x % len(cs)) return offsets def ask(seed, io_gen): io = io_gen() io.send(str(seed).encode() + b"\n") io.recvuntil(b'flag: ') resp = io.recvrepeat(0.05).decode('ascii').strip() io.shutdown() assert len(resp) == len(expected_flag) return resp def solve(io_gen): ans = [set(cs) for _ in range(flag_len)] for seed in good_seeds: offsets = get_offsets(seed) encrypted = ask(seed, io_gen) for i, c in enumerate(encrypted): ans[i] = ans[i] & set([cs[(cs.index(c) - off + len(cs)) % len(cs)] for off in offsets]) assert(all(len(a) == 1 for a in ans)) return ''.join([list(a)[0] for a in ans]) def solve_local(): os.chdir('./dist') env = {'FLAG': expected_flag} return solve(lambda: process(['python3', './main.py'], env=env)) def solve_remote(addr, port): return solve(lambda: remote(addr, port)) def main(): for seed in good_seeds: print(f'seed: {seed:9} offsets: {len(get_offsets(seed)):2}') if len(sys.argv) < 3: res = solve_local() else: res = solve_remote(sys.argv[1], int(sys.argv[2])) print(f"The flag is: {res}") exit(0 if res == expected_flag else 1) if __name__ == '__main__': main() ``` `TSGCTF{D4NCE_R0BOT_D4NCE_8caa8d05ff7f}`