Geodesic
Solving the problem of Boolean satisfiability for estimating the security of block ciphers Magma and PRESENT to algebraic cryptanalysis
Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 62-64 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 IntelCore i5 for 416.31 sec.
Keywords: cryptography, block ciphers, algorithm PRESENT, SAT-solver, SageMath, security estimation.
Mots-clés : algebraic cryptanalysis, algorithm Magma 
@article{PDMA_2017_10_a25,
     author = {L. K. Babenko and E. A. Maro},
     title = {Solving the problem of {Boolean} satisfiability for estimating the security of block ciphers {Magma} and {PRESENT} to algebraic cryptanalysis},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {62--64},
     year = {2017},
     number = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2017_10_a25/}
}
TY  - JOUR
AU  - L. K. Babenko
AU  - E. A. Maro
TI  - Solving the problem of Boolean satisfiability for estimating the security of block ciphers Magma and PRESENT to algebraic cryptanalysis
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2017
SP  - 62
EP  - 64
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/PDMA_2017_10_a25/
LA  - ru
ID  - PDMA_2017_10_a25
ER  - 
%0 Journal Article
%A L. K. Babenko
%A E. A. Maro
%T Solving the problem of Boolean satisfiability for estimating the security of block ciphers Magma and PRESENT to algebraic cryptanalysis
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2017
%P 62-64
%N 10
%U http://geodesic.mathdoc.fr/item/PDMA_2017_10_a25/
%G ru
%F PDMA_2017_10_a25
L. K. Babenko; E. A. Maro. Solving the problem of Boolean satisfiability for estimating the security of block ciphers Magma and PRESENT to algebraic cryptanalysis. Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 62-64. http://geodesic.mathdoc.fr/item/PDMA_2017_10_a25/

[1] Courtois N., Bard G., Jefferson C., Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over $\mathrm{GF}(2)$ via SAT-Solvers, Cryptology ePrint Archive, Report 2007/024, , 2007 http://eprint.iacr.org/2007/024

[2] Soos M., Nohl K., Castelluccia C., “Extending SAT solvers to cryptographic problems”, Proc. 12th Intern. Conf. Theory and Applications of Satisfiability Testing, 2009, 244–257 | MR

[3] Charfi A., SAT-Solving in Algebraic Cryptanalysis, Bachelor Thesis, 2014 https://www.cdc.informatik.tu-darmstadt.de/reports/reports/Ahmed_Charfi.bachelor.pdf

[4] Courtois N., Gawinecki J., Song G., “Contradiction immunity and guess-then-determine attack on GOST”, Tatra Mt. Math. Publ., 53 (2012), 65–79 https://www.sav.sk/journals/uploads/0114113604CuGaSo.pdf | MR | Zbl

[5] Kazymyrov O., Oliynykov R., Raddum H., “Influence of addition modulo $2^n$ on algebraic attacks”, Cryptography and Communications, 8:2 (2016), 277–289 | DOI | MR | Zbl

[6] Dinur I., Dunkelman O., Shamir A., “Improved attacks on full GOST”, LNCS, 7549, 2012, 9–28 ; https://eprint.iacr.org/2011/558.pdf | Zbl

[7] Nakahara J., Sepehrdad P., Zhang B., Wang M., “Linear (hull) and algebraic cryptanalysis of the block cipher PRESENT”, 8th Intern. Conf. Cryptology and Network Security, CANS'09, N.Y., 2009, 58–75 | DOI | Zbl

[8] Lacko-Bartosova L., “Algebraic cryptanalysis of PRESENT based on the method of syllogism”, Tatra Mt. Math. Publ., 53 (2012), 201–212 https://www.sav.sk/journals/uploads/0114111812lackob.pdf | MR | Zbl

[9] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 7.4), , 2016 http://www.sagemath.org

[10] Sage Reference Manual: Cryptography Release 7.5, http://doc.sagemath.org/pdf/en/reference/cryptography/cryptography.pdf

[11] Babenko L. K., Ischukova E. A., “Analiz algoritma GOST 28147-89: poisk slabykh blokov”, Izvestiya YuFU. Tekhnicheskie nauki. Informatsionnaya bezopasnost, 2014, no. 2(151), 129–138