Pages

Wednesday, January 7, 2015

Hash Collisions Reading List

Lately in an effort to code up and properly understand the Wang attack on the MD4 family of hash functions I've been reading a lot of papers on the subject. Many of the papers have very similar names and the same authors. I found myself having to create a quick reference about each paper and it's contents. 

Here they are with a brief summary of what I got from each:





Collision for Hash Functions MD4, MD5 HAVAL-128 and RIPEMD

Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu

https://eprint.iacr.org/2004/199.pdf

This is the original paper listing out some collisions for each of these functions. This must have been quite a blockbuster at the time.




Cryptanalysis of the Hash Functions MD4 and RIPEMD

Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, and Xiuyuan Yu

https://s3-eu-west-1.amazonaws.com/md5collisions/CryptanalysisOftheHashFunctionsMD4andRIPEMD.pdf


This article details the attack that was used to generate the collisions of the previous paper and should be all you need to write a collision generating script for MD4 and RIPEMD.





How to Break MD5 and Other Hash Functions

Xiaoyun Wang and Hongbo Yu

https://s3-eu-west-1.amazonaws.com/md5collisions/HowtoBreakMD5andOtherHashFunctions.pdf

MD5 is slightly harder to break than MD4 requiring 2 blocks and more muli-step message modifications. This article details the method used to generate MD5 collisions in the first.



Searching for Differential Paths in MD4

Martin Schälffer and Elisabeth Oswald

https://s3-eu-west-1.amazonaws.com/md5collisions/SearchingforDifferentialPathsInMD4.pdf


More detail on how the attacks work with a good description of how paths are calculated and an algorithm for finding them. Also contains a new path with fewer stage 2 required requirements.



Improved Collision Attack on MD5

Yu Sasaki, Yusuke Naito, Noboru Kunihiro and Kazuo Ohta

https://s3-eu-west-1.amazonaws.com/md5collisions/ImprovedCollisionAttackonMD5.pdf

The paper where I finally understood how the correction of second round collisions worked



Improved Collision Attack on MD4

Yusuke Naito, Yu Sasaki, Noboru Kunihiro, and Kazuo Ohta


Some corrections to the Wang collision on MD4 speeds things up with good explanation.

Automatic Search of Differential Path in MD4

Pierre-Alain Fouque, Gaëtan Leurent, Phong Nguyen


New Message Difference for MD4

Yu Sasaki, Lei Wang, Kazuo Ohta and Noboru Kunihiro

https://www.iacr.org/archive/fse2007/45930331/45930331.pdf

The best path I know of with a totally different message difference and explanation of the local collisions underlying the collisions.



Herding Hash Functions and the Nostradamus Attack

John Kelsey and Tadayoshi Kohno