9
$\begingroup$

On the Wikipedia page of SHA-2, the following is written:

Currently, the best public attacks break preimage resistance for 52 out of 64 rounds of SHA-256 or 57 out of 80 rounds of SHA-512, and collision resistance for 46 out of 64 rounds of SHA-256.

Can someone explain in simple terms what that means?

Also, for SHA-1, the Wikipedia page currently states:

Since 2005, SHA-1 has not been considered secure against well-funded opponents;[4] as of 2010 many organizations have recommended its replacement.[5][6][7] NIST formally deprecated the use of SHA-1 in 2011 and disallowed its use for digital signatures in 2013. As of 2020, chosen-prefix attacks against SHA-1 are practical.[8][9] As such, it is recommended to remove SHA-1 from products as soon as possible and instead use SHA-2 or SHA-3. Replacing SHA-1 is urgent where it is used for digital signatures.

All major web browser vendors ceased acceptance of SHA-1 SSL certificates in 2017.[10][11][12] In February 2017, CWI Amsterdam and Google announced they had performed a collision attack against SHA-1, publishing two dissimilar PDF files that produced the same SHA-1 hash.[13][2] But SHA-1 is still secure for HMAC.[14]

Microsoft has discontinued SHA-1 code signing support for Windows Update on August 7, 2020.

So, ten years after the original publication, the hash algorithm already wasn't deemed secure enough to be trusted anymore.

SHA-2 was published in 2001. Given the advancements in computing power, does it even make sense to use SHA-2 in new technology? Isn't it reasonable to expect that very soon it won't be trustworthy anymore, seeing how SHA-1 wasn't trustworthy after ten years? Shouldn't we use SHA-3-512 wherever possible to be on the safe side looking forward?

$\endgroup$

1 Answer 1

11
$\begingroup$

AES-128 (2000) has been around for 20 years and there is no attack faster than brute-force, except the multi-target that affects all block ciphers and hash algorithms. As you can see, an algorithm can withstand attacks for a long time with a good design.

SHA-1 (1995) has 160-bit output, which results in 80-bit generic collision resistance. It was good for the 1990s. The NIST removed it from signatures in 2013. Today, this is already low, by today's standards where it is considered that we need at least 112-bit security. The chosen prefix-collision attack on SHA-1 (2017) is faster than the generic collision attack; it is faster 100,000s ($\approx 2^{16}$) of times. Maybe in the future, one can present faster collision findings like MD5's imminent collision findings, we don't know.

Now, SHA-256 (2001) has 128-bit generic collision resistance with a 50% probability under the birthday attack. The 128-bit is not easily accessible. The public example is the Bitcoin Miners that they can collectively reach $2^{92}$ double SHA-256 hashes per-year (it is almost $2^{93}$ after two years). Therefore they need $2^{36}$-year to find a collision with 50% probability.

SHA-512 (2001), on the other hand, has 256-bit generic collision resistance. 256 bit is not vulnerable.

SHA-3-512 has the same generic collision resistance as the SHA-512. The main differences are these; the SHA-3 series uses sponge construction and has resistance to length-extension attack whereas the SHA-2 series uses MD construction and if not trimmed, they have no length-extension resistance.

There is also a quantum attack side of the story like the work of Brassard et. al dropped collision finding into the $\mathcal{O}(2^{n/3})$-time and requiring $\mathcal{O}(2^{n/3})$ storage in the total cost of $\mathcal{O}(2^{2n/3})$. This and other quantum attacks are theoretical and should not be considered a real threat. Actually, they are not better than classical algorithms like the parallel $\rho$ based collision search algorithm of Van Oorschot and Wiener based has $\mathcal{O}(2^{n/2})$. See in details in this answer

So, like 10 years after the original publication, the hash algorithm already wasn't deemed secure enough anymore to be trusted.

NIST and the designers of the SHA series (except SHA3) has come from a long way to design a better hash algorithm from the MD5 and earlier MD hashes, SHA-0, & SHA-1. We don't compare something by saying that if $x$ was broken in $y$ years then since $z$ is $y$ years old it must no longer be secure. We compare according to published attacks. SHA-256 has been there for almost 20 years withstanding the classical attacks. Yet no problem seems on the horizon. If you want to be secure for the foreseeable future use SHA-512, besides it has 64-bit CPU support ( SHA-256 has 32-bit CPU support).

SHA-2 was published in 2001, given the advancements in computing power, does it even make sense to use SHA-2 in new technology? Isn't it reasonable to expect that very soon it won't be trustworthy anymore, seeing how SHA-1 wasn't trustworthy anymore 10 years after inception? Shouldn't we use SHA-3-512 wherever possible to be on the safe side looking forward?

The computing power has limits. We have already seen that reaching $2^{100}$ is not easy, and $2^{128}$ has a long time to be secure for direct brute-force.

If there are no new attacks that are going to be performed and much better than the SHA-1's attacks on SHA-2, then there is no problem for the SHA-2 family. However, we always assume that the attacks always become better, not worse.

Conclusion:

Normally SHA-256 is fine with 32-bit CPUs; 128-bit is classically impossible to break. To take the advantage of 64-bit CPUs use SHA-512. Similarly, you can use SHAKE128/256 and BLAKE2 that has both 32 and 64-bit CPU designs. To take advantage of parallel hashes use ParallelHash (parallel version for SHA-3) and BLAKE3 (parallel).

Currently, the best public attacks break preimage resistance for 52 out of 64 rounds of SHA-256 or 57 out of 80 rounds of SHA-512, and collision resistance for 46 out of 64 rounds of SHA-256.

This is the short story of the big picture

  • The cost for 52 out of 64 round pre-image attacks of SHA-256 is $2^{255}$
  • The cost for 57 out of 80 round pre-image attacks of SHA-512 is $2^{511}$

These attacks are on the reduced round of the SHA-256 and SHA-512, i.e. if the SHA-256 uses 52 rounds then the cost of finding pre-images will be $2^{255}$ instead of $2^{256}$ and even on average you will find the pre-image with brute-force with $2^{255}$-time

As we can see, the cost is already far from reachable. While reading an attack in hash functions one must look at all requirements; the complexity compared to generic attack, the memory requirements, possible reduced rounds, or the success of the attack on how many rounds.

$\endgroup$
8
  • $\begingroup$ @matthias_buehlmann You will have noticed that your first question has been avoided completely so far, and the given response starts with the topic of AES-128 (2000), which is not to the point. $\endgroup$
    – Patriot
    Jan 26, 2021 at 20:12
  • 1
    $\begingroup$ @Patriot are you talking about "Can someone explain in simple terms what that means?" this? $\endgroup$
    – kelalaka
    Jan 26, 2021 at 20:17
  • $\begingroup$ Yes, that is it. $\endgroup$
    – Patriot
    Jan 26, 2021 at 20:24
  • $\begingroup$ @Patriot It is the end of the answer; The cost of reduced rounds is almost the cost of brute-force. Nothing clear? I chose to provide an introduction then the questions. Maybe I should begin with Look at AES-128... $\endgroup$
    – kelalaka
    Jan 26, 2021 at 20:28
  • $\begingroup$ @Patriot better know? $\endgroup$
    – kelalaka
    Jan 26, 2021 at 20:51

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.