solve.py (5888B)
1import random 2import requests 3import subprocess 4import sys 5import time 6 7# MT19937 constants 8W, N, M, R = 32, 624, 397, 31 9A = 0x9908B0DF 10 11w_upper = (1 << W) - (1 << R) 12w_lower = (1 << R) - (1 << 0) 13w_full = (1 << W) - (1 << 0) 14 15def _mask_lower(n): 16 return (1 << n) - (1 << 0) 17 18def mask_lower(bits, n, shl): 19 mask = _mask_lower(n) 20 return (bits & mask) << shl 21 22def _mask_upper(n): 23 return (1 << W) - (1 << (W - n)) 24 25def mask_upper(bits, n, shr): 26 mask = _mask_upper(n) 27 return (bits & mask) >> shr 28 29def undo_selfxor(bits, mask, shr, shl): 30 dirty = (mask << shl) >> shr 31 clean = w_full ^ dirty 32 assert(dirty == (dirty & w_full)) 33 rec = bits & clean 34 while dirty != 0: 35 pre = clean & ((dirty << shr) >> shl) 36 post = ((pre << shl) >> shr) & w_full 37 assert(pre != 0) # we can recover new bits 38 rec |= (((rec & pre) << shl) >> shr) ^ (bits & post) 39 clean |= post 40 dirty &= w_full ^ clean 41 return rec 42 43def harden(bits): 44 bits ^= mask_upper(bits, W - 11, 11) 45 bits ^= mask_lower(bits, W - 7, 7) & 0x9d2c5680 46 bits ^= mask_lower(bits, W - 15, 15) & 0xefc60000 47 bits ^= mask_upper(bits, W - 18, 18) 48 return bits 49 50def unharden(bits): 51 bits = undo_selfxor(bits, _mask_upper(W - 18), 18, 0) 52 bits = undo_selfxor(bits, _mask_lower(W - 15) & (0xefc60000 >> 15), 0, 15) 53 bits = undo_selfxor(bits, _mask_lower(W - 7) & (0x9d2c5680 >> 7), 0, 7) 54 bits = undo_selfxor(bits, _mask_upper(W - 11), 11, 0) 55 return bits 56 57val = random.getrandbits(32) 58assert(unharden(harden(val)) == val) 59 60# for initial state population from seed 61def mutate(state_in, out_i): 62 return (1812433253 * (state_in ^ (state_in >> 30)) + out_i) & w_full 63 64def unmutate(state_out, out_i): 65 state_sub = (state_out + (1 << W) - out_i) & w_full 66 state_xor = (2520285293 * state_sub) & w_full 67 return undo_selfxor(state_xor, _mask_upper(2), 30, 0) 68 69val = random.getrandbits(32) 70assert(unmutate(mutate(val, 1), 1) == val) 71 72def mul_a(x): 73 return (x >> 1) ^ (A * (x & 1)) 74 75def twist(m, u, v): 76 ax = mul_a((u & w_upper) | (v & w_lower)) 77 return m ^ ax 78 79def from_ax(ax): 80 if ax & (1 << 31): 81 assert((ax ^ A) & w_full == (ax ^ A)) 82 x = ((ax ^ A) << 1) | 1 83 else: 84 x = ax << 1 85 return x 86 87def gen_next(states): 88 si = len(states) 89 ax = mul_a(states[si - N][1] | states[si - N + 1][0]) 90 return states[si - N + M][2] ^ ax 91 92def untwist_m_n(m, n): 93 x = from_ax(m ^ n) 94 return x & w_upper, x & w_lower 95 96def consolidate_from_full(state): 97 if state[2] is not None: 98 state[0] = state[2] & w_lower 99 state[1] = state[2] & w_upper 100 101def consolidate_to_full(state): 102 if state[0] is not None and state[1] is not None: 103 state[2] = state[0] | state[1] 104 105def php_reload(states): 106 for i in range(N - M): 107 states[i][2] = twist(states[i+M][2], states[i][2], states[i+1][2]) 108 for i in range(N - M, N - 1): 109 states[i][2] = twist(states[i-N+M][2], states[i][2], states[i+1][2]) 110 states[N-1][2] = twist(states[M][2], states[N-1][2], states[0][2]) 111 for state in states: 112 consolidate_from_full(state) 113 114def php_srand(val): 115 inner = [[None, None, None] for _ in range(N)] 116 inner[0][2] = val 117 consolidate_from_full(inner[0]) 118 for i in range(1, N): 119 inner[i][2] = mutate(inner[i-1][2], i) 120 consolidate_from_full(inner[i]) 121 states = [s[:] for s in inner] 122 php_reload(states) 123 return inner, states 124 125# |A |B | 126# 0 N - M N 127P_A, P_B = (0, N - M) 128 129# states[B] = twist(states[B + M - N], _states[B], _states[B+1] 130# = twist(states[N - M + M - N], _states[B], _states[B+1]) 131# = twist(states[0], _states[B], _states[B+1]) 132# = twist(states[A], _states[B], _states[B+1]) => can recover _state[B+1] 133 134def recover(sa, sb): 135 initial = [[None, None, None] for _ in range(N)] 136 initial[P_B][1], initial[P_B+1][0] = untwist_m_n(sa, sb) 137 138 # recover upper bit 139 cands = [] 140 for b in (0, 1): 141 initial[P_B+1][1] = b << 31 142 consolidate_to_full(initial[P_B+1]) 143 initial[P_B][2] = unmutate(initial[P_B+1][2], P_B+1) 144 if initial[P_B][1] == initial[P_B][2] & w_upper: 145 cands.append(b) 146 if len(cands) != 1: 147 return 148 149 initial[P_B+1][1] = cands[0] << 31 150 consolidate_to_full(initial[P_B+1]) 151 152 for i in range(P_B+2, N, 1): 153 initial[i][2] = mutate(initial[i-1][2], i); 154 consolidate_from_full(initial[i]) 155 156 for i in range(P_B, -1, -1): 157 initial[i][2] = unmutate(initial[i+1][2], i+1) 158 consolidate_from_full(initial[i]) 159 160 prediction = gen_next(initial) 161 expectation = sa 162 163 if prediction == expectation: 164 return initial 165 return None 166 167def main(host="localhost:9095"): 168 print("Timing request..", end="", flush=True) 169 while True: 170 s = int(time.time()) % 60 171 if s == 46: 172 break 173 print(".", end="", flush=True) 174 time.sleep(1) 175 print() 176 177 session = requests.Session() 178 179 r = session.get(f"http://{host}") 180 values = [int(v) for v in r.text.split("\n")[:-2]] 181 stime, sa_h, sb_h = values[0], values[1], values[2+3] 182 assert(stime % 60 == 46) # 3 * 60 + 47 = 227 (but off-by-one) 183 184 # initial, states = php_srand(0) 185 # sa_h = harden(states[0]) >> 1 186 # sb_h = harden(states[N-M]) >> 1 187 188 nextv = None 189 for bits in range(1 << 2): 190 sa = unharden((sa_h << 1) | ((bits >> 0) & 1)) 191 sb = unharden((sb_h << 1) | ((bits >> 1) & 1)) 192 if initial := recover(sa, sb): 193 print("FOUND") 194 php_reload(initial) 195 nextv = harden(initial[301][2]) >> 1 196 break 197 assert(nextv is not None) 198 199 r = session.post(f"http://{host}/submit", data={"next": nextv}) 200 print(r.text) 201 202if __name__ == "__main__": 203 main(*sys.argv[1:])