Accelerated brute force attack on stream cipher systems on LFSR

Babaei, Alireza; Haj Seyyed Javadi, Hamid; Jafari Rad, Nader

doi:10.22124/cse.2024.25975.1065

Document Type : Original Article

Authors

¹ Faculty of Basic Sciences, Shahed University, Tehran, Iran

² Faculty of Computer Engineering, Shahed University, Tehran, Iran

https://doi.org/10.22124/cse.2024.25975.1065

Abstract

Algebraic attack is an emergent decryption method. The main objective in this decryption is to form and solve a set of multivariate polynomial equations on finite fields. The present findings show that algebraic attacks have been significantly successful and effective on a specific type of stream ciphers system and linear-feedback shift register systems (LFSRs). One of the reasons for this is that linear functions are used for updating LFSRs, although the nonlinear types can also be approximated by an appropriate linear function, and this increases the necessity of paying attention to it. In the present article, an attempt is made to present the main idea of algebraic attacks on stream ciphers systems, to explain these ideas by certain concrete examples. Particularly, a synchronous stream cipher system based on LFSRs, entitled the LILI stream ciphers, and algebraic attacks on them, will be discussed. In algebraic attacks, solving a set of multivariate polynomial equations is needed. In the present research, the extended linearization algorithm (XL) will be used to deal with an attained set of equations. Additionally, some of the accelerated extended algorithms (XL) for dealing with the set of equations algebraic resulted from the attacks on stream cipher systems, will be analyzed and their efficiency will be examined in the frame of certain examples.

Keywords

References

[1] Courtois, N. T. (2001). The security of hidden field equations (HFE). In Topics in Cryptology—CT-RSA 2001: The Cryptographers’ Track at RSA Conference 2001 San Francisco, CA, USA, April 8–12, 2001 Proceedings (pp. 266-281). Springer Berlin Heidelberg.

[2] Courtois, N. T., & Meier, W. (2003). Algebraic attacks on stream ciphers with linear feedback. In Advances in Cryptology—EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003 Proceedings 22 (pp. 345-359). Springer Berlin Heidelberg.

[3] Courtois, N., Klimov, A., Patarin, J., & Shamir, A. (2000, May). Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In International Conference on the Theory and Applications of Cryptographic Techniques (pp. 392-407). Berlin, Heidelberg: Springer Berlin Heidelberg.

[4] Courtois, N. T., & Pieprzyk, J. (2002). Cryptanalysis of block ciphers with overdefined systems of equations. In Advances in Cryptology—ASIACRYPT 2002: 8th International Conference on the Theory and Application of Cryptology and Information Security Queenstown, New Zealand, December 1–5, 2002 Proceedings 8 (pp. 267-287). Springer Berlin Heidelberg.

[5] Diem, C. (2004). The XL-algorithm and a conjecture from commutative algebra. In Advances in Cryptology-ASIACRYPT 2004: 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004. Proceedings 10 (pp. 323-337). Springer Berlin Heidelberg.

[6] Najafi, A., Bayat, M., & Haj Seyyed Javadi, H. (2018). Search over Encrypted Data: Functionalities and Challenges. Biannual Journal Monadi for Cyberspace Security (AFTA), 7(1), 21-44.

[7] Momenzadeh, A., Javadi, H. H. S., & Dezfouli, M. A. (2009, March). Design an efficient system for intrusion detection via evolutionary fuzzy system. In 2009 11th International Conference on Computer Modelling and Simulation (pp. 89-94). IEEE.

[8] Alimohammadi, K., Bayat, M., & Javadi, H. H. (2020). A secure key-aggregate authentication cryptosystem for data sharing in dynamic cloud storage. Multimedia Tools and Applications, 79, 2855-2872.

[9] Haj Seyyed Javadi, H., & Anzani, M. (2015). Hybrid Key pre-distribution scheme for wireless sensor network based on combinatorial design. Journal of Advances in Computer Engineering and Technology, 1(3), 33-38.

[10] Eskandari, Z. (2019). Algebraic Attack in Presence of NonLinear and Noisy Equations. ISeCure, 12,1-12.

[11] Vörös, M. (2007). Algebraic attack on stream ciphers. Master's thesis, Comenius University, Faculty of Mathematics, Physics and Informatics, Department of Computer Science.

[12] Li, C., & Preneel, B. (2019, August). Improved interpolation attacks on cryptographic primitives of low algebraic degree. In International conference on selected areas in cryptography (pp. 171-193). Cham: Springer International Publishing.

[13] Akhbarifar, S., Haj Seyyed Javadi, H., Rahmani, A. M., & Hosseinzadeh, M. (2019). Hybrid key pre-distribution scheme based on symmetric design. Iranian Journal of Science and Technology, Transactions A: Science, 43, 2399-2406.

[14] Kipnis, A., & Shamir, A. (1999, August). Cryptanalysis of the HFE public key cryptosystem by relinearization. In Annual International Cryptology Conference (pp. 19-30). Berlin, Heidelberg: Springer Berlin Heidelberg.

[15] Wang Q, Hao Y, Todo Y, Li C, Isobe T, Meier W. Improved division property based cube attacks exploiting algebraic properties of superpoly. InAdvances in Cryptology–CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part I 38 2018 (pp. 275-305). Springer International Publishing.

Computational Sciences and Engineering

Accelerated brute force attack on stream cipher systems on LFSR

References

References

Articles in Press, Accepted Manuscript
Available Online from 19 February 2024

Accelerated brute force attack on stream cipher systems on LFSR

References

References

Articles in Press, Accepted Manuscript Available Online from 19 February 2024

Articles in Press, Accepted Manuscript
Available Online from 19 February 2024