nullcon2023-chall-randrevenge

PHP PRNG prediction challenge for NullCon 2023 Berlin
git clone https://git.sinitax.com/sinitax/nullcon2023-chall-randrevenge
Log | Files | Refs | sfeed.txt

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:])