Geodesic
Guess-and-determine attacks and automatic methods for their construction
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 81-86.

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

In the paper, a brief review of approaches to construction of cryptographic attacks from the class “guess-and-determine” is presented. The main focus is done on recent works, in which some automatic methods for constructing SAT-based guess-and-determine attacks were proposed. With that purpose, the problems of constructing corresponding attacks are stated as optimization problems for specific evaluation functions over Boolean hypercube. To solve the latter, the metaheuristic algorithms widely employed in discrete optimization are used. In the mentioned papers, two types of evaluation functions were formally introduced. Those can be viewed as concretizations of the notions of “UNSAT-immunity” and “SAT-immunity” informally introduced by N. Courtois in 2012. Within the report, several examples of constructing guess-and-determine attacks of the mentioned type on a number of block and stream ciphering algorithms will be given.
Keywords: guess-and-determine attacks, Boolean satisfiability problem, SAT. 
@article{PDMA_2018_11_a25,
     author = {A. A. Semenov},
     title = {Guess-and-determine attacks and automatic methods for their construction},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {81--86},
     publisher = {mathdoc},
     number = {11},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2018_11_a25/}
}
TY  - JOUR
AU  - A. A. Semenov
TI  - Guess-and-determine attacks and automatic methods for their construction
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2018
SP  - 81
EP  - 86
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2018_11_a25/
LA  - ru
ID  - PDMA_2018_11_a25
ER  - 
%0 Journal Article
%A A. A. Semenov
%T Guess-and-determine attacks and automatic methods for their construction
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2018
%P 81-86
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a25/
%G ru
%F PDMA_2018_11_a25
A. A. Semenov. Guess-and-determine attacks and automatic methods for their construction. Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 81-86. http://geodesic.mathdoc.fr/item/PDMA_2018_11_a25/

[1] Tseitin G. S., “O slozhnosti vyvoda v ischislenii vyskazyvanii”, Zapiski nauchnykh seminarov LOMI AN SSSR, 8, 1968, 234–259 | MR | Zbl

[2] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1986 | MR

[3] Dowling W., Gallier J., “Linear-time algorithms for testing the satisfiability of propositional horn formulae”, J. Logic Programming, 7 (1984), 267–284 | DOI | MR

[4] Cook S. A., “The complexity of theorem-proving procedures”, Third Ann. ACM Symp. on Theory of Computing, 1971, 151–159 | DOI

[5] Anderson R., A5 (Was: Hacking Digital Phones), , Newsgroup Communication, 1994 http://yarchive.net/phone/gsmcipher.html

[6] Gendrullis T., Novotny M., Rupp A., “A real-world attack breaking A5/1 within hours”, LNCS, 5154, 2008, 266–282

[7] Bulavintsev V., Semenov A., Zaikin O., Kochemazov S., “A bitslice implementation of Anderson's attack on A5/1”, Open Eng., 8 (2018), 7–16 | DOI

[8] Golic J. Dj., “Cryptanalysis of alleged A5 stream cipher”, LNCS, 1233, 1997, 239–255

[9] Agibalov G. P., “Logicheskie uravneniya v kriptoanalize generatorov klyuchevogo potoka”, Vestnik Tomskogo gosudarstvennogo universiteta. Prilozhenie, 2003, no. 6, 31–41

[10] Timoshevskaya N. E., “Zadachi o kratchaishem linearizatsionnom mnozhestve”, Vestnik Tomskogo gosudarstvennogo universiteta. Prilozhenie, 2005, no. 4, 79–83

[11] Courtois N., Pieprzyk J., “Cryptanalysis of block ciphers with overdefined systems of equations”, LNCS, 2501, 2003, 267–287 | MR

[12] Marques-Silva J., Lynce I., Malik S., “CDCL Solvers”, Handbook of Satisfiability, IOS Press, 2009, 131–153

[13] Mironov I., Zhang L., “Applications of SAT solvers to cryptanalysis of hash functions”, LNCS, 4121, 2006, 102–115 | MR | Zbl

[14] De D., Kumarasubramanian A., Venkatesan R., “Inversion attacks on secure hash functions using SAT solvers”, LNCS, 4501, 2007, 377–382 | Zbl

[15] Semenov A., Zaikin O., Bespalov D., Posypkin M., “Parallel logical cryptanalysis of the generator A5/1 in BNB-Grid system”, LNCS, 6873, 2011, 473–483 | Zbl

[16] Posypkin M. A., Zaikin O. S., Bespalov D. V., Semenov A. A., “Reshenie zadach kriptoanaliza potochnykh shifrov v raspredelennykh vychislitelnykh sredakh”, Trudy ISA RAN, 46, 2009, 119–137

[17] Bard G., Algebraic Cryptanalysis, Springer, 2009 | MR | Zbl

[18] Semenov A., Zaikin O., “Using Monte Carlo method for searching partitionings of hard variants of Boolean satisfiability problem”, LNCS, 9251, 2015, 222–230

[19] Semenov A., Zaikin O., “Algorithm for finding partitionings of hard variants of Boolean satisfiability problem with application to inversion of some cryptographic functions”, SpringerPlus, 5:1 (2016), 1–16 | DOI | MR

[20] Courtois N. T., Gawinecki J. A., Song G., “Contradiction immunity and guess-then-determine attacks on GOST”, Tatra Mountains Mathematical Publications, 53:1 (2012), 2–13 | DOI | MR

[21] Courtois N. T., Algebraic Complexity Reduction and Cryptanalysis of GOST, Preprint, , 2010–2013 https://eprint.iacr.org/2011/626.pdf

[22] Semenov A., Zaikin O., Otpuschennikov I., et al., “On cryptographic attacks using backdoors for SAT”, The Thirty-Second AAAI Conf. on Artificial Intelligence, AAAI'2018, New Orleans, Louisiana, USA, 2018, 6641–6648

[23] Williams R., Gomes C. P., Selman B., “Backdoors to typical case complexity”, Proc. of IJCAI, Acapulco, Mexico, 2003, 1173–1178