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)(n) -> GF(2)(m) to generate the blocks of m >= 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 in 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 [10]; 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.
guess and determine stream ciphers algebraic attacks algebraic immunity annihilators linear feedback shift register (lfsr) filtering generator nonlinear combiner boolean function filter state guessing attack