Applications of SAT Solvers to Cryptanalysis of Hash Functions
International Conference on Theory and Applications of Satisfiability Testing (SAT 06) |
Published by Springer
Several standard cryptographic hash functions were broken in 2005. Some essential building blocks of these attacks lend themselves well to automation by encoding them as CNF formulas, which are within reach of modern SAT solvers. In this paper we demonstrate eﬀectiveness of this approach. In particular, we are able to generate full collisions for MD4 and MD5 given only the diﬀerential path and applying a (minimally modiﬁed) oﬀ-the-shelf SAT solver. To the best of our knowledge, this is the ﬁrst example of a SAT-solver-aided cryptanalysis of a non-trivial cryptographic primitive. We expect SAT solvers to ﬁnd new applications as a validation and testing tool of practicing cryptanalysts.