Geodesic
New algorithm for relaxation constrains generation in the inversion problem of~MD4-39
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 139-141

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

The paper presents the preimage attack on 39-step variant of the MD4 cryptographic hash-function (MD4-39) using new approach which can be considered as a development of the ideas proposed earlier by H. Dobbertin. Particularly, we search for special relaxation constraints which are used to simplify the equations corresponding to the problem of finding a preimage for a random MD4-39 hash value. These equations supplemented with the relaxation constraints are reduced to the Boolean Satisfiability Problem (SAT) and then solved using the SAT solvers. We suggest a new method for automatic generation of relaxation constraints by applying the black-box optimization to the function of a special kind, which evaluates the effectiveness of a set of relaxation constraints. The proposed method allows to find new relaxation constraints using which we manage to construct preimage attack on MD4-39 which in dozens of times outperforms the best known attack for considered function.
Keywords: cryptographic hash functions, inversion problem of hash functions, SAT.
Mots-clés : MD4, MD4-39 
@article{PDMA_2018_11_a42,
     author = {I. A. Gribanova},
     title = {New algorithm for relaxation constrains generation in the inversion problem {of~MD4-39}},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {139--141},
     publisher = {mathdoc},
     number = {11},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2018_11_a42/}
}
TY  - JOUR
AU  - I. A. Gribanova
TI  - New algorithm for relaxation constrains generation in the inversion problem of~MD4-39
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2018
SP  - 139
EP  - 141
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2018_11_a42/
LA  - ru
ID  - PDMA_2018_11_a42
ER  - 
%0 Journal Article
%A I. A. Gribanova
%T New algorithm for relaxation constrains generation in the inversion problem of~MD4-39
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2018
%P 139-141
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a42/
%G ru
%F PDMA_2018_11_a42
I. A. Gribanova. New algorithm for relaxation constrains generation in the inversion problem of~MD4-39. Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 139-141. http://geodesic.mathdoc.fr/item/PDMA_2018_11_a42/