Classification and generation of disturbance vectors for collision attacks against SHA-1 (Q2430693)

The main contribution is a classification (type-I/type-II) of all published disturbance vectors used in differential collision attacks against SHA-1. A deterministic algorithm is presented which produces efficient disturbance vectors with respect to any given cost function. Two simple cost functions are defined to evaluate the efficiency of a candidate disturbance vector. Using this algorithm and these cost functions, all previously known vectors are retrieved and it is found that the most efficient disturbance vector is the one first reported as Codeword2 by Jutla and Patthak. Moreover, a statistical evaluation of local collision's holding probabilities is presented and it is shown that the common assumption of local collision independence is flawed.