International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Charanjit S. Jutla
Anindya C. Patthak
Download:
URL: http://eprint.iacr.org/2005/266
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2005-12600,
  title={A Matching Lower Bound on the Minimum Weight of SHA-1 Expansion Code},
  booktitle={IACR Eprint archive},
  keywords={Hash Functions, Codes, minimum distance},
  url={http://eprint.iacr.org/2005/266},
  note={ csjutla@us.ibm.com 13008 received 11 Aug 2005, last revised 13 Aug 2005},
  author={Charanjit S. Jutla and Anindya C. Patthak},
  year=2005
}