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

Available format(s)
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
See all versions
Short URL
https://ia.cr/2005/266

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},
note = {\url{https://eprint.iacr.org/2005/266}},
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.