A resynchronization attack on stream ciphers filtered by Maiorana-McFarland functions

Abstract

A resynchronization attack is proposed on stream ciphers filtered by Maiorana-McFarland (M-M) functions and equipped with a linear resynchronization mechanism. The proposed attack utilizes the linear weakness of the resynchronization mechanism, the partial linearity of M-M functions, and applies the linear consistency test method to recover the secret key. It is shown that an M-M function should not be implemented by itself but rather in combination with other nonlinear components in stream ciphers using linear mechanisms to prevent the proposed attack. It is also shown that the use of linear resynchronization mechanisms should be avoided despite their high efficiency in stream ciphers filtered by M-M functions.

Keywords

stream ciphers / Maiorana-McFarland (M-M) functions / cryptanalysis / resynchronization attack

References

[1] Daemen J, Govaerts R, Vandewalle J. Resynchronization weakness in synchronous stream ciphers. In: Proceedings of Workshop on the theory and application of cryptographic techniques on Advances in cryptology. 1994, 159-167

[2] Golić J D, Morgari G. On the resynchronization attack. In: Proceedings of 10th International Workshop on Fast Software Encryption. 2003, 100-110

[3] Borissov Y, Nikova S, Preneel B, Vandewalle J. On a resynchronization weakness in a class of combiners with memory. In: Proceedings of the 3rd international conference on Security in communication networks. 2003, 164-173

[4] Armknecht F, Lano J, Preneel B. Extending the resynchronization attack. In: Proceedings of 11th International Workshop on Selected Areas in Cryptography. 2005, 19-38

[5] Juhani M, Saarinen O. Chosen-IV statistical attacks on eStream ciphers. In: Proceedings of the International Conference on Security and Cryptography. 2006, 260-266

[6] Englund H, Johansson T, Sonmez Turn M. A framework for chosen IV statistical analysis of stream ciphers. In: Proceedings of 8th International Conference on Cryptology in India. 2007, 268-281

[7] Fischer S, Khazaei S, Meier W. Chosen IV statistical analysis for key recovery attacks on stream ciphers. In: Proceedings of 1st International Conference on Cryptology in Africa. 2008, 236-245

[8] Dinur I, Shamir A. Cube attacks on tweakable black box polynomials. In: Proceedings of 28th Annual International Conference on Advances in Cryptology. 2009, 278-299

[9] Camion P, Carlet C, Charpin P, Sendrier N. On correlation-immune functions. In: Proceedings of 11th Annual International Cryptology Conference. 1991, 86-100

[10] Seberry J, Zhang X M, Zheng Y. On constructions and nonlinearity of correlation immune functions. In: Proceedings of Workshop on the theory and application of cryptographic techniques on Advances in cryptology. 1993, 181-193

[11] Chee S, Lee S, Lee D, Sung S H. On the correlation immune functions and their nonlinearity. In: Proceedings of International Conference on the Theory and Applications of Cryptology and Information Security. 1996, 232-243

[12] Carlet C. A larger class of cryptographic Boolean functions via a study of the Maiorana-McFarland construction. In: Proceedings of 22nd Annual International Cryptology Conference on Advances in Cryptology. 2002, 549-564

[13] Carlet C. On the confusion and diffusion properties of Maiorana-McFarland’s and extended Maiorana-McFarland’s functions. Journal of Complexity, 2004, 20(2-3): 182-204

[14] Pasalic E. Maiorana-McFarland class: degree optimization and algebraic properties. IEEE Transactions on Information Theory, 2006, 52(10): 4581-4594

[15] Zeng K, Yang C H, Rao T R N. On the linear consistency test (LCT) in cryptanalysis with applications. In: Proceedings of 9th Annual International Cryptology Conference on Advances in Cryptology. 1990, 164-174

[16] Pasalic E. On guess and determine cryptanalysis of LFSR-based stream ciphers. IEEE Transactions on Information Theory, 2009, 55(7): 3398-3406

[17] Gong G, Khoo K. Additive autocorrelation of resilient Boolean functions. In: Proceedings of 10th Annual International Workshop on Selected Areas in Cryptography. 2003, 275-290

Acknowledgements

This work was supported in part by the Major State Basic Research Development Program of China (973 Program) (2007CB311201), and the National Natural Science Foundation of China (Grant Nos. 60833008 and 60803149), and foundation of Guangxi key laboratory of information and communication (20902).

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg