Algebraic Attacks on Grain-like Keystream Generator

This paper analyses the resistance of certain keystream generators against algebraic attacks, namely generators consisting of a nonlinear feedback shift register, a linear feedback shift register and a filter function. We show that poorly chosen filter functions make such designs vulnerable to new algebraic attacks, using a divide and conquer approach that targets the LFSR first. This approach provides efficient LFSR initial state recovery followed by partial NFSR initial state recovery. We apply our algebraic attacks to modified versions of the Grain family of stream ciphers. Our analysis shows that, despite the highly nonlinear filter functions used in these variants, the LFSR state can be recovered using our algebraic attack much faster than exhaustive search. Following this, the NFSR initial state can be partially recovered, leaving a smaller subset of NFSR stages to be exhaustively searched. This investigation highlights the importance of the filter function in keystream generators with a "Grain-like'" structure, and demonstrates that many functions previously considered secure are vulnerable to this attack.