4
$\begingroup$

Google today announced they are sunsetting SHA-1. Its fine by me. But that made me realize I am not keeping up with the research on SHA-1. The Wikipedia page only says Stevens' attack is the most efficient but its also on a reduced round SHA-1 - not the SHA-1 with the full rounds. So is there no theoretical attack on SHA-1 or is the one I referred to above enough for it to be considered vulnerable? Are there others?

$\endgroup$
6
$\begingroup$

The cost of finding collision for SHA-1 is currently estimated as $2^{61}$ SHA-1 calls. To understand how much (or how little) it is, we could look at Bitcoin mining. Right now (September 2014) the entire mining network computes 200,000,000 giga-double-hashes of SHA-256 per second, or $2^{61}$ hashes in three seconds.

$\endgroup$
  • $\begingroup$ Giving a rate of 25 BTC every 10 Minutes that would be worth 0.125 Bitcoins (=~ 58.25 $ at the moment) $\endgroup$ – Mouk Sep 10 '14 at 8:23
  • $\begingroup$ Yes, but the problem is that they compute SHA-256, not SHA-1. $\endgroup$ – Dmitry Khovratovich Sep 10 '14 at 11:06
  • $\begingroup$ @DmitryKhovratovich yes but it's just an approximation for how much compute power is needed. $\endgroup$ – immibis Sep 6 '17 at 7:11
3
$\begingroup$

Stevens' attack is on full SHA-1, not a reduced round variant. The differentials are on only part of the rounds, but the attack itself extends to the full algorithm. However, the attack (pdf of full paper) described as "fully working" in the slides you link has still not been used to demonstrate actual collisions, so it's indeed theoretical.

Additionally, even without the attack, it might be time to get rid of SHA-1 in situations where collision attacks are possible. 80 bits of brute force is probably feasible for a very dedicated attacker, either now or in the near future.

Related:

$\endgroup$
  • 1
    $\begingroup$ Thanks! 80 bits of brute force without any weaknesses or optmizations is feasible you think? AES provides 80 bit security. But that is still considered secure. There is no question SHA1 should be retired. $\endgroup$ – user220201 Sep 8 '14 at 21:36
  • $\begingroup$ @user220201 : $\;\;\;$ In what sense does AES provide "80 bit security"? $\:$ Is it the same as the sense in which AES also provides n bit security, for all values of n smaller than 80? $\;\;\;\;\;\;\;$ $\endgroup$ – user991 Sep 8 '14 at 23:08
  • $\begingroup$ Oh! Never mind. I still had SHA1 in mind when I wrote that :) $\endgroup$ – user220201 Sep 9 '14 at 4:16
  • $\begingroup$ @user220201, I'm not sure anyone is doing 80-bit brute force yet, but as shown in the question I linked, it is no longer definitely outside the capabilities of a large adversary. $\endgroup$ – otus Sep 9 '14 at 5:55
  • 1
    $\begingroup$ Stevens' attack closely resembles earlier attacks by Wang's group (which has been also verified by the Austrian group). It is entirely differential-based. There is no "linear attack", there are linear conditions. $\endgroup$ – Dmitry Khovratovich Sep 9 '14 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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