Algebraic cryptanalysis of round-reduced lightweight ciphers simon and Speck | Applied Discrete Mathematics. Supplement. 2021. № 14. DOI: 10.17223/2226308X/14/19

Algebraic cryptanalysis of round-reduced lightweight ciphers simon and Speck

This paper presents algebraic attacks on Simon and Speck, two families of lightweight block ciphers having LRX- and ARX-structures respectively. They were presented by the U.S. National Security Agency in 2013 and later standardized by ISO as a part of the RFID air interface standard. The ciphers are algebraically encoded, and the resulting systems of Boolean equations are solved with different SAT solvers as well as methods based on the linearization. For the first time, the approaches that use the sparsity of systems of Boolean equations are applied to these ciphers. The linearization parameters in systems of equations for both of the ciphers are estimated. A comparison of the efficiency of the used methods is provided.The results of the algebraic analysis show that the inclusion of additional nonlinear operations significantly increases the attack time and the amount of memory used. Therefore, the methods considered are more effective for cryptanalysis of the Simon cipher than Speck.

Download file

Counter downloads: 29

Keywords

Speck, Simon, lightweight cryptography, block cipher, algebraic cryptanalysis

Authors

Name	Organization	E-mail
Kutsenko A. V.	Novosibirsk State University; Institute of Mathematics. S. L. Sobolev SB RAS	alexandrkutsenko@bk.ru
Atutova N. D.	Novosibirsk State University; JetBrains Research Crypto Lab	atutova.n@yandex.ru
Zyubina D. A.	Novosibirsk State University; JetBrains Research Crypto Lab	zyubinadarya@gmail.com
Maro E. A.	South Federal University	marokat@gmail.com
Filippov S. D.	Saint Petersburg State University	filippowstepan@yandex.ru

Всего: 5

References

Biere A. New technique for solving sparse equation systems // Des. Codes Cryptogr. 2008.

Raddum H. and Semaev I. New Technique for Solving Sparse Equation Systems. IACR Cryptology ePrint Archive, 2006/475, 2006.

Biere A. CaDiCaL, Lingeling, Plingeling, Treengeling, YalSAT entering the SAT Competition 2017 // Proc. SAT Competition. Helsinki, 2017. P. 14-15.

Soos M. The CryptoMiniSat 5 set of solvers at SAT competition 2016 // Proc. SAT Competition. Helsinki, 2016. P. 28.

Albrecht M., Brickenstein M., and Soos M. An ANF to CNF Converter using a Dense/Sparse Strategy. https://doc.sagemath.org/html/en/reference/sat/sage/sat/converters/polybori.html.

Courtois N. and Bard G. V. Algebraic cryptanalysis of the data encryption standard // LNCS. 2007. V.4887. P. 152-169.

Courtois N. The Security of Cryptographic Primitives based on Multivariate Algebraic Problems. Ph.D. Thesis, Paris, 2001.

Bard G. Algebraic Cryptanalysis. Springer, 2009. 356 p.

Courtois N., Shamir A., Patarin J., and Klimov A. Efficient algorithms for solving overdefined systems of multivariate polynomial equations // LNCS. 2000. V. 1807. P. 293-407.

Beaulieu R., Shors D., Smith J., et al. The Simon and Speck Families of Lightweight Block Ciphers. Cryptology ePrint Archive, Report 2013/404, 2013.

Raddum H. Algebraic analysis of the Simon block cipher family // LNCS. 2015. V. 9230. P. 157-169.

Courtois N., Mourouzis T., Song G., et al. Combined algebraic and truncated differential cryptanalysis on reduced-round Simon // 11th Intern. Conf. Security Cryptogr. 2014. P. 399-404