Accelerated brute force attack on sequential 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

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

² Department of Computer Engineering, 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, and 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 this 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] K. Alimohammadi, (2020). A secure key-aggregate authentication cryptosystem for data sharing in dynamic cloud storage. Multimedia Tools and Applications, 79, 2855–2872.

[2] M. Anzani, H. Haj Seyyed Javadi, V. Modirir, (2018). Key-management scheme for wireless sensor networks based on merging blocks of symmetric design. Wireless Networks, 24(8), 2867–2879.

[3] N. T. Courtois, (2001). The security of Hidden Field Equations (HFE). Topics in Cryptology - CT-RSA 2001, LNCS 2020, Springer-Verlag, 266 -281.

[4] N. T. Courtois (2003). Fast algebraic attack on stream ciphers with linear feedback. Advances in Cryptology - Crypto 2003, LNCS 2729, Springer-Verlag, 176-194.

[5] N. T. Courtois, W. Meier. (2003). Algebraic attacks on stream ciphers with linear feedback. Advances in Cryptology - EUROCRYPT 2003, LNCS 2656, Springer-Verlag, 345-359.

[6] N. T. Courtois, A. Klimov, J. Patarin, A. Shamir (2000). Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. Advances in Cryptology - EUROCRYPT 2000, LNCS 1807, Springer-Verlag, 392-407.

[7] K. Diem (2004). The XL-algorithm and a conjecture from commutative algebra. Advances in cryptology - ASIACRYPT 2004, LNCS 3329, Springer-Verlag, 323-337.

[8] S. H. Erfani, H. Haj Seyyed Javadi, A. M. Rahmani (2015). A dynamic key management scheme for dynamic wireless sensor networks. Security and Communication Networks, 8(6), 1040-1049.

[9] Z. Eskandari, A. Ghaemi Bafghi (2020). Extension of Cube Attack with Probabilistic Equations and it’s Application on Cryptanalysis of KATAN Cipher. ISeCure, 12(1), 1-12.

[10] M. Javanbakht, S. H. Erfani, H. Haj Seyyed Javadi, P. Daneshjoo (2014). Key Predistribution Scheme for Clustered Hierarchical Wireless Sensor Networks based on Combinatorial Designs. Security and Communication Networks, 7(11), 2003-2014.

[11] P. Hawkes, G. Rose (2004). The complexity of fast algebraic attacks onstream ciphers. Advances in Cryptology - Crypto 2004, LNCS 3152, Springer-Verlag, 390-406.

[12] M. Krause, F. ArmKnecht (2003). Algebraic attacks on combiners with memory. Advances in Cryptology - Crypto 2003, LNCS 2729, Springer-Verlag, 162-175.

[13] C. Li, B. Preneel (2019). Improved Interpolation Attacks on Cryptographic Primitives of Low Algebraic Degree. Selected Areas in Cryptography 2019, Available on IACR Cryptology ePrint Archive 2019: 812, 1-23.

[14] J. Pieprzyk, N. T. Courtois (2002). Cryptanalysis of block ciphers with overdened systems ofequations. Advances in cryptology - ASIACRYPT 2002, LNCS 2501, Springer-Verlag, 267-287.

[15] R. A. Mollin (2006). An Introduction to Cryptography. New York: Chapman and Hall/CRC.

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

[17] M. Voros, (2007). Algebraic attack on stream ciphers. Master Thesis, Comenius University.

Computational Sciences and Engineering

Accelerated brute force attack on sequential cipher systems on LFSR

References

References

Volume 3, Issue 1
April 2023
Pages 115-128

Accelerated brute force attack on sequential cipher systems on LFSR

References

References

Volume 3, Issue 1April 2023Pages 115-128

Volume 3, Issue 1
April 2023
Pages 115-128