Cryptology ePrint Archive: Report 2008/469

Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1

Stephane Manuel

Abstract: In this paper, we present a deterministic algorithm to produce disturbance vectors for collision attacks against SHA-1. We show that all published disturbance vectors can be classified into two types of vectors, type-I and type-II. We define a cost function, close to those described in \cite{Mendel06}, to evaluate the complexity of a collision attack for a given disturbance vector. Using the classification and the cost function we made an exhaustive search which allowed us to retrieve all known vectors. We also found new vectors which have lower cost. This may lead to the best collision attack against SHA-1, with a theoretical attack complexity of $2^{51}$ hash function calls.

Category / Keywords: Hash Functions, SHA-1, Collision Attack, Disturbance Vector.

Date: received 4 Nov 2008

Contact author: stephane manuel at inria fr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20081118:202259 (All versions of this report)

Short URL: ia.cr/2008/469

Discussion forum: Show discussion | Start new discussion