Further Musings on the Wang et al. MD5 Collision: Improvements and Corrections on the Work of Hawkes, Paddon,

Abstract. The recent successful attack on the widely used hash function, the MD5 Message Digest Algorithm, was a breakthrough in cryptanalysis. The original paper, published in 2004 by Wang et al., described this attack in an obscure and elliptical manner. Hawkes, Paddon, and Rose subsequently presented the attack in more detail, but even their paper contained numerous unproven statements and several significant errors. In a seven-step process, this paper will explicate their work, prove many of their assertions, and provide original corrections and illustrations to make the differential attack on MD5 more accessible to the mathematically literate reader. First, this paper will augment their introductory material by comparing their unorthodox description of MD5 to the original notation of Ron Rivest. Second, it will provide original examples for conditions that they present for the Tt. Third, it will elaborate on the description of the first block of the differential, showing why and how the conditions on the Tt are determined. Fourth, it will develop a step by step analysis of the description of the second block of the differential based only on the table that Hawkes, Paddon, and Rose provide. Fifth, it will supply original proofs of their assertions regarding the conditions for the propagation of the differences through the ft functions for the first block. Sixth, it will give both assertions and proofs for the propagation of the differences through the ft functions for the second block. Finally, it will correct two significant errors in the work of Hawkes, Paddon, and Rose. It will demonstrate that the complexity of the attack is only about half as great as they believed, and it will show that their Case Two does not succeed in fulfilling the conditions required for the collision differential to hold