Numerical methods and programming
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Num. Meth. Prog.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Num. Meth. Prog., 2015, Volume 16, Issue 1, Pages 61–77 (Mi vmp519)  

This article is cited in 2 scientific papers (total in 2 papers)

Problems of search for collisions of cryptographic hash functions of the MD family as variants of Boolean satisfiability problem

I. A. Bogachkovaa, O. S. Zaikinb, S. E. Kochemazovb, I. V. Otpushchennikovb, A. A. Semenovb, O. O. Khamisova

a Irkutsk State University
b Matrosov Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences, Irkutsk

Abstract: 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, collisions, differential attacks, Boolean satisfiability problem, SAT, CDCL (Conflict-Driven Clause Learning), parallel SAT solvers.

Full text: PDF file (455 kB)
UDC: 004.056.55, 004.832.25
Received: 18.01.2015

Citation: 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”, Num. Meth. Prog., 16:1 (2015), 61–77

Citation in format AMSBIB
\Bibitem{BogZaiKoc15}
\by I.~A.~Bogachkova, O.~S.~Zaikin, S.~E.~Kochemazov, I.~V.~Otpushchennikov, A.~A.~Semenov, O.~O.~Khamisov
\paper Problems of search for collisions of cryptographic hash functions of the MD family as variants of Boolean satisfiability problem
\jour Num. Meth. Prog.
\yr 2015
\vol 16
\issue 1
\pages 61--77
\mathnet{http://mi.mathnet.ru/vmp519}


Linking options:
  • http://mi.mathnet.ru/eng/vmp519
  • http://mi.mathnet.ru/eng/vmp/v16/i1/p61

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. I. A. Bogachkova, O. S. Zaikin, S. E. Kochemazov, I. V. Otpuschennikov, A. A. Semenov, “Primenenie algoritmov resheniya problemy bulevoi vypolnimosti k kriptoanalizu khesh-funktsii semeistva MD”, PDM. Prilozhenie, 2015, no. 8, 139–142  mathnet  crossref
    2. I. A. Gribanova, “Primenenie algoritmov resheniya problemy bulevoi vypolnimosti k postroeniyu raznostnykh putei v zadachakh poiska kollizii kriptograficheskikh khesh-funktsii semeistva MD”, PDM. Prilozhenie, 2016, no. 9, 129–132  mathnet  crossref
  • Numerical methods and programming
    Number of views:
    This page:114
    Full text:111

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022