Improved Collision Detection of MD5 Using Sufficient Condition Combination

Counter-cryptanalysis uses cryptanalytic techniques to detect cryptanalytic attacks. It was introduced by Stevens with a collision detection algorithm that detects whether a message is one of a colliding message pair constructed using a collision attack. Later, Stevens and Shumow improved the collision detection against SHA-1 by using unavoidable conditions. However, there are no results improving collision detection against MD5 due to its weak diffusion properties. In this paper, an improved collision detection algorithm against MD5 is proposed by using the 14-bit sufficient condition combinations. This leads to the dividing the 223 classes into four sets. Each element, belonging to the first two sets, holds the same sufficient condition combination. Our new algorithm can classify 126 classes efficiently. The runtime is 28.6% of the previous collision detection method.