×

zbMATH — the first resource for mathematics

Breaking the stream ciphers F-FCSR-H and F-FCSR-16 in real time. (English) Zbl 1258.94037
Summary: The F-FCSR stream cipher family has been presented a few years ago. Apart from some flaws in the initial propositions, corrected in a later stage, there are no known weaknesses of the core of these algorithms. Two variants, F-FCSR-H and F-FCSR-16, were proposed in the eSTREAM project, and F-FCSR-H v2 is one of the ciphers selected for the eSTREAM portfolio.
In this paper we present a new and severe cryptanalytic attack on the F-FCSR stream cipher family. We give the details of the attack when applied to F-FCSR-H v2 and F-FCSR-16. The attack requires a few Mbytes of received sequence, and the complexity is low enough to allow the attack to be performed on a single PC within seconds.

MSC:
94A60 Cryptography
Software:
eSTREAM; X-FCSR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnault, F.; Berger, T., Design and properties of a new pseudorandom generator based on a filtered FCSR automaton, IEEE Trans. Comput., 54, 1374-1383 (2005)
[2] Arnault, F.; Berger, T.; Gilbert, H.; Handschuh, H., F-FCSR: Design of a new class of stream ciphers, Fast Software Encryption 2005, 83-97 (2005), Berlin: Springer, Berlin · Zbl 1140.68381
[3] Arnault, F.; Berger, T.; Necer, A.; Menezes, A.; Sarkar, P., A new class of stream ciphers combining LFSR and FCSR architectures, Progress in Cryptology—INDOCRYPT 2002, 22-33 (2002), Berlin: Springer, Berlin · Zbl 1033.94507
[4] Arnault, F.; Berger, T.; Necer, A., Feedback with carry shift registers synthesis with the Euclidean algorithm, IEEE Trans. Inf. Theory, 50, 5, 910-917 (2004) · Zbl 1247.94023
[5] F. Arnault, T. Berger, C. Lauradoux, Preventing weaknesses on F-FCSR in IV mode and tradeoff attack on F-FCSR-8. eSTREAM, ECRYPT Stream Cipher Project, Report 2005/075 (2005). http://www.ecrypt.eu.org/stream
[6] F. Arnault, T. Berger, C. Lauradoux, Update on F-FCSR stream cipher. eSTREAM, ECRYPT Stream Cipher Project, Report 2006/025 (2006). http://www.ecrypt.eu.org/stream
[7] Arnault, F.; Berger, T. P.; Lauradoux, C.; Minier, M.; Srinathan, K.; Pandu Rangan, C.; Yung, M., X-FCSR—a new software oriented stream cipher based upon FCSRs, Progress in Cryptology—INDOCRYPT 2007, 341-350 (2007), Berlin: Springer, Berlin · Zbl 1153.68370
[8] F. Arnault, T. Berger, M. Minier, On the security of FCSR-based pseudorandom generators. eSTREAM, ECRYPT Stream Cipher Project, Report 2007/022 (2007). http://www.ecrypt.eu.org/stream
[9] Arnault, F.; Berger, T.; Minier, M., Some results on FCSR automata with applications to the security of FCSR-based pseudorandom generators, IEEE Trans. Inf. Theory, 54, 2, 836-840 (2008) · Zbl 1308.94056
[10] S. Babbage, A space/time tradeoff in exhaustive search attacks on stream ciphers. In European Convention on Security and Detection. IEE Conference Publication, vol. 408 (1995)
[11] S. Babbage, C. De Cannière, A. Canteaut, C. Cid, H. Gilbert, T. Johansson, M. Parker, B. Preneel, V. Rijmen, M.J.B. Robshaw, The eSTREAM portfolio (2008). Available via http://www.ecrypt.eu.org/stream
[12] S. Babbage, C. De Cannière, A. Canteaut, C. Cid, H. Gilbert, T. Johansson, M. Parker, B. Preneel, V. Rijmen, M.J.B. Robshaw, The eSTREAM portfolio (rev. 1) (2008). Available via http://www.ecrypt.eu.org/stream
[13] Biryukov, A.; Shamir, A.; Okamoto, T., Cryptanalytic time/memory/data tradeoffs for stream ciphers, Advances in Cryptology—ASIACRYPT 2000, 1-13 (2000), Berlin: Springer, Berlin · Zbl 0980.94013
[14] Englund, H.; Johansson, T.; Turan, M. S.; Srinathan, K.; Pandu Rangan, C.; Yung, M., A framework for chosen IV statistical analysis of stream ciphers, Progress in Cryptology—INDOCRYPT 2007, 268-281 (2007), Berlin: Springer, Berlin · Zbl 1153.94373
[15] S. Fischer, W. Meier, D. Stegemann, Equivalent representations of the F-FCSR keystream generator. The State of the Art of Stream Ciphers, Workshop Record, SASC 2008, Lausanne, Switzerland, February 2008
[16] Golić, J. D.; Fumy, W., Cryptanalysis of alleged A5 stream cipher, Advances in Cryptology—EUROCRYPT’97, 239-255 (1997), Berlin: Springer, Berlin
[17] Hell, M.; Johansson, T., Breaking the F-FCSR-H stream cipher in real time, Advances in Cryptology—ASIACRYPT 2008, 557-569 (2008), Berlin: Springer, Berlin · Zbl 1206.94071
[18] E. Jaulmes, F. Muller, Cryptanalysis of ECRYPT candidates F-FCSR-8 and F-FCSR-H. eSTREAM, ECRYPT Stream Cipher Project, Report 2005/046 (2005). http://www.ecrypt.eu.org/stream
[19] Jaulmes, E.; Muller, F.; Preneel, B.; Tavares, S., Cryptanalysis of the F-FCSR stream cipher family, Selected Areas in Cryptography—SAC 2005, 36-50 (2005), Berlin: Springer, Berlin
[20] Klapper, A.; Helleseth, T.; Sarwate, D.; Song, H.; Yang, K., A survey of feedback with carry shift registers, Sequences and Their Applications—SETA 2004, 56-71 (2004), Berlin: Springer, Berlin
[21] Klapper, A.; Goresky, M.; Anderson, R. J., 2-adic shift registers, Fast Software Encryption’93, 174-178 (1994), Berlin: Springer, Berlin · Zbl 0943.94515
[22] Klapper, A.; Goresky, M., Feedback shift registers, 2-adic span, and combiners with memory, J. Cryptol., 10, 2, 111-147 (1997) · Zbl 0874.94029
[23] Klapper, A.; Xu, J., Register synthesis for algebraic feedback shift registers based on non-primes, Des. Codes Cryptogr., 31, 3, 227-250 (2004) · Zbl 1064.94012
[24] Koblitz, N., P-adic Numbers, p-adic Analysis, and Zeta-Functions (1996), Berlin: Springer, Berlin
[25] Matsui, M.; Helleseth, T., Linear cryptanalysis method for DES cipher, Advances in Cryptology—EUROCRYPT’93, 386-397 (1994), Berlin: Springer, Berlin · Zbl 0951.94519
[26] Meier, W.; Staffelbach, O., Fast correlation attacks on certain stream ciphers, J. Cryptol., 1, 3, 159-176 (1989) · Zbl 0673.94010
[27] M.-J.O. Saarinen, Chosen-IV statistical attacks on eSTREAM stream ciphers. eSTREAM, ECRYPT Stream Cipher Project, Report 2006/013 (2006). http://www.ecrypt.eu.org/stream
[28] P. Stankovski, M. Hell, T. Johansson, An efficient state recovery attack on X-FCSR-256. Fast Software Encryption 2009 (2009). Preproceedings · Zbl 1248.94096
[29] M. Vielhaber, Breaking ONE.FIVIUM by AIDA an algebraic IV differential attack (2007). Available at http://eprint.iacr.org/2007/413
[30] Zhang, B.; Wu, H.; Feng, D.; Bao, F.; Canteaut, A.; Viswanathan, K., Chosen ciphertext attack on a new class of self-synchronizing stream ciphers, Progress in Cryptology—INDOCRYPT 2004, 73-83 (2004), Berlin: Springer, Berlin · Zbl 1113.94322
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.