LFSR Destroyer

cryptohack

Task: a filter-generator stream cipher — 128-bit LFSR (taps [0,1,2,7]) with a 6-variable nonlinear filter f over state bits [0,16,32,64,96,127], output bit = 1 XOR f, 256-clock skip; recover the key within a 15 s timeout. Solution: an algebraic attack. f has algebraic immunity 2, so (1+f) has a unique degree-2 annihilator g; every keystream bit equal to 1 gives g(state)=0, a degree-2 equation in the 128 post-skip state bits. Linearize over 8257 monomials, solve the GF(2) system from ~2500 bytes of keystream (numpy bit-packed Gaussian elimination), pick the nonzero nullspace candidate, roll the LFSR backward 256 steps to the original key. Precompute the key-independent equation rows offline so gather+solve fits the timeout.