Abstract
This article presents some new results concerning two algebraic attacks against the F-FCSR constructions proposed in [2]. We focus on the parameters of the stream ciphers proposed that permit to mount algebraic attacks when using the IV mode. The complexity obtained for the first attack described here is 245 binary instructions using 215 known IV values for the construction F-FCSR-SF1. All the proposed attacks are full key recovery attacks. We do not contest that the FCSRs are a good and new idea, we just say that the chosen parameters do not ensure the security level claimed.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arnault, F., Berger, T.P.: Design and properties of a new pseudo-random generator based on a filtered FCSR automaton. IEEE, Transactions on Computers (2005) (To appear)
Arnault, F., Berger, T.P.: F-FCSR: design of a new class of stream ciphers. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 83–97. Springer, Heidelberg (2005)
Arnault, F., Berger, T.P., Lauradoux, C.: The FCSR: primitive specification and supporting documentation. In: ECRYPT - Network of Excellence in Cryptology, Call for stream Cipher Primitives (2005), http://www.ecrypt.eu.org/stream/
Ars, G., Faugère, J.-C.: An algebraic cryptanalysis of nonlinear filter generators using Gröbner bases. Research Report INRIA Lorraine 4739 (2003)
Coppersmith, D., Winograd, S.: On the asymptotic complexity of matrix multiplication. SIAM Journal on Computing 11(3), 472–492 (1982)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic programming. Journal of Symbolic Computation 9(3), 251–280 (1990)
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)
Jaulmes, E., Muller, F.: Cryptanalysis of ecrypt candidates F-FCSR-8 and F-FCSR-H. ECRYPT Stream Cipher Project Report 2005/046 (2005), http://www.ecrypt.eu.org/stream
Jaulmes, E., Muller, F.: Cryptanalysis of the F-FSCR stream cipher family. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 20–35. Springer, Heidelberg (2006)
Klapper, A., Goresky, M.: 2-adic shift registers. In: Anderson, R. (ed.) FSE 1993. LNCS, vol. 809, pp. 174–178. Springer, Heidelberg (1994)
Klimov, A., Shamir, A.: A new class of invertible mappings. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 470–483. Springer, Heidelberg (2003)
Klimov, A., Shamir, A.: Cryptographic applications of T-functions. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 248–261. Springer, Heidelberg (2004)
Klimov, A., Shamir, A.: New applications of T-functions in block ciphers and hash functions. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 19–32. Springer, Heidelberg (2005)
Koblitz, N.: p-adic numbers, p-adic analysis and zeta-functions. Springer, Heidelberg (1997)
Meier, W., Pasalic, E., Carlet, C.: Algebraic attacks and decomposition of Boolean functions. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 474–491. Springer, Heidelberg (2004)
Network of Excellence in Cryptology ECRYPT. Call for stream cipher primitives, http://www.ecrypt.eu.org/stream/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Berger, T.P., Minier, M. (2005). Two Algebraic Attacks Against the F-FCSRs Using the IV Mode. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds) Progress in Cryptology - INDOCRYPT 2005. INDOCRYPT 2005. Lecture Notes in Computer Science, vol 3797. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11596219_12
Download citation
DOI: https://doi.org/10.1007/11596219_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30805-8
Online ISBN: 978-3-540-32278-8
eBook Packages: Computer ScienceComputer Science (R0)