Geodesic
Algebraic cryptanalysis of round-reduced lightweight ciphers \textsc{Simon} and \textsc{Speck}
Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 84-91.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : algebraic cryptanalysis, Simon
Keywords: block cipher, lightweight cryptography, Speck. 
@article{PDMA_2021_14_a19,
     author = {A. V. Kutsenko and N. D. Atutova and D. A. Zyubina and E. A. Maro and S. D. Filippov},
     title = {Algebraic cryptanalysis of round-reduced lightweight ciphers {\textsc{Simon}} and {\textsc{Speck}}},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {84--91},
     publisher = {mathdoc},
     number = {14},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2021_14_a19/}
}
TY  - JOUR
AU  - A. V. Kutsenko
AU  - N. D. Atutova
AU  - D. A. Zyubina
AU  - E. A. Maro
AU  - S. D. Filippov
TI  - Algebraic cryptanalysis of round-reduced lightweight ciphers \textsc{Simon} and \textsc{Speck}
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2021
SP  - 84
EP  - 91
IS  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2021_14_a19/
LA  - ru
ID  - PDMA_2021_14_a19
ER  - 
%0 Journal Article
%A A. V. Kutsenko
%A N. D. Atutova
%A D. A. Zyubina
%A E. A. Maro
%A S. D. Filippov
%T Algebraic cryptanalysis of round-reduced lightweight ciphers \textsc{Simon} and \textsc{Speck}
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2021
%P 84-91
%N 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2021_14_a19/
%G ru
%F PDMA_2021_14_a19
A. V. Kutsenko; N. D. Atutova; D. A. Zyubina; E. A. Maro; S. D. Filippov. Algebraic cryptanalysis of round-reduced lightweight ciphers \textsc{Simon} and \textsc{Speck}. Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 84-91. http://geodesic.mathdoc.fr/item/PDMA_2021_14_a19/

[1] Raddum H., “Algebraic analysis of the Simon block cipher family”, LNCS, 9230, 2015, 157–169 | MR | Zbl

[2] Courtois N., Mourouzis T., Song G., et al., “Combined algebraic and truncated differential cryptanalysis on reduced-round Simon”, 11th Intern. Conf. Security Cryptogr., 2014, 399–404

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

[4] Courtois N., Shamir A., Patarin J., Klimov A., “Efficient algorithms for solving overdefined systems of multivariate polynomial equations”, LNCS, 1807, 2000, 293–407 | MR

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

[6] Bard G., Algebraic Cryptanalysis, Springer, 2009, 356 pp. | MR | Zbl

[7] Courtois N., Bard G. V., “Algebraic cryptanalysis of the data encryption standard”, LNCS, 4887, 2007, 152–169 | MR | Zbl

[8] Albrecht M., Brickenstein M., 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

[9] Soos M., “The CryptoMiniSat 5 set of solvers at SAT competition 2016”, Proc. SAT Competition (Helsinki, 2016), 28

[10] Biere A., “CaDiCaL, Lingeling, Plingeling, Treengeling, YalSAT entering the SAT Competition 2017”, Proc. SAT Competition (Helsinki, 2017), 14–15

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

[12] Biere A., “New technique for solving sparse equation systems”, Des. Codes Cryptogr., 49:1–3 (2008), 47–60 | MR