On Guess and Determine Cryptanalysis of LFSR-Based Stream Ciphers

In this paper, the complexity of applying a guess and determine attack to so-called Linear Feedback Shift register (LFSR)-based stream ciphers is analyzed. This family of stream ciphers uses a single or several LFSR and a filtering function F : GF(2)ⁿ rarr GF(2)^m to generate the blocks of m ges 1 keystream bits at the time. In difference to a classical guess and determine attack, a method based on guessing certain bits in order to determine the remaining secret key/state bits, our approach efficiently takes advantage of the reduced preimage space for relatively large m and at the same time employing the design structure of the cipher. Several variations of the algorithm are derived to circumvent the sensitivity of attack to the input data, n, m and the key length. In certain cases, our attack outperforms classical algebraic attacks; these being considered as one of the most efficient cryptanalyst tools for this type of ciphers. A superior performance of our attack over algebraic attacks is demonstrated in case the filtering function belongs to the extended Maiorana-McFarland class.