Gröbner Basis Based Cryptanalysis of SHA-1

Makoto Sugita; Mitsuru Kawazoe; Hideki Imai

Paper 2006/098

Gröbner Basis Based Cryptanalysis of SHA-1

Makoto Sugita, Mitsuru Kawazoe, and Hideki Imai

Abstract

Recently, Wang proposed a new method to cryptanalyze SHA-1 and found collisions of $58$ -round SHA-1. However many details of Wang's attack are still unpublished, especially, 1) How to find differential paths? 2) How to modify messages properly? For the first issue, some results have already been reported. In our article, we clarify the second issue and give a sophisticated method based on Gröbner basis techniques. We propose two algorithm based on the basic and an improved message modification techniques respectively. The complexity of our algorithm to find a collision for 58-round SHA-1 based on the basic message modification is message modifications and its implementation is equivalent to SHA-1 computation experimentally, whereas Wang's method needs SHA-1 computation. We propose an improved message modification and apply it to construct a more sophisticated algorithm to find a collision. The complexity to find a collision for 58-round SHA-1 based on this improved message modification technique is message modifications, but our latest implementation is very slow, equivalent to SHA-1 computation experimentally. However we conjecture that our algorithm can be improved by techniques of error correcting code and Gröbner basis. By using our methods, we have found many collisions for -round SHA-1.

Metadata

Available format(s): PDF PS
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Keywords: hash function SHA-1 Gaussian elimination Gröbner basis
Contact author(s): m-sugita @ ipa go jp
History: 2006-07-07: revised; 2006-03-19: received; See all versions
Short URL: https://ia.cr/2006/098
License: CC BY

BibTeX

@misc{cryptoeprint:2006/098,
      author = {Makoto Sugita and Mitsuru Kawazoe and Hideki Imai},
      title = {Gröbner Basis Based Cryptanalysis of {SHA}-1},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/098},
      year = {2006},
      url = {https://eprint.iacr.org/2006/098}
}