Paper 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.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Unknown where it was published
Keywords
Hash FunctionsCodesminimum distance
Contact author(s)
csjutla @ us ibm com
History
2005-08-13: revised
2005-08-13: received
See all versions
Short URL
https://ia.cr/2005/266
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/266,
      author = {Charanjit S.  Jutla and Anindya C.  Patthak},
      title = {A Matching Lower Bound on the Minimum Weight of {SHA}-1 Expansion Code},
      howpublished = {Cryptology {ePrint} Archive, Paper 2005/266},
      year = {2005},
      url = {https://eprint.iacr.org/2005/266}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.