zbMATH — the first resource for mathematics

An efficient state recovery attack on the X-FCSR family of stream ciphers. (English) Zbl 1350.94051
Summary: We describe a state recovery attack on the X-FCSR family of stream ciphers. In this attack we analyse each block of output keystream and try to solve for the state. The solver will succeed when a number of state conditions are satisfied. For X-FCSR-256, our best attack has a computational complexity of only \(2^{4.7}\) table lookups per block of keystream, with an expected \(2^{44.3}\) such blocks before the attack is successful. The precomputational storage requirement is \(2^{33}\). For X-FCSR-128, the computational complexity of our best attack is \(2^{16.3}\) table lookups per block of keystream, where we expect \(2^{55.2}\) output blocks before the attack comes through. The precomputational storage requirement for X-FCSR-128 is \(2^{67}\).

94A60 Cryptography
Full Text: DOI
[1] Arnault, F.; Berger, T.; Gilbert, H. (ed.); Handschuh, H. (ed.), F-FCSR: design of a new class of stream ciphers, No. 3557, 83-97, (2005), Berlin · Zbl 1140.68381
[2] 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 · Zbl 1153.68370
[3] Arnault, F.; Berger, T.; Lauradoux, C.; Minier, M.; Pousse, B.; Rijmen, V. (ed.); Jacobson, M.J. (ed.); Safavi-Naini, R. (ed.), A new approach for F-fcsrs, No. 5867, 433-448, (2009), Berlin · Zbl 1267.94032
[4] Arnault, F.; Berger, T.P.; Lauradoux, C.; Srinathan, K. (ed.); Pandu Rangan, C. (ed.); Yung, M. (ed.), M. minier. X-FCSR—a new software oriented stream cipher based upon fcsrs, No. 4859/2007, 341-350, (2007), Berlin · Zbl 1153.68370
[5] Berger, T.; Minier, M.; Pousse, B.; Roy, B. (ed.); Sendrier, N. (ed.), Software oriented stream ciphers based upon FCSRs in diversified mode, No. 5922, 119-135, (2009), Berlin · Zbl 1252.94048
[6] ECRYPT. eSTREAM: ECRYPT Stream Cipher Project, IST-2002-507932. Available at http://www.ecrypt.eu.org/stream/. Last accessed on January 14, 2011 · Zbl 1091.68036
[7] Hell, M.; Johansson, T., Breaking the F-FCSR-H stream cipher in real time, No. 5350/2008, 557-569, (2008), Berlin · Zbl 1206.94071
[8] M. Hell, T. Johansson, Breaking the Stream Ciphers F-FCSR-H and F-FCSR-16 in Real Time. J. Cryptol. (2009) · Zbl 1258.94037
[9] 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 · Zbl 1252.94048
[10] Jaulmes, E.; Muller, F.; Preneel, B. (ed.); Tavares, S. (ed.), Cryptanalysis of the F-FCSR stream cipher family, No. 3897, 36-50, (2005), Berlin
[11] Klapper, A.; Goresky, M.; Anderson, R.J. (ed.), 2-adic shift registers, No. 809, 174-178, (1994), Berlin · Zbl 0943.94515
[12] Klapper, A.; Goresky, M., Feedback shift registers, 2-adic span, and combiners with memory, J. Cryptol., 10, 111-147, (1997) · Zbl 0874.94029
[13] Pagh, R., F. F. rodler. cuckoo hashing, J. Algorithms, 51, 122-144, (2004) · Zbl 1091.68036
[14] Stankovski, P.; Hell, M.; Johansson, T., An efficient state recovery attack on X-FCSR-256, No. 5665, 23-37, (2009), Berlin · Zbl 1248.94096
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.