International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A New Collision Differential For MD5 With Its Full Differential Path

Authors:
Tao Xie
DengGuo Feng
FanBao Liu
Download:
URL: http://eprint.iacr.org/2008/230
Search ePrint
Search Google
Abstract: Since the first collision differential with its full differential path was presented for MD5 function by Wang et al. in 2004, renewed interests on collision attacks for the MD family of hash functions have surged over the world of cryptology. To date, however, no cryptanalyst can give a second computationally feasible collision differential for MD5 with its full differential path, even no improved differential paths based on Wangs MD5 collision differential have appeared in literature. Firstly in this paper, a new differential cryptanalysis called signed difference is defined, and some principles or recipes on finding collision differentials and designing differential paths are proposed, the signed difference generation or elimination rules which are implicit in the auxiliary functions, are derived. Then, based on these newly found properties and rules, this paper comes up with a new computationally feasible collision differential for MD5 with its full differential path, which is simpler thus more understandable than Wangs, and a set of sufficient conditions considering carries that guarantees a full collision is derived from the full differential path. Finally, a multi-message modification-based fast collision attack algorithm for searching collision messages is specialized for the full differential path, resulting in a computational complexity of 2 to the power of 36 and 2 to the power of 32 MD5 operations, respectively for the first and second blocks. As for examples, two collision message pairs with different first blocks are obtained.
BibTeX
@misc{eprint-2008-17907,
  title={A New Collision Differential For MD5 With Its Full Differential Path},
  booktitle={IACR Eprint archive},
  keywords={foundations / MD5 / differential cryptanalysis / collision attacks / collision differential / differential path design},
  url={http://eprint.iacr.org/2008/230},
  note={Not published elsewhere. hamishxie@vip.sina.com 14019 received 20 May 2008},
  author={Tao Xie and DengGuo Feng and FanBao Liu},
  year=2008
}