Paper 2014/239

Logical Reasoning to Detect Weaknesses About SHA-1 and MD4/5

Florian Legendre, Gilles Dequen, and Michaël Krajecki

Abstract

In recent years, studies about the SATisfiability Problem (short for SAT) were more and more numerous because of its conceptual simplicity and ability to express a large set of various problems. Within a practical framework, works highlighting SAT impli- cations in real world problems had grown significantly. In this way, a new field called logical cryptanalysis appears in the 2000s and consists in an algebraic cryptanalysis in a binary context thanks to SAT solving. This paper deals with this concept applied to cryptographic hash functions. We first present the logical cryptanalysis principle, and provide details about our encoding approach. In a second part, we put the stress on the contribution of SAT to analyze the generated problem thanks to the discover of logical inferences and so simplifications in order to reduce the computational complexity of the SAT solving. This is mainly realized thanks to the use as a preprocessor of learning and pruning techniques from the community. Third, thanks to a probabilistic reasoning applied on the formulas, we present a weakness based on the use of round constants to detect probabilistic relations as implications or equivalences between certain vari- ables. Finally, we present a practical framework to exploit these weaknesses through the inversions of reduced-step versions of MD4, MD5, SHA-0 and SHA-1 and open some prospects.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
hash functionsone-way functionscryptanalysis
Contact author(s)
gilles dequen @ u-picardie fr
History
2014-04-15: received
Short URL
https://ia.cr/2014/239
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/239,
      author = {Florian Legendre and Gilles Dequen and Michaël Krajecki},
      title = {Logical Reasoning to Detect Weaknesses About SHA-1 and MD4/5},
      howpublished = {Cryptology ePrint Archive, Paper 2014/239},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/239}},
      url = {https://eprint.iacr.org/2014/239}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.