SCHOOL OF COMPUTER SCIENCE – Colloquium Series
The School of Computer Science at the University of Windsor is pleased to present…
Colloquium Presentation by Dr. Oleg Zaikin
Abstract:
MD4 and MD5 are prominent cryptographic hash function proposed in the early 1990s. MD4 consists of 48 steps and produces a hash of size 128 bits given a message of an arbitrary finite size. MD5 isa strengthened 64-step version of MD4. Both MD4 and MD5 are vulnerable to practical collision attacks, yet it is still not realistic toinvert them, i.e. to find a message given a hash. In 2007, the truncated 39-step version of MD4 was inverted for one specified hash via reducing to the Boolean satisfiability problem (SAT) and applying a Conflict-Driven Clause Learning (CDCL) solver. As for MD5, in 2012 its truncated 28-step version was inverted for one specified hash via a CDCL solver. Until recently, these results were state of the art. This talk will reveal how 40-, 41-, 42-, and 43-step MD4 can be inverted via the Cube-and-Conquer approach (a combination of CDCL and lookahead). Also, by applying the same approach, 28-step MD5 is inverted for three more specified hashes compared to the paper from 2012.
Keywords: artificial intelligence, automated reasoning, SAT, Cube-and-Conquer, cryptographic hash function, cryptanalysis
Biography:
Dr. Oleg Zaikin is a leading researcher at Matrosov Institute for System Dynamics and Control Theory, a research institute of the Russian Academy of Sciences. His PhD was dedicated to SAT-based cryptanalysis of stream ciphers. Then he was a research assistant at the Computer Science Department of Swansea University, United Kingdom, where he applied Cube-and-Conquer to find new combinatorial designs based on Latin squares. Currently, his research is mainly focused on applying Cube-and-Conquer to hard cryptanalysis and combinatorial problems.
5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716 csgradinfo@uwindsor.ca