Paper 2015/1045

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

Gefei Li, Yuval Yarom, and Damith C. Ranasinghe


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 transformations can assist in cryptanalysis of NFSR-based ciphers and demonstrate the application of the technique to successfully cryptanalyse the lightweight cipher Sprout. Our attack on Sprout has a time complexity of 2^70.87, which is 2^3.64 times better than any published non-TMD attack, and requires only 164 bits of plaintext-ciphertext pairs.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
yval @ cs adelaide edu au
2015-10-29: received
Short URL
Creative Commons Attribution


      author = {Gefei Li and Yuval Yarom and Damith C.  Ranasinghe},
      title = {Exploiting Transformations of the Galois Configuration to Improve Guess-and-Determine Attacks on NFSRs},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1045},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.