10
$\begingroup$

It is well-known that SHA1 is broken. Collisions have already been achieved.

Current algorithms for finding collisions leave a “fingerprint” in the collision files, which can easily be detected. It is claimed that brute-force would not be practical, since that would require $2^{80}$ time.

However, I am not so sure if $2^{80}$ time is that impractical. My understanding is that the Bitcoin mining network together generates about $7*2^{89}$ hashes per year. That is enough to break any system with 80 bits of security by sheer brute force. I know that it uses dedicated hardware that cannot be repurposed. But creating such hardware would be well within the capabilities of a nation state. And cryptosystems are supposed to be secure against such adversaries. Furthermore, there are other cryptosystems with 80 bits of security, and some are still being proposed today (!)

Just how feasable is this attack?

Improve this question
$\endgroup$
9
  • $\begingroup$ We know of no such attack (publicly), so while it may be feasible (even for a company like Google if they really cared to do it) it would be a huge investment that would have to pay off. Finding such a target is hard. $\endgroup$
    – SEJPM
    May 4, 2017 at 17:54
  • 6
    $\begingroup$ Well, there is a reason why there isn't a SHA-160 defined in SHA-2. If we would deem a 160 bit hash secure NIST would certainly have defined a length-compatible hash in SHA-2 and 3. $\endgroup$
    – Maarten Bodewes ♦
    May 4, 2017 at 18:33
  • 1
    $\begingroup$ I'd argue that bitcoin isn't a good example, since you can't buy it's time. Take any big computing engine workpower and go with that. Also remember you also need storage, not just workpower. Then you will find that it is unlikely to happen now, but it will happen "soon enough". $\endgroup$
    – axapaxa
    May 4, 2017 at 20:47
  • 3
    $\begingroup$ @axapaxa I believe that the cite of Bitcoin isn't meant as "we can grab the Bitcoin network, and target it at this problem"; it's more "we know that building the size of Bitcoin mining network is feasible, hence we can assume that building a similar network targeted at this problem is also likely feasible" $\endgroup$
    – poncho
    May 4, 2017 at 21:07
  • $\begingroup$ Are you sure about your numbers? I get about $2^{78}$ hashes per day. (Doesn't change much about the validity of your question.) $\endgroup$
    – j.p.
    May 5, 2017 at 8:50

2 Answers 2

Reset to default
5
$\begingroup$

Yes, it is now conceivable to find a SHA-1 collision by brute force.

The general method is outlined in Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, 1999; free earlier version available from the first author's website; expands on an article presented at CACM 1994). It uses local search iterating hashing; when a distinguished value (say with a certain number of zeroes in low-order bits) is found, it is reported to a central location; enough findings lead to a collision. It is expected that less than $2^{82}$ hashes (and comparatively little extra work) are required to find a collision.

By May 2018, the bitcoin mining aggregate hash rate is reportedly $30\cdot10^{18}$ SHA-256d per second ($2^{81.1}$ per day), where SHA-256d uses two SHA-256, and SHA-256 is roughly as costly as SHA-1. The ASICs predominantly used for that can not be directly repurposed for a SHA-1 collision search: they use SHA-256d, not SHA-1; and as an aside they hash incremental values, rather than iterated ones. However the technology is there.

Thus the energy spent in a day of bitcoin mining is enough to find a SHA-1 collision by brute force, hypothesizing the same technology is used. The collision found would be a random one, with chosen prefix decided at start of attack, and could not be detected.

And it might well be that significantly less work would be enough to find a collision that evades detection using the current "fingerprint" method, by using specially crafted (but less efficient) differentials than used to find the first collision reported.

Improve this answer
$\endgroup$
2
$\begingroup$

This paper outlines an implementation that takes 193 CPU cycles/block to compute AES - Let's assume SHA1 is similar Given no vulnerability that breaks SHA1 quicker than the birthday bound, it would take \begin{equation} 1/2 * 2^{80} \end{equation} operations on average to find a collision. Let's be generous and say we can compute SHA1 in 128 cycles: For one hash, this would take \begin{equation} 2^{79}*2^{7} = 2^{86} \end{equation} CPU Cycles. For one 2GHz processor, this operation would take approx. 3.8x10^6 seconds, or roughly 1.24 Billion years.

The Sunway TaihuLight Supercomputer in China (currently largest in the world) has a total of 10,649,600 CPU cores. For this one computer to find a collision in SHA1 would take over 118 years.

It is certainly recommended to use security parameters far above 80 (and also to NOT use SHA1), but this is a lot of work for someone to do to find hack your Nintendo Wii. I don't know what current estimates are for the NSA's computing power, but if you're concerned about nation-state snooping I would recommend a more secure hash function, Keccak / SHA-3 is the current standard, and as high a security parameter as you are willing to put up with in terms of computation speed.

Hope this is helpful :)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.