Geodesic
New algorithm for relaxation constrains generation in the inversion problem of MD4-39
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 139-141 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2018},
     number = {11},
     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
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
%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/

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

[2] Wang X., Lai X., Feng D., et al., “Cryptanalysis of the hash functions MD4 and RIPEMD”, LNCS, 3494, 2005, 1–18 | MR | Zbl

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

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

[5] Gribanova I., Zaikin O., Otpuschennikov I., Semenov A., “Using parallel SAT solving algorithms to study the inversion of MD4 hash function”, Proc. Parallel Computational Technologies, 2017, 100–109

[6] Otpuschennikov I. V., Semenov A. A., “Tekhnologiya translyatsii kombinatornykh problem v bulevy uravneniya”, Prikladnaya diskretnaya matematika, 2011, no. 1(11), 96–115

[7] Otpuschennikov I., Semenov A., Gribanova I., et al., “Encoding Cryptographic Functions to SAT Using TRANSALG System”, Proc. ECAI2016 – 22nd Europ. Conf. Artificial Intelligence, Frontiers in Artificial Intelligence and Applications, 285, Hague, 2016, 1594–1595

[8] Glover F., Laguna M., TABU Search, Kluwer, 1999 | MR | Zbl

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