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

Gebhardt, MaxIllies, GeorgSchindler, WernerAlkassar, AmmarSiekmann, Jörg2019-04-032019-04-032008978-3-88579-222-2https://dl.gi.de/handle/20.500.12116/21521This 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].enhash functioncollision pathpostadditionprobabilitystochastic modelOn an Approach to Compute (at least Almost) Exact Probabilities for Differential Hash Collision PathsText/Conference Paper1617-5468