Solving the problem of boolean satisfiability for estimating the security of block ciphers magma and present to algebraic cryptanalysis
Some results of experimental investigating algorithms for cryptanalysis of ciphers Magma and PRESENT are presented. Algorithms under investigation solve the systems of Boolean equations of these ciphers by known methods - SAT and XL. The ciphers under consideration have been taken with small numbers of rounds (3, 4 in PRESENT, 5, 8 in Magma) and simplified S-boxes (identical, linearized in Magma). The experimental results (memory size, running time, number of addition operations) are presented in dependence on the numbers of plain/cipher texts, equations, unknowns, etc. For example, the 8-round cipher Magma with 5376 equations, 2048 unknowns is analysed by a computer with the processor Intel-Core i5 for 416.31 sec.
Download file
Counter downloads: 184
Keywords
криптография, алгебраический криптоанализ, блочные алгоритмы шифрования, Магма, PRESENT, SAT-решатель, SageMath, cryptography, algebraic cryptanalysis, block ciphers, algorithm Magma, algorithm PRESENT, SAT-solver, SageMath, security estimationAuthors
| Name | Organization | |
| Babenko L.K. | Southern Federal University | blk@tsure.ru |
| Maro E. A. | Southern Federal University | eamaro@sfedu.ru |
References
Courtois N., Bard G., and 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, Report 2007/024, 2007. http://eprint.iacr.org/2007/024
Soos M., NohlK., and Castelluccia C. Extending SAT solvers to cryptographic problems // Proc. 12th Intern. Conf. Theory and Applications of Satisfiability Testing. 2009. P. 244-257.
Charfi A. SAT-Solving in Algebraic Cryptanalysis. Bachelor Thesis, 2014. https://www.cdc. informatik.tu-darmstadt.de/reports/reports/Ahmed_Charfi.bachelor.pdf
Courtois N., Gawinecki J., and Song G. Contradiction immunity and guess-then-determine attack on GOST // Tatra Mt. Math. Publ. 2012. V. 53. P. 65-79. https://www.sav.sk/ journals/uploads/0114113604CuGaSo.pdf
Kazymyrov O., Oliynykov R., and Raddum H. Influence of addition modulo 2n on algebraic attacks // Cryptography and Communications. 2016. V. 8. Iss.2. P. 277-289.
Dinur I., Dunkelman O., and Shamir A. Improved attacks on full GOST // LNCS. 2012. V.7549. P. 9-28. https://eprint.iacr.org/2011/558.pdf
Nakahara J., Sepehrdad P., Zhang B., and Wang M. Linear (hull) and algebraic cryptanalysis of the block cipher PRESENT // 8th Intern. Conf. Cryptology and Network Security CANS'09. N.Y., 2009. P. 58-75.
Lacko-Bartosov L. Algebraic cryptanalysis of PRESENT based on the method of syllogism // Tatra Mt. Math. Publ. 2012. V. 53. P. 201-212. https://www.sav.sk/journals/uploads/ 0114111812lackob.pdf
The Sage Developers. SageMath, the Sage Mathematics Software System (Version 7.4), 2016. http://www.sagemath.org
Sage Reference Manual: Cryptography Release 7.5. http://doc.sagemath.org/pdf/en/ reference/cryptography/cryptography.pdf
Бабенко Л. К., Ищукова Е. А. Анализ алгоритма ГОСТ 28147-89: поиск слабых блоков // Известия ЮФУ. Технические науки. Информационная безопасность. 2014. №2 (151). С. 129-138.
