Authors L.K. Babenko, E.A. Maro
Month, Year 09, 2016 @en
Index UDC 681.03.245
DOI 10.18522/2311-3103-2016-9-3750
Abstract This article describes the approach to algebraic analysis methods for the evaluation of data protection by cryptographic algorithms, as an example we have observed the symmetric block ciphers. As the base of research we have selected standards GOST 34.12-2015 (n = 64) and PRESENT. The basis of the algebraic analysis is the method of reduction system of equations to the Boolean formulas satisfiability (SAT) problem. We create a generation algorithms of Boolean systems of nonlinear equations for arbitrary substitution boxes and a different number of encryption rounds (based on a Feistel network and SP-network). We present a methodjlogy of algebraic analysis with a SAT-solver CryptoMiniSat, which allows pre-calculating the expected complexity of finding the sets of solutions of Boolean nonlinear equations systems by the methods of reduction to SAT-problem. Observed criteria for the evaluation of data protection based on the algebraic analysis of cryptographic algorithms are listed. Developed in the course of research algorithms and methodology may be further used to evaluate the security of arbitrary transformations on the basis of operations of replacement and addition modulo by algebraic analysis. During the modeling of the algebraic analysis we assessed data protection of reduced-rounds encryption algorithms (experiments were made using SageMath Cloud computing resources). For 8 rounds "Magma" algorithm (GOST 34.12-2015, n = 64) encryption key was calculated with 4 texts for 3029.56 4 seconds. For 4 rounds encryption PRESENT (ISO 29192-2: 2012) we have calculated 16 keys-sets with 8 texts for 3268.42 seconds.

Download PDF

Keywords Evaluation of data protection; algebraic analysis; symmetric block encryption algorithms; GOST 34.12-2015; PRESENT; Boolean formulas satisfiability problem (SAT); solver CryptoMiniSat; algebraic normal form (ANF); conjunctive normal form (CNF).
References 1. Semenov A.A., Zaikin O.S., Bespalov D.V., Ushakov A.A. SAT-podkhod v kriptoanalize nekotorykh sistem potochnogo shifrovaniya [SAT-approach in the cryptanalysis of certain stream encryption systems], Vychislitel'nye tekhnologii [Computational technologies], 2008, Vol. 13, No. 6.
2. Semenov A.A. Algoritmy resheniya zadachi o bulevoy vypolnimosti (SAT) i ikh primenenie v kriptoanalize [Algorithms for solving the problem of Boolean satisfiability (SAT) and their use in cryptanalysis ], PHDays 2015.
3. Soos M., Nohl K., Castelluccia C. Extending SAT Solvers to Cryptographic Problems, Theory and Applications of Satisfiability Testing – SAT, 2009, pp. 244-257.
4. Sepehrdad P. Statistical and Algebraic Cryptanalysis of Lightweight and Ultra-lightweight Symmetric Primitives: PhD Dissertation, 2012, 180 p.
5. Erickson J., Ding J., Christensen C. Algebraic Cryptanalysis of SM4: Grobner Basis Attack and SAT Attack Compared, 12th International Conference, Seoul, Korea, 2009, pp. 73-86.
6. Albrecht M. Tools for Algebraic Cryptanalysis, Proceedings of the ECRYPT Workshop on Tools for Cryptanalysis, 2010, pp. 13-14.
7. Courtois N. Algebraic Complexity Reduction and Cryptanalysis of GOST. Available at:
8. Weinmann R.-P. Algebraic Methods in Block Cipher Cryptanalysis. PhD Dissertation, 2009, 113 p.
9. Bulygin S. Algebraic cryptanalysis of the round-reduced and side channel analysis of the full PRINTCipher-48. Available at:
10. Otpuschennikov I., Semenov A., Gribalova I., Zaikin O., Kochemazov S. Encoding Crypto-graphic functions to SAT Using TRANSALG system, ECAI 2016: 22nd European Conference on Artificial Intelligence, 2016, pp. 1594-1595.
11. Soos M. CryptoMiniSat 2.5.1. Available at:
12. Bard G., Courtois N., Jefferson C. Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT-Solvers, Cryptology ePrint Archive, 2007, Vol. 24. Available at:
13. SageMath, the Sage Mathematics Software System, The Sage Developers, 2016. Available at:
14. GOST R 34.12-2015. Kriptograficheskaya zashchita informatsii [Cryptographic protection of information]. Available at:
15. Babenko L.K., Maro E.A. Analiz stoykosti blochnykh algoritmov shifrovaniya k algebraicheskim atakam [Analysis of resistance block ciphers against algebraic cryptanalysis], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 12 (125), pp. 110-119.
16. Babenko L. K., Maro E.A., Anikeev M.V. Modeling of algebraic analysis of GOST+ cipher in SageMath, 7th international conference on Security of information and networks, 2016,
pp. 100-103.
17. Babenko L.K., Ishchukova E.A., Maro E.A. Algebraic analysis of GOST encryption algorithm, 4th International conference on Security of information and networks, 2011, pp. 57-62.
18. Babenko L.K., Ishchukova E.A. Analiz algoritma GOST 28147-89: poisk slabykh blokov [Analysis of algorithm GOST 28147-89: research of weak s-boxes], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 2 (151), pp. 129-138.
19. Bogdanov A., Knudsen L.R., Leander G., Paar C., Poschmann A., Robshaw M.J., Seurin B., Vikkelsoe C. PRESENT: An ultra-light--weight block cipher, Cryptographic Hardware and Embedded Systems-CHES ’07, 9th International Workshop, Vienna, Austria, 2007,
Vol. 4727, pp. 450-466.
20. Bard G. Algebraic Cryptanalysis, 2009, 356 p.
21. Nakahara J., Sepehrdad P., Zhang B., Wang M. Linear (Hull) and Algebraic Cryptanalysis of the Block Cipher PRESENT, 8th International Conference on Cryptology and Network Security, CANS ’09, New York, 2009, pp. 58-75.

Comments are closed.