2012 · 16 citations · 12 references
ComputingComputer ScienceMathematicsAlgorithmsCryptographyTheory Of ComputationCryptographic AlgorithmsCryptographic ComplexityCryptographic HashingHash FunctionsBoolean Satisfiability ProblemCryptanalysisHash Function AttacksHash Function CryptanalysisPropositional EncodingSat AttacksSatisfiabilitySatisfiability Problem
The SATisfiability Problem is a core problem in mathematical logic and computing theory. In the last years, progresses have led it to be a great and competitive approach to practically solve a wide range of industrial and academic problems. Thus, the current SAT solving capacity allows the propositional formalism to be an interesting alternative to tackle cryptographic problems, and particularly introduced a new field called logical cryptanalysis [15]. This paper deals with an original application of the SAT problem to encode the well-known MD? and SHA? hash functions algorithm in a generic DIMACS formula. As cryptographic hash functions are central elements in modern cryptography we choose to validate our modelisation with a dedicated attack on the inversion of these functions. This attack behaves like a reverse-engineering process, thanks to a state of the art SAT solver achieving a weakening of the second preimage of MD? and SHA?. As a result, we present our modelisation and an improvement of the current limit of best practical attacks on step-reduced MD4, MD5 and SHA? inversions, respectively up to 39, 28 and 23 broken steps. Finally, a brief analyse of our results allows to give an idea about logical cryptanalysis and hash functions.
12
A machine program for theorem-proving
Martin Davis, George Logemann, Donald Loveland · Communications of the ACM · 1962 · 3.2K citations · Full text
Differential cryptanalysis of DES-like cryptosystems
Eli Biham, Adi Shamir · Journal of Cryptology · 1991 · 2.9K citations
GRASP - A New Search Algorithm for Satisfiability
1996 · 860 citations
Efficient Conflict Driven Learning in a Boolean Satisfiability Solver
2001 · 666 citations