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

Charanjit S.  Jutla; Anindya C.  Patthak

Paper 2005/266 Original: eprint.iacr.org/2005/266 ↗

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

Charanjit S. Jutla

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
Publication info: Preprint.
History: 2005-08-13: last updated; 2005-08-13: published
Short URL: https://ia.cr/2005/266
License: https://creativecommons.org/licenses/by/4.0/

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}
}