Paper 2007/375

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

Gregory Hirshman

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 later presented the attack in more detail, but even their paper contained numerous unproven statements and several significant errors. In a seven-fold process, this paper will prove assertions made by Hawkes, Paddon, and Rose, provide original corrections and illustrations, and explicate their work to make it more accessible to the mathematically literate reader. First, this paper will augment their introductory material by adding original insight to compare their unorthodox description of MD5 to the more conventional 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 by asserting 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 the table that Hawkes, Paddon, and Rose provide. Fifth, it will supply original proofs for the assertions that they make for the conditions for the propagation of the differences through the ft functions for the first block. Sixth, it will give both the assertions and the 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, demonstrating that the complexity of the attack is only about half of what they stated it to be and that their Case Two does not succeed in fulfilling the conditions required for the collision differential to hold.