Cryptology ePrint Archive: Report 2015/1045

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

Gefei Li and Yuval Yarom and Damith C. Ranasinghe

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 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.

Category / Keywords: secret-key cryptography / Guess-and-determine, NFSR, Sprout

Date: received 28 Oct 2015, last revised 28 Oct 2015

Contact author: yval at cs adelaide edu au

Available format(s): PDF | BibTeX Citation

Version: 20151029:213011 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]