Geodesic
Problems of search for collisions of cryptographic hash functions of the MD family as variants of Boolean satisfiability problem
Numerical methods and programming, Tome 16 (2015) no. 1, pp. 61-77

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

An implementation of the differential attacks on cryptographic hash functions MD4 (Message Digest 4) and MD5 (Message Digest 5) by reducing the problems of search for collisions of these hash functions to the Boolean satisfiability problem (SAT) is considered. The novelty of the results obtained consists in a more compact (compared to already known) SAT encodings for the algorithms considered and in the use of modern parallel and distributed SAT solvers in applications to the formulated SAT problems. Searching for single block collisions of MD4 in this approach turned out to be very simple. In addition, several dozens of double block collisions of MD5 are found. In the process of the corresponding numerical experiments, a certain class of messages that produce the collisions is found: in particular, a set of pairs of such messages with first 10 zero bytes is constructed.
Keywords: CDCL (Conflict-Driven Clause Learning), cryptographic hash functions, differential attacks, Boolean satisfiability problem, SAT, CDCL (Conflict-Driven Clause Learning), parallel SAT solvers.
Mots-clés : collisions 
@article{VMP_2015_16_1_a6,
     author = {I. A. Bogachkova and O. S. Zaikin and S. E. Kochemazov and I. V. Otpushchennikov and A. A. Semenov and O. O. Khamisov},
     title = {Problems of search for collisions of cryptographic hash functions of the {MD} family as variants of {Boolean} satisfiability problem},
     journal = {Numerical methods and programming},
     pages = {61--77},
     publisher = {mathdoc},
     volume = {16},
     number = {1},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMP_2015_16_1_a6/}
}
TY  - JOUR
AU  - I. A. Bogachkova
AU  - O. S. Zaikin
AU  - S. E. Kochemazov
AU  - I. V. Otpushchennikov
AU  - A. A. Semenov
AU  - O. O. Khamisov
TI  - Problems of search for collisions of cryptographic hash functions of the MD family as variants of Boolean satisfiability problem
JO  - Numerical methods and programming
PY  - 2015
SP  - 61
EP  - 77
VL  - 16
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMP_2015_16_1_a6/
LA  - ru
ID  - VMP_2015_16_1_a6
ER  - 
%0 Journal Article
%A I. A. Bogachkova
%A O. S. Zaikin
%A S. E. Kochemazov
%A I. V. Otpushchennikov
%A A. A. Semenov
%A O. O. Khamisov
%T Problems of search for collisions of cryptographic hash functions of the MD family as variants of Boolean satisfiability problem
%J Numerical methods and programming
%D 2015
%P 61-77
%V 16
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMP_2015_16_1_a6/
%G ru
%F VMP_2015_16_1_a6
I. A. Bogachkova; O. S. Zaikin; S. E. Kochemazov; I. V. Otpushchennikov; A. A. Semenov; O. O. Khamisov. Problems of search for collisions of cryptographic hash functions of the MD family as variants of Boolean satisfiability problem. Numerical methods and programming, Tome 16 (2015) no. 1, pp. 61-77. http://geodesic.mathdoc.fr/item/VMP_2015_16_1_a6/