BitStorm - Crypto

Points: 50 | Flag: 0xfun{L1n34r_4lg3br4_W1th_Z3_1s_Aw3s0m3} | Solved by: Smothy @ 0xN1umb

what we got

custom PRNG challenge. we get chall.py and output.txt with 60 outputs. goal is to recover the initial state (which is the flag).

the PRNG is a "GiantLinearRNG" with:

• 32 state words, each 64-bit (2048 bits total)
• flag content gets padded to 256 bytes → converted to the seed
• uses taps, XORs, shifts, and rotations to generate new values

def next(self):
    taps = [0, 1, 3, 7, 13, 22, 28, 31]
    new_val = 0
    for i in taps:
        val = s[i]
        mixed = val ^ ((val << 11) & mask) ^ (val >> 7)
        rot = (i * 3) % 64
        mixed = ((mixed << rot) | (mixed >> (64 - rot))) & mask
        new_val ^= mixed
    # ... more mixing
    self.state = s[1:] + [new_val]  # shift
    # compute output from new state

the solve

ngl i tried Z3 first and it just sat there thinking forever lmao. then i remembered - this is ALL linear operations over GF(2). XOR = addition mod 2, shifts and rotations just move bits around.

the key insight: every output bit is just XOR of some subset of the original 2048 state bits. we can track WHICH original bits contribute to each output bit symbolically, then solve the system.

approach:

1. represent each bit as a frozenset of original bit indices it depends on
2. XOR = symmetric difference of sets
3. shifts/rotations = just reindex the bits
4. simulate the PRNG symbolically for 40 outputs (2560 equations, 2048 unknowns)
5. gaussian elimination over GF(2)
6. ???
7. profit

the tricky part was getting the rotation directions right. wasted like 20 mins on that fr

def rotate_right(word, n):
    """(val >> n) | (val << (64-n))"""
    n = n % 64
    return word[n:] + word[:n]  # bit[j] = old_bit[(j+n) % 64]

then just standard gaussian elimination but everything is mod 2:

if augmented[row, col] == 1:
    augmented[row] ^= augmented[pivot_row]  # XOR instead of subtract

after solving, reconstruct the state bits → convert back to bytes → strip null padding → flag

flag

0xfun{L1n34r_4lg3br4_W1th_Z3_1s_Aw3s0m3}

lmaooo the flag literally says "Linear algebra with Z3 is awesome" but Z3 couldn't solve it in time. had to go back to basics with manual gaussian elimination. sometimes the old ways are the best ways

50 points for linear algebra? lowkey felt like more work than the 250pt mersenne twister challenge tbh

smothy out ✌️