Jeff's LFSR (jeff)

cryptohack

Task: a Geffe generator — three Fibonacci LFSRs (19/27/23-bit, 69-bit key total) combined as out = LFSR1 if LFSR0 else LFSR2; 256 output bits given, flag AES-CBC encrypted under sha1(str(key))[:16]. Solution: a fast correlation attack. The output correlates with LFSR1 and LFSR2 at P=0.75 each; model each LFSR's 256 outputs as GF(2)-linear functionals of its initial state and use the Walsh-Hadamard transform to find the max-correlation states for the 27-bit and 23-bit registers, then exhaust the 19-bit LFSR0 to match all 256 bits exactly. Reassemble the 69-bit key, derive the AES key, and decrypt.