4
$\begingroup$

Let's define "breaking" a hash function $H$ as being threefold (corresponding to the main properties of a cryptographic hash function):

  1. preimage attacks to get $m$ knowing $H(m)$
  2. second-preimage attacks to find some $m'\neq m$ knowing $m$ so that $H(m)=H(m')$
  3. collision attacks to find $m_1,m_2\neq m_1$ for $H(m_1)=H(m_2)$

I wonder how much computational resources would in theory be required for performing each attack on SHA-256. I have little experience with complexity theory, but could not find much literature on this.

My approach was this: in general, there are $2^{256}$ possible hashes. Since there is no known structural weakness in SHA-2, brute-forcing a preimage is the only option and should take $2^{255}$ trials (half of the hash space). However most refer to $2^{256}$, is that because that means certain success rather than expected time needed?

A collision takes $2^{128}$ steps with a Birthday attack. I could not find figures for the second-preimage attack.

First of all, are my assumptions above correct? What would the complexity of the three attacks be?

I am also curious what "unit" a number like $2^{256}$ implies - is it something like floating-point operations that would be needed to run?

I am aware that SHA-256 is deemed secure given today's computational power. is it likely that increasing computer capacities (classical, not quantum computing) will become a threat to this over the next years?

$\endgroup$
6
$\begingroup$

First of all, are my assumptions above correct? What would the complexity of the three attacks be? I am also curious what "unit" a number like $2^{256}$ implies - is it something like floating-point operations that would be needed to run?

Almost, this number is the number of times the primitive (in this case SHA-256) must be called to break the algorithm (e.g. find a preimage or collision).

I am aware that SHA-256 is deemed secure given today's computational power. Is it likely that increasing computer capacities (classical, not quantum computing) will become a threat to this over the next years?

No, SHA-256 will not be broken because of computational power. When you attack a hash function using brute force, the computation will take millions of years. $2^{128}$ operations is just too large a number.

However, most people expect that SHA-2 will be broken in the next 100 years. That is how the first preimage/collision will be found. What this means (in the case of collisions) is that somebody devises a smart algorithm which can find a collision without needing to execute this large amount of operations. Recently, Marc Stevens et al published an attack on SHA-1 which needs only needs $9\,223\,372\,036\,854\,775\,808 \approx 2^{63}$ operations. This number is small enough to be searched through by Google's awesome computing cluster (and consequently the first known SHA-1 collision has been found).

$\endgroup$
  • 1
    $\begingroup$ Exactly, the "attack" is this more efficient way. We say that a hash function has been (academically) broken if a method exists that is more efficient than brute force. $\endgroup$ – dsprenkels Oct 26 '17 at 17:56
  • 3
    $\begingroup$ @indiscreteLogarithm: the assumption that 'some people' (I won't say most people, as I haven't taken a survey; I don't personally expect a preimage attack on SHA-256) are making is someone will discover a practical preimage attack on SHA-256; no such attack is currently known. $\endgroup$ – poncho Oct 26 '17 at 17:59
  • 1
    $\begingroup$ Which $2^{128}$ work effort is indeed highly nontrivial, it isn't quite at the 'heat death of the universe' level. If we assume that we take the entire chip manufacturing capability of the world (currently circa 300+ billion dollars us), and devote the entire output for just one year to making dedicated attack chips, with each chip costing one dollar, and is able to compute $2^{30}$ hashes per second, well, that gives us an attack in only 300 million years, far less than the expected universe lifetime :-) $\endgroup$ – poncho Oct 26 '17 at 19:07
  • 1
    $\begingroup$ @indiscreteLogarithm: $2^{128}$ work effort / 300 billion chips / $2^30$ hashes per chip $\approx 2^{59.8}$ seconds $\approx$ 33 billion years. Hmmmm, it appears that I miscomputed just a tad; well, make each chip 10 times faster, and devote 100 years of global chip output; that'll get you to 30+ million years... $\endgroup$ – poncho Oct 30 '17 at 14:49
  • 2
    $\begingroup$ A twitter survey in this field doesn't mean anything. There are amateurs, who think they are cryptographers and then propose "unbreakable encryption algorithms" with the actual security of a Vigenere cipher. Therefore, I suggest removing that link. Also, the term "breaking a hash function" in theoretical context actually means, that the attack requires less complexity than the just a full search / brute force. That does not mean, it's much more efficient, a reduction in the exponent by $1$ would not make an attack practical - that is the important word. $\endgroup$ – tylo Nov 16 '17 at 15:32
2
$\begingroup$

brute-forcing a preimage (..) should take $2^{255}$ trials (half of the hash space). However most refer to $2^{256}$, is that because that means certain success rather than expected time needed?

The expected number of trial to find a preimage of a random(-like) function with 256-bit output (like a hash aims to be) is $2^{256}$ queries. Justification: the probability of success at each new try is $\frac1{2^{256}}$. The question makes a confusion with the expected number of trials to invert a random permutation of 256-bit block by querying, which is (very closely) halved because the probability of success at each new try is $\frac1{2^{256}-k}$ when there has been $k$ previous tries.

A collision takes $2^{128}$ steps with a Birthday attack.

At $2^{128}$ evaluations, probability of success is only about 39.3%. It reaches 50% at about $\approx1.177\cdot2^{128}$, that's the median number of queries. The mean number of queries is $\approx1.253\cdot2^{128}$ (see my Birthday problem for cryptographic hashing, 101). On top of that, practical methods to find collisions trade feasible memory size and bandwidth against making significantly more evaluations, see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

I could not find figures for the second-preimage attack

They are the same as for first preimage.

What "unit" a number like $2^{256}$ implies ?

In theory that's a number of queries to an oracle, in practice that's the number of computations of SHA-256. Bitcoin mining is performing $>10^{20}$ SHA-256 hashes per second as of October 2018 (per this source, which gives TH/s for SHA256d, that is two SHA-256). At this rate, and if this effort was spent trying to find collisions (it is not), it is improbable a collision would be found in $10^{11}$ years. Only if the rate kept quadrupling every year (the trend in the past few years) for 18 years or so could we reach the point where a collision could be found by brute force. I believe this waste of energy will eventually slow down.

$\endgroup$

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.