Open AccessImproved collision detection of MD5 with additional sufficient conditions
Author(s) -
Linan Fang,
Tung Ying Wu,
Yongxing Qi,
Yanzhao Shen,
Peng Zhang,
Mingmin Lin,
Xinfeng Dong
Publication year - 2022
Publication title -
electronic research archive
Language(s) - English
Resource type - Journals
ISSN - 2688-1594
DOI - 10.3934/era.2022102
Subject(s) - md5 , collision , computer science , cryptanalysis , differential (mechanical device) , algorithm , collision attack , collision detection , hash function , cryptographic hash function , cryptography , computer security , engineering , double hashing , aerospace engineering
One application of counter-cryptanalysis is detecting whether a message block is involved in a collision attack, such as the detection of MD5 and SHA-1. Stevens and Shumow speeded up the detection of SHA-1 by introducing unavoidable conditions in message blocks. They left a challenge: how to determine unavoidable conditions for MD5. Later, Shen et al. found that the unavoidable conditions of MD5 were the sufficient conditions located in the last round of differential paths. In this paper, we made further work. We discover sufficient conditions in the second round that can also be used as unavoidable conditions. With additional sufficient conditions, we subdivide three sets and distinguish seven more classes. As a result, compared with Shen's collision detection algorithm, our improved algorithm reduces the collision detection cost by 8.18%. Finally, we find that they do exist in the differential paths constructed by the automatic tool "HashClash".