Paper 2004/081

Rewriting Variables: the Complexity of Fast Algebraic Attacks on Stream Ciphers

Philip Hawkes and Gregory G. Rose

Abstract

Recently proposed algebraic attacks [AK03,CM03] and fast algebraic attacks [A04,C03] have provided the best analyses against some deployed LFSR-based ciphers. The process complexity is exponential in the degree of the equations. Fast algebraic attacks were introduced [C03] as a way of reducing run-time complexity by reducing the degree of the system of equations. Previous reports on fast algebraic attacks [A04,C03] have underestimated the complexity of substituting the keystream into the system of equations, which in some cases dominates the attack. We also show how the Fast Fourier Transform (FFT) [CT65] can be applied to decrease the complexity of the substitution step, although in one case this step still dominates the attack complexity. Finally, we show that all functions of degree d satisfy a common, function-independent linear combination that may be used in the pre-computation step of the fast algebraic attack and provide an explicit factorization of the corresponding characteristic polynomial. This yields the fastest known method for performing the pre-computation step.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
stream ciphers
Contact author(s)
phawkes @ qualcomm com
History
2004-03-16: received
Short URL
https://ia.cr/2004/081
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/081,
      author = {Philip Hawkes and Gregory G.  Rose},
      title = {Rewriting Variables: the Complexity of Fast Algebraic Attacks on Stream Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2004/081},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/081}},
      url = {https://eprint.iacr.org/2004/081}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.