Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
(Others)
(Others)
Line 65: Line 65:
 
   volume    = {3650},
 
   volume    = {3650},
 
   isbn      = {3-540-29001-X},
 
   isbn      = {3-540-29001-X},
   abstract  = {The cryptanalysis of hash functions has advanced rapidly, and many hash functions have been broken one after another. The most popular hash function SHA-1 has not been broken yet, but the new collision search techniques proposed by Wang et al. reduced the computational complexity down to 269, which is only 1/2,000 of the 280 operations needed for a birthday attack. The complexity is still too large even for today's supercomputers, but no feasibility study of breaking SHA-1 using specialized hardware has been reported. The well known brute force attack on DES simply repeats the DES operation 256 times at a maximum, but the complexity of $2^{69}$ hash operations to break SHA-1 does not mean 269 SHA-1 operations. Complex procedures using SHA-1 functions are required, and the total number of operations based on the probability of a collision occurrence is almost equivalent to the 269 SHA-1 operations. Therefore, we describe a procedure and propose an LSI architecture to find real collisions for SHA-1 in this paper. The hardware core was synthesized by using a 0.13-$\micro m$ CMOS standard cell library, and its performances in speed, size, and power consumption were evaluated. A \$10 million budget can build a custom hardware system that would consist of 303 personal computers with 16 circuit boards each, in which 32 SHA-1-breaking LSIs are mounted. Each LSI has 64 SHA-1 cores that can run in parallel. This system would find a real collision in 127 days.},
+
   abstract  = {The cryptanalysis of hash functions has advanced rapidly, and many hash functions have been broken one after another. The most popular hash function SHA-1 has not been broken yet, but the new collision search techniques proposed by Wang et al. reduced the computational complexity down to $2^{69}$, which is only 1/2,000 of the $2^{80}$ operations needed for a birthday attack. The complexity is still too large even for today's supercomputers, but no feasibility study of breaking SHA-1 using specialized hardware has been reported. The well known brute force attack on DES simply repeats the DES operation 256 times at a maximum, but the complexity of $2^{69}$ hash operations to break SHA-1 does not mean 269 SHA-1 operations. Complex procedures using SHA-1 functions are required, and the total number of operations based on the probability of a collision occurrence is almost equivalent to the 269 SHA-1 operations. Therefore, we describe a procedure and propose an LSI architecture to find real collisions for SHA-1 in this paper. The hardware core was synthesized by using a 0.13-$\micro m$ CMOS standard cell library, and its performances in speed, size, and power consumption were evaluated. A \$10 million budget can build a custom hardware system that would consist of 303 personal computers with 16 circuit boards each, in which 32 SHA-1-breaking LSIs are mounted. Each LSI has 64 SHA-1 cores that can run in parallel. This system would find a real collision in 127 days.},
 
}
 
}
 
</bibtex>
 
</bibtex>

Revision as of 07:16, 11 March 2008

1 Specification

2 Cryptanalysis

2.1 Best Known Results

The best collision attack on full SHA-1 was published by Wang et al. It has complexity of 269 hash evaluations. The best collision example, a 70-step collision for SHA-1, was published by DeCanniere, Mendel and Rechberger.


2.2 Collision Attacks

Christophe De Canni\`ere, Christian Rechberger - Finding SHA-1 Characteristics: General Results and Applications

ASIACRYPT 4284:1-20,2006
http://dx.doi.org/10.1007/11935230_1
Bibtex
Author : Christophe De Canni\`ere, Christian Rechberger
Title : Finding SHA-1 Characteristics: General Results and Applications
In : ASIACRYPT -
Address :
Date : 2006

Vincent Rijmen, Elisabeth Oswald - Update on SHA-1

CT-RSA pp. 58-71,2005
http://dx.doi.org/10.1007/b105222
Bibtex
Author : Vincent Rijmen, Elisabeth Oswald
Title : Update on SHA-1
In : CT-RSA -
Address :
Date : 2005

2.3 Preimage Attacks

  • We are not aware of any articles w.r.t. preimage attacks on SHA-1.

2.4 Others

Akashi Satoh - Hardware Architecture and Cost Estimates for Breaking SHA-1

ISC 3650:259-273,2005
http://dx.doi.org/10.1007/11556992_19
Bibtex
Author : Akashi Satoh
Title : Hardware Architecture and Cost Estimates for Breaking SHA-1
In : ISC -
Address :
Date : 2005

3 eHash Recommendation (optional) or eHash Opinion

Something like: SHA-1 is considered to be broken. Please do not incorporate SHA-1 in new application any longer. Try to migrate to another hash function.