Classification and generation of disturbance vectors for collision attacks against SHA-1
The main contribution of this paper is to provide a classification of disturbance vectors used in differential collision attacks against. We show that all published disturbance vectors can be classified into two types of vectors, type-I and type-II. We present a deterministic algorithm which produce efficient disturbance vectors with respect to any given cost function. We define two simple cost functions to evaluate the efficiency of a candidate disturbance vector. Using our algorithm and those cost function we retrieved all previously known vectors and found that the most efficient disturbance vector is the one first reported as Codeword2 by Jutla and Patthak, A matching lower bound on the minimum weight of SHA-1 expansion code. Cryptology ePrint Archive, Report 2005/266, (2005). We also present a statistical evaluation of local collisions' holding probabilities and show that the common assumption of local collision independence is flawed.
disturbance vector collision attack sha-1 local collisions independence hash functions