11
$\begingroup$

Presently 160 bits of hash block width seems to provide adequate security against brute force attacks. The recent developments concerning SHA-1 have reduced the effort to force collisions by 5 orders of magnitude according to the latest Wikipedia edit.

Other cryptographic primitives have been evolved to fix issues that were similarly found, such as:-

  • RSA -> increasing bit count
  • RC4 -> RC4A -> Spritz
  • Whirlpool0 -> WhirlpoolT -> Whirlpool

I'm specifically using the term fix, to mean keeping the SHA-1 160 bit essentials and making internal changes /improvements. So some (but not limited to) changes might be:-

  • amending the round count with perhaps double rounds to tie in with the existing key schedule as 80 x 2 instead of 80 x 1
  • changes to key schedule to increase rounds directly
  • something akin to internalising SHA-1(SHA-1(message))
  • additional bit wise operations

Hopefully you get the idea. Why can't we do this so that it forms a plug in upgrade whereby the existing block size can be kept? My intention is to easily prolong the life of SHA-1 in existing code and data bases without huge and far reaching programmatic changes. I realise that 160 bits will someday become insecure requiring it's ultimate replacement by a wider hash.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ "Presently 160 bits of hash block width seems to provide adequate security " there are many who would disagree, including the US government, by and for whom the hash standard was created, as they now require 112 bits of security $\endgroup$
    – Richie Frame
    May 3, 2017 at 0:11
  • $\begingroup$ Maybe a better question would be to argue that an exploit that is visible is for the most part desired more than a cryptographic-unknown? $\endgroup$
    – Q-Club
    May 3, 2017 at 0:16
  • 1
    $\begingroup$ These break your code because all your existing hashes won't match, so in what way is it a plug-in upgrade? $\endgroup$
    – user253751
    May 4, 2017 at 3:15
  • 1
    $\begingroup$ If you need a 160-bit hash just use SHA256/SHA3 and take the first 160 bits. $\endgroup$
    – user253751
    May 4, 2017 at 3:16
  • $\begingroup$ @back_seat_driver Do you mean so that you'll know exactly where the weakness lies? $\endgroup$
    – Paul Uszak
    May 4, 2017 at 11:29

2 Answers 2

Reset to default
27
$\begingroup$

I have 3 answers: We can't fix SHA-1, we shouldn't fix SHA-1 and we already did fix SHA-1. SHA-1 is a hash standard; many different people can and have implemented it and they all get the same results. SHA-1 is broken. We have to replace it and convince everybody to move on to a new standard. A fixed SHA-1 wouldn't be SHA-1. We shouldn't try a minimal fix; we should build the best (fastest, most secure) hash algorithm we can. A minimal fix will keep us with the problematic basic structure of SHA-1. If are switching, we want something which will be secure for many years to come. And be as efficient as possible.

That said, we already fixed it. It's called hardened SHA-1; it is immune to the known and similar collision attacks and it is even backwards compatible with SHA-1, sort of. It detects patterns which will occur in a collision attack and are very rare in random data. Hardened SHA-1 is identical to SHA-1 on almost any input, yet won't be the same and an infinitesimally small portion of inputs we see in collision attacks of the class published.

However though there are no currently known attacks on hardened SHA-1 and it isn't much slower. Nobody has the illusion SHA-1 has competitive security with SHA-2 or SHA-3. Even if you need to truncate to 160 bits, these are probably safer options. If you must have backwards compatibility as a quick fix, Hardened SHA-1 is a great trick but you should make plans to switch to SHA-3

Improve this answer
$\endgroup$
3
  • $\begingroup$ "We shouldn't try a minimal fix, we should build the best (fastest, most secure) hash algorithm we can." I'd argue the slowest hash algorithm is the most secure. $\endgroup$
    – Q-Club
    May 3, 2017 at 5:23
  • 27
    $\begingroup$ @back_seat_driver Slowness is not a property you would want for a generic secure hash construction. You don't want file verification or signature verification to take ages. Slowness can be a good property of password hashes (or rather PBKDF's), which have other requirements altogether - mainly key strengthening - which are completely off topic for a generic secure hash. $\endgroup$
    – Maarten Bodewes ♦
    May 3, 2017 at 8:06
  • 3
    $\begingroup$ I guess that in your 2nd paragraph you speak about Marc Stevens' Counter-Cryptanalysis, the "best young author paper" from Crypto 2013. Here a link for who doesn't know it: ia.cr/2013/358 $\endgroup$
    – j.p.
    May 3, 2017 at 8:36
23
$\begingroup$

We can fix SHA-1 but why?

SHA-1 is broken. We cannot fix it without modifying result (so compability won't be preserved). We can make changes that will fix it... for now, and also will make it inefficient. What are gains? That perhaps implementation will be somewhat easier... That is not much for fixing something that has only 160bit security and something that will be very inefficient.

Presently 160 bits of hash block width seems to provide adequate security against brute force attacks.

Presently is important word here. We assume it might not be true in future.

Other cryptographic primitives have been evolved to fix issues that were similarly found

RSA is wrong example here, since we don't change anything other than we assumed will differ. There are algorithms with tweakable security parameters, but SHA-1 is not one of them.

Spritz and Whirlpool were fixed, but keep in mind that neither is mainstream algorithm, unlike SHA-2 and SHA-3. This is because they are inefficient and not well studied.

Also keep in mind how RC4 was broken. At first key could be recovered from first 1024 bytes of cipherstream, so people started rejecting it. It worked for some time except it was broken more severely after that. Why would we patch insecure algorithm to hopefully make it secure? Better start from scratch learning from previous mistakes.

There are some attempts to make algorithms future-proof by making security parameters tweakable (SHA-3/Keccak, Salsa/Chacha), but I can see two major drawbacks of such thing (but maybe in future we can use their properties to fix them if they get broken):

  • If algorithm is broken, then probably we have to increase security parameters over efficiency, because original construction has diffusion problems etc.
  • It's hard to make efficient implementation for very tweakable algorithms.
Improve this answer
$\endgroup$
9
  • $\begingroup$ I understand, but your compatibility preservation argument is invalid. Function replacement with a larger block width (say SHA -3) is even more incompatible as you also have to change large parts of code /database fields/ GUIs, over and above modified results. $\endgroup$
    – Paul Uszak
    May 3, 2017 at 14:00
  • 4
    $\begingroup$ @PaulUszak Functions using SHA-1 would have to change anyway, to use "SHA-1-new" or whatever you called it (unless you fancied really confusing everyone into not knowing which algorithm they were using). The block size is just an internal detail, and would require no changes to storage or UI; the incompatible change in switching to SHA-3 is that the output size is larger. If that was a big problem, you might be able to make an algorithm stronger than SHA-1, but still with a 160-bit output, but there would be no reason to model it on SHA-1, rather than a newer approach. $\endgroup$
    – IMSoP
    May 3, 2017 at 15:36
  • $\begingroup$ @PaulUszak I agree with IMSoP. You can cast SHA-3 to 160bit output but perhaps worse problem is that you assume that your hash is always 160bit in DB/UI, because this is design without foresight. No matter how great your hash function is, 160bit is NOT good enough for far future and you will end up changing large parts of code anyway soon enough. Simply said, that's poor design of DB/UI/Code. $\endgroup$
    – axapaxa
    May 3, 2017 at 16:25
  • 1
    $\begingroup$ @PaulDraper 80-bit security for birthday attack without quantum computer, which is close to broken by now. 40-bit security with quantum computer which is trivially broken. There is reason why SHA-1 was deprecated before it was broken and new ciphers use at least 256bit, but even as much as 512bits. 512-bit hash /4 = 128-bit birthday attack security with quantum computer which is fairly secure. $\endgroup$
    – axapaxa
    May 3, 2017 at 18:47
  • 3
    $\begingroup$ @IMSoP No reason to model it on SHA-1? Pff, the solution OBVIOUSLY is to start running SHA-1 on your data 3 times! I shall call it Triple SHA-1, or 3SHA-1 for short. $\endgroup$
    – Aron
    May 4, 2017 at 9:49

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.