Geodesic
Using inverse backdoors sets to construct guess-and-determine attacks on hash-functions MD4
Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 124-129.

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

In the paper, we propose new preimage attacks on hash-functions MD4-$k$, $k>39$. These attacks, related to the class of guess-and-determine attacks, are based on the idea of inverse backdoor set. We use SAT solvers to solve the cryptanalysis problems weakened by substitution of guessed bits to SAT encodings of the considered functions. The problem of search for an inverse backdoor set with relatively small complexity estimation is considered as a minimization problem of a special pseudo-Boolean function. To solve this problem, we apply several metaheuristic algorithms: tabu search algorithm, (1+1)-$FEA_{\beta}$, and a variant of genetic algorithm. These algorithms produce attacks on the considered functions with close complexity estimations. For the full-round compression function MD4 the best attack is constructed using the genetic algorithm.
Keywords: preimage attack on hash function, guess-and-determine attacks, inverse backdoor sets, SAT.
Mots-clés : MD4 
@article{PDMA_2020_13_a36,
     author = {I. A. Gribanova and A. A. Semenov},
     title = {Using inverse backdoors sets to construct guess-and-determine attacks on hash-functions {MD4}},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {124--129},
     publisher = {mathdoc},
     number = {13},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2020_13_a36/}
}
TY  - JOUR
AU  - I. A. Gribanova
AU  - A. A. Semenov
TI  - Using inverse backdoors sets to construct guess-and-determine attacks on hash-functions MD4
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2020
SP  - 124
EP  - 129
IS  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2020_13_a36/
LA  - ru
ID  - PDMA_2020_13_a36
ER  - 
%0 Journal Article
%A I. A. Gribanova
%A A. A. Semenov
%T Using inverse backdoors sets to construct guess-and-determine attacks on hash-functions MD4
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2020
%P 124-129
%N 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2020_13_a36/
%G ru
%F PDMA_2020_13_a36
I. A. Gribanova; A. A. Semenov. Using inverse backdoors sets to construct guess-and-determine attacks on hash-functions MD4. Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 124-129. http://geodesic.mathdoc.fr/item/PDMA_2020_13_a36/

[1] Semenov A., Zaikin O., Otpuschennikov I., et al., “On cryptographic attacks using backdoors for SAT”, Proc. 32nd AAAI Conf., 2018, 6641–6648

[2] Bard G., Algebraic Cryptanalysis, Springer Publishing Company, Inc., 2009, 356 pp. | MR | Zbl

[3] Semenov A., Otpuschennikov I., Gribanova I., et al., “Translation of algorithmic descriptions of discrete functions to SAT with application to cryptanalysis problems”, Log. Methods Comput. Sci., 16:1 (2020), 29:1–29:42 | MR | Zbl

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

[5] Chen Ch., Li R., Matematicheskaya logika i avtomaticheskoe dokazatelstvo teorem, Nauka, M., 1983, 360 pp.

[6] Boros E., Hammer P. L., “Pseudo-Boolean optimization”, Discrete Appl. Math., 123:1–3 (2002), 155–225 | DOI | MR | Zbl

[7] Feller U., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, v. 1, Mir, M., 1964, 500 pp. | MR

[8] 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

[9] Glover F., Laguna M., Tabu Search, Kluwer Academic Publishers, Norwell, 1997, 401 pp.

[10] Doerr B., Le H., Makhmara R., et al., “Fast genetic algorithms”, Proc. GECCO'17, 2017, 777–784

[11] Pavlenko A., Semenov A., Ulyantsev V., “Evolutionary computation techniques for constructing SAT-based attacks in algebraic cryptanalysis”, LNCS, 11454, 2019, 237–253

[12] Muhlenbein H., “How genetic algorithms really work: Mutation and hill climbing”, Proc. PPSN-II, 1992, 15–26

[13] Wegener I., “Theoretical aspects of evolutionary algorithms”, ICALP 2001, LNCS, 2076, 2001, 64–78 | MR | Zbl

[14] Droste S., Jansen T., Wegener I., “On the analysis of the (1+1) evolutionary algorithm”, Theor. Comput. Sci., 276:1–2 (2002), 51–81 | DOI | MR | Zbl

[15] Luke S., Essentials of Metaheuristics, Second Edition, 2015, 261 pp. https://cs.gmu.edu/s̃ean/book/metaheuristics/Essentials.pdf | MR

[16] Rivest R. L., “The MD4 message digest algorithm”, CRYPTO'90, LNCS, 537, 1990, 303–311

[17] Dobbertin H., “The first two rounds of MD4 are not one-way”, FSE 1998, LNCS, 1372, 1998, 284–292 | Zbl

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

[19] Gribanova I., Semenov A., “Using automatic generation of relaxation constraints to improve the preimage attack on 39-step MD4”, Proc. 41st Intern. Convention, MIPRO 2018 (Opatija, 2018), 1174–1179

[20] Gribanova I. A., Semenov A. A., “Ob argumentatsii otsutstviya svoistv sluchainogo orakula u nekotorykh kriptograficheskikh khesh-funktsii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2019, no. 12, 95–98

[21] Gribanova I. A., Semenov A. A., “Parallel guess-and-determine preimage attack with realistic complexity estimation for MD4-40 cryptographic hash function”, Trudy XIII Mezhdunar. konf. «Parallelnye vychislitelnye tekhnologii» (Kaliningrad, 02–04 aprelya 2019), 8–18

[22] Irkutskii superkompyuternyi tsentr SO RAN, http://hpc.icc.ru