Paper 2004/325

Complexity of the Collision and Near-Collision Attack on SHA-0 with Different Message Schedules

Mitsuhiro HATTORI, Shoichi HIROSE, and Susumu YOSHIDA

Abstract

SHA-0 employs a primitive polynomnial of degree 16 over GF(2) in its message schedule. There are 2048 primitive polynomials of degree 16 over GF(2). For each primitive polynomial, a SHA-0 variant can be constructed. In this paper, the security of 2048 variants is analyzed against the Chabaud-Joux attack proposed in CRYPTO'98. The analysis shows that all the variants could be collision-attacked by using near-collisions as a tool and thus the replacement of the primitive polynomial is not a proper way to make SHA-0 secure. However, it is shown that the selection of the variants highly affects the complexity of the attack. Furthermore, a collision in the most vulnerable variant is presented. It is obtained by the original Chabaud-Joux attack without any improvements.

Note: The result of the near-collision attack (Table 6) is corrected.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
hash functionsSHA-0collision attacknear-collision attack
Contact author(s)
hattori @ hanase kuee kyoto-u ac jp
History
2005-02-14: revised
2004-11-26: received
See all versions
Short URL
https://ia.cr/2004/325
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/325,
      author = {Mitsuhiro HATTORI and Shoichi HIROSE and Susumu YOSHIDA},
      title = {Complexity of the Collision and Near-Collision Attack on {SHA}-0 with Different Message Schedules},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/325},
      year = {2004},
      url = {https://eprint.iacr.org/2004/325}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.