Exploiting Transformations of the Galois Configuration to Improve Guess-and-Determine Attacks on NFSRs

Abstract. Guess-and-determine attacks are based on guessing a subset of internal state bits and subsequently using these guesses together with the cipher’s output function to determine the value of the remaining state. These attacks have been successfully employed to break NFSR-based stream ciphers. The complexity of a guess-and-determine attack is directly related to the number of state bits used in the output function. Consequently, an opportunity exits for efficient cryptanalysis of NFSR-based stream ciphers if NFSRs used can be transformed to derive an equivalent stream cipher with a simplified output function. In this paper, we present a new technique for transforming NFSRs. We show how we can use this technique to transform NFSRs to equivalent NFSRs with simplified output functions. We explain how such transfor-mations can assist in cryptanalysis of NFSR-based ciphers and demon-strate the application of the technique to successfully cryptanalyse the lightweight cipher Sprout. Our attack on Sprout has a time complexity of 270.87, which is 23.64 times better than any published non-TMD attack, and requires only 164 bits of plaintext-ciphertext pairs