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/