solve.py (2421B)
1from pwn import * 2 3import random 4import subprocess 5import sys 6import time 7 8# MT19937 constants 9W, N, M, R = 32, 624, 397, 31 10A = 0x9908B0DF 11 12w_upper = (1 << W) - (1 << R) 13w_lower = (1 << R) - (1 << 0) 14w_full = (1 << W) - (1 << 0) 15 16def _mask_lower(n): 17 return (1 << n) - (1 << 0) 18 19def mask_lower(bits, n, shl): 20 mask = _mask_lower(n) 21 return (bits & mask) << shl 22 23def _mask_upper(n): 24 return (1 << W) - (1 << (W - n)) 25 26def mask_upper(bits, n, shr): 27 mask = _mask_upper(n) 28 return (bits & mask) >> shr 29 30def undo_selfxor(bits, mask, shr, shl): 31 dirty = (mask << shl) >> shr 32 clean = w_full ^ dirty 33 assert(dirty == (dirty & w_full)) 34 rec = bits & clean 35 while dirty != 0: 36 pre = clean & ((dirty << shr) >> shl) 37 post = ((pre << shl) >> shr) & w_full 38 assert(pre != 0) # we can recover new bits 39 rec |= (((rec & pre) << shl) >> shr) ^ (bits & post) 40 clean |= post 41 dirty &= w_full ^ clean 42 return rec 43 44def harden(bits): 45 bits ^= mask_upper(bits, W - 11, 11) 46 bits ^= mask_lower(bits, W - 7, 7) & 0x9d2c5680 47 bits ^= mask_lower(bits, W - 15, 15) & 0xefc60000 48 bits ^= mask_upper(bits, W - 18, 18) 49 return bits 50 51def unharden(bits): 52 bits = undo_selfxor(bits, _mask_upper(W - 18), 18, 0) 53 bits = undo_selfxor(bits, _mask_lower(W - 15) & (0xefc60000 >> 15), 0, 15) 54 bits = undo_selfxor(bits, _mask_lower(W - 7) & (0x9d2c5680 >> 7), 0, 7) 55 bits = undo_selfxor(bits, _mask_upper(W - 11), 11, 0) 56 return bits 57 58val = random.getrandbits(32) 59assert(unharden(harden(val)) == val) 60 61# for initial state population from seed 62def mul_a(x): 63 return (x >> 1) ^ (A * (x & 1)) 64 65def gen_next(states): 66 si = len(states) 67 x = (states[si - N] & w_upper) | (states[si - N + 1] & w_lower) 68 return states[si - N + M] ^ mul_a(x) 69 70def main(host="localhost", port="9051"): 71 io = remote(host, int(port)) 72 73 retries = 100 74 good = 9 75 76 values = [] 77 for n in range(retries): 78 assert(io.readline() == b"Hints:\n") 79 for i in range(good): 80 values.append(unharden(int(io.readline()))) 81 assert(io.readline() == b"Guess:\n") 82 if n == retries - 1: 83 break 84 values.append(None) 85 io.sendline(b"0") 86 87 predict = gen_next(values) 88 io.sendline(str(harden(int(predict))).encode()) 89 90 print(io.readline().decode()) 91 92if __name__ == "__main__": 93 main(*sys.argv[1:])