On an Approach to Compute (at least Almost) Exact Probabilities for Differential Hash Collision Paths

Abstract

This paper presents a new, generally applicable method to compute the probability of given differential (near-)collision paths in Merkle-Damgard-type hash functions. The path probability determines the expected workload to generate a collision (and thus the true risk potential of a particular attack). In particular, if the expected workload appears to be in a borderline region between practical feasibility and non- feasibility (as for SHA-1 collisions, for instance) it is desirable to know these proba- bilities as exact as possible. For MD5 we verified the accuracy of our approach experimentally. Our results underline both that the number of bit conditions only provides a rough estimate for the true path probability and the impact of the IV. An expanded version of this paper can be found online [GIS4].