Paper Info
Title
Hardware architecture and cost estimates for breaking SHA-1
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 269 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-μ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.
Year
DOI
Venue
2005
10.1007/11556992_19
ISC
Keywords
Field
DocType
sha-1 function,hash function,sha-1 operation,collision occurrence,sha-1 core,popular hash function sha-1,cost estimate,hardware architecture,computational complexity,real collision,custom hardware system,hash operation,feasibility study,cost estimation
Brute-force attack,SHA-1,Computer science,Parallel computing,Personal computer,Birthday attack,Collision,Hash function,Security of cryptographic hash functions,Hardware architecture,Distributed computing,Embedded system
Conference
Volume
ISSN
ISBN
3650
0302-9743
3-540-29001-X
Citations 
PageRank 
References 
1
0.37
11
Authors
1
Name
Order
Citations
PageRank
Akashi Satoh186669.99