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