Cryptology ePrint Archive: Report 2005/266

A Matching Lower Bound on the Minimum Weight of SHA-1 Expansion Code

Charanjit S. Jutla and Anindya C. Patthak

Abstract: Recently, Wang, Yin, and Yu have used a low weight codeword in the SHA-1 message expansion to show a better than brute force method to find collisions in SHA-1. The codeword they used has a (bit) weight of 25 in the last 60 of the 80 expanded words. In this paper we show, using a computer assisted method, that this is indeed the smallest weight codeword. In particular, we show that the minimum weight over GF2 of any non-zero codeword in the SHA-1 (linear) message expansion code, projected on the last 60 words, is at least 25.

Category / Keywords: Hash Functions, Codes, minimum distance

Date: received 11 Aug 2005, last revised 13 Aug 2005

Contact author: csjutla at us ibm com

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

Version: 20050813:210415 (All versions of this report)

Short URL: ia.cr/2005/266

Discussion forum: Show discussion | Start new discussion