Difference between revisions of "SHA-0"

From The ECRYPT Hash Function Website
(Specification)
(Collision Attacks)
Line 19: Line 19:
  
 
=== Collision Attacks ===
 
=== Collision Attacks ===
 +
 +
<bibtex>
 +
@inproceedings{asiacryptNaitoSSYKO06,
 +
  author    = {Yusuke Naito and Yu Sasaki and Takeshi Shimoyama and Jun Yajima and Noboru Kunihiro and Kazuo Ohta},
 +
  title    = {Improved Collision Search for SHA-0},
 +
  pages    = {21-36},
 +
  url        = {http://dx.doi.org/10.1007/11935230_2},
 +
  editor    = {Xuejia Lai and Kefei Chen},
 +
  booktitle = {ASIACRYPT},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4284},
 +
  year      = {2006},
 +
  isbn      = {3-540-49475-8},
 +
  abstract  = {At CRYPTO 2005, Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin proposed a collision attack on SHA-0 that could generate a collision with complexity $2^39$ SHA-0 hash operations. Although the method of Wang et al. can find messages that satisfy the sufficient conditions in steps 1 to 20 by using message modification, it makes no mention of the message modifications needed to yield satisfaction of the sufficient conditions in steps 21 and onwards. In this paper, first, we give sufficient conditions for the steps from step 21, and propose submarine modification as the message modification technique that will ensure satisfaction of the sufficient conditions from steps 21 to 24. Submarine modification is an extension of the multi-message modification used in collision attacks on the MD-family. Next, we point out that the sufficient conditions given by Wang et al. are not enough to generate a collision with high probability; we rectify this shortfall by introducing two new sufficient conditions. The combination of our newly found sufficient conditions and submarine modification allows us to generate a collision with complexity $2^36$ SHA-0 hash operations. At the end of this paper, we show the example of a collision generated by applying our proposals.},
 +
}
 +
</bibtex>
  
 
----
 
----

Revision as of 17:21, 10 March 2008

1 Specification

  • digest size: 160 bits
  • max. message length: < 264 bits
  • compression function: 512-bit message block, 160-bit chaining variable
  • Specification:

2 Cryptanalysis

2.1 Best Known Results


2.2 Generic Attacks


2.3 Collision Attacks

Yusuke Naito, Yu Sasaki, Takeshi Shimoyama, Jun Yajima, Noboru Kunihiro, Kazuo Ohta - Improved Collision Search for SHA-0

ASIACRYPT 4284:21-36,2006
http://dx.doi.org/10.1007/11935230_2
Bibtex
Author : Yusuke Naito, Yu Sasaki, Takeshi Shimoyama, Jun Yajima, Noboru Kunihiro, Kazuo Ohta
Title : Improved Collision Search for SHA-0
In : ASIACRYPT -
Address :
Date : 2006

2.4 Second Preimage Attacks


2.5 Preimage Attacks


2.6 Others