10
$\begingroup$

I know that 512 bit hashing is more secure, but I don't really know why. I hope someone can help me to better understand it in more detail.

$\endgroup$
  • 2
    $\begingroup$ It's not universally true. For example, SHA-512 is less secure than the 256-bit "SHA-512/256" (which is basically SHA-512 with a different initialization vector, then truncated to 256 bits). This is because SHA-512 suffers from length extension attacks whereas "SHA-512/256" does not. $\endgroup$ – Nayuki Aug 3 '20 at 17:01
  • $\begingroup$ academically speaking, yes 512 is more secure than 256. but realistically speaking, they're both equally strong. (at least as far as SHA2/SHA3 is concerned) $\endgroup$ – hanshenrik Aug 4 '20 at 1:39
17
$\begingroup$

When there is no known weakness in the hash function we talk about their generic1 resistances

  • Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. E.g., consider storing the hashes of passwords on the server. An attacker will try to find a valid password to your account.

  • Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 \neq m_2$ and $Hash(m_1)=Hash(m_2)$, e.g., producing a forgery of a given message.

  • Collision resistance : it is hard to find two distinct inputs, $a$ and $b$, that hash to the same output $a$ and $b$, i.e., $H(a)= H(b)$ and $a \neq b.$

A hash function with output size $n$ is expected to have $\mathcal{O}(2^n)$ pre-image resistance and secondary image resistance and $\mathcal{O}(\sqrt{2^n)} = \mathcal{O}(2^{n/2})$ collision resisance. The collision resistance is less due to the birthday paradox (attack).

If we plug 256 and 512 into those equations you will see that

  • 256 has $\mathcal{O}(2^{256})$ pre and secondary and $\mathcal{O}(2^{128})$ collision resistance, whereas
  • 512 has $\mathcal{O}(2^{512})$ pre and secondary and $\mathcal{O}(2^{256})$ collision resistances.

As a result, as long as there is no specific weakness in the (unspecified) hash function the larger the output the better the resistance they will have.

When the hash function is specified then one can talk about their resistance in all directions. For example;


The relations of the generic resistances are, in simple terms,

The formal definitions of the resistance and modern cryptographic deal of the above facts and more provided in the novel article; Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance by P. Rogaway and T. Shrimpton on 2009.


1 The term generic is used when a resistance ( or the attacks) applies all of the hash functions. This term similarly used in other cryptographic contexts, too.

$\endgroup$
  • $\begingroup$ So @kelalaka, is the term generic applies to all hash functions because it is referring to the construction of the function itself? $\endgroup$ – Hinton Zsh Aug 7 '20 at 9:43
  • $\begingroup$ Yes, if you look at their definitions you will see an arbitrary function. When one defines the function the one can talk deaper. $\endgroup$ – kelalaka Aug 7 '20 at 11:21
9
$\begingroup$

A n-bit hash can be brute forced $O(2^n)$ operations. If you run the numbers, you find that a 256-bit hash is completely immune to brute force attacks. $2^{256}$ is so large that it would literally take a good chunk of the available energy in our galaxy to break it. So in that sense, they are both "completely secure against brute force."

However, we do find attacks against hashes. These are not brute force attacks, but rather leveraging mathematical quirks about the hash to do the attack with fewer operations than the brute force attack. We can measure the effectiveness of these things in terms of the original brute force attack. If I find an attack on a 256-bit hash which can be done in $O^{192}$ operations, then I have reduced the strength of the hash by $256-192=64$ bits.

Historically, we find that most hashes which survive the initial cryptonanalysis that they receive when they are introduced tend to fall apart gradually. Its rare that we suddenly find a new angle which lets us drop 100 or 200 bits off of the strength of the hash in one big advancement. Typically we see mathematicians take nibbles off of the hash strength, slowly weaning it down.

Past performance does not predict future behaviors. Any given hash could indeed be suddenly broken at any point in time. However, as a general, we find that isn't how it works.

So how do you value this? Well, we can look at computational resources available. The Folding@HOME response to COVID-19 was on the order of $2.4\cdot10^{18}$ operations per second, or $7.5\cdot10^{25} \approx 2^{86} $ operations per year. The speed of Fugaku, a top Japanese super computer, is on a similar scale. So once the number of operations required to break the hash gets to that level, it becomes feasible to break the hash in a year. Using a 512 bit hash provides some additional buffer before it reaches this point.

I'm intentionally ignoring details like birthday attacks, which are important, but do not change the fundamental way the risks are analyzed.

So in general, you can expect a 512-bit hash to remain safe against attacks longer. However, you cannot assume it. There's nothing about a 512-bit hash which is fundamentally safer than a 256-bit hash. It just has a bit more buffer against the historical trends in cryptography. It's the quality of the math inside the hash which is more important. As a reduction to absurdity: I can always make a 512-bit hash by taking a 256-bit hash and doubling each bit. Of course, people will notice rather quickly that there's an attack against it which reduces the strength of my hash by 256-bits!

$\endgroup$
  • $\begingroup$ Thank you so much you provided me with extra information which is very valuable to me. $\endgroup$ – Hinton Zsh Aug 2 '20 at 18:42

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.