Abstract
Recently proposed algebraic attacks [2,6] and fast algebraic attacks [1,5] 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 [5] as a way of reducing run-time complexity by reducing the degree of the system of equations. Previous reports on fast algebraic attacks [1,5] 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) [4] can be applied to decrease the complexity of the substitution step. Finally, it is shown 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. An explicit factorization of the corresponding characteristic polynomial yields the fastest known method for performing the pre-computation step.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Armknecht, F.: Improving Fast Algebraic Attacks. In: To be presented at FSE2004 Fast Software Encryption Workshop, Delhi, India, February 5-7 (2004)
Armknecht, F., Krause, M.: Algebraic Attacks on Combiners with Memory. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 162–176. Springer, Heidelberg (2003)
Bluetooth CIG, Specification of the Bluetooth system, Version 1.1, February 22 (2001), Available from www.bluetooth.com
Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90), 297-301 (1965)
Courtois, N.: Fast Algebraic Attacks on Stream Ciphers with Linear Feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 177–194. Springer, Heidelberg (2003)
Courtois, N., Meier, W.: Algebraic Attacks on Stream Ciphers with Linear Feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003)
Key, E.: An Analysis of the Structure and Complexity of Nonlinear Binary Sequence Generators. IEEE Transactions on Information Theory IT-22(6) (1976)
Massey, J.: Shift Register synthesis and BCH decoding. IEEE Transactions on Information Theory IT-15, 122–127 (1969)
Menezes, A., van Oorschot, P., Vanstone, A.: Handbook of Applied Cryptography. CRC Press series on discrete mathematics and its applications. CRC Press LLC, Boca Raton (1997)
Mihaljevic, M., Imai, H.: Cryptanalysis of Toyocrypt-HS1 stream cipher. IEICE Transactions on Fundamentals, E85-A, 66-73 (January 2002), Available at http://www.csl.sony.co.jp/ATL/papers/IEICEjan02.pdf
Rueppel, R.: Stream Ciphers. In: Simmons, G. (ed.) Contemporary Cryptology: The Science of Information Integrity, IEEE Press, New York (1991)
Simpson, L., Dawson, E., Golic, J., Millan, W.: LILI Keystream Generator. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012, pp. 392–407. Springer, Heidelberg (2001)
Strassen, V.: Gaussian Elimination is Not Optimal. Numerische Mathematik 13, 354–356 (1969)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hawkes, P., Rose, G.G. (2004). Rewriting Variables: The Complexity of Fast Algebraic Attacks on Stream Ciphers. In: Franklin, M. (eds) Advances in Cryptology – CRYPTO 2004. CRYPTO 2004. Lecture Notes in Computer Science, vol 3152. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28628-8_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-28628-8_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22668-0
Online ISBN: 978-3-540-28628-8
eBook Packages: Springer Book Archive