<p>Preimage resistance and collision resistance are not absolute, they are just matters of amount of computation that is necessary to solve certain problems. For example, for an ideal hash function with 256-bit output, an order of 2<sup>256</sup> evaluations are needed to find a preimage, and an order of 2<sup>128</sup> evaluations are needed to find a collision. Anything less is considered an attack.</p>

<p>For example, if you can find collisions with just 2<sup>124</sup> evaluations (and not because you are lucky, but because you use some approach specific to the function), this is an attack, but it is not practical because 2<sup>124</sup> is still immensely large.</p>

<p>Moreover, for Bitcoin mining, you need to find only partial preimages, not full preimages. For example, to find a value such that first 50 bits of its hash are zeros, you need 2<sup>50</sup> hash evaluations, assuming the hash is ideal. And there is a problem: if the hash is not preimage-resistant (so you need, for example, just 2<sup>240</sup> evaluations to find a preimage, rather than 2<sup>256</sup>), this doesn't tell anything about resistance to finding partial preimages (so the above problem may still take 2<sup>50</sup> evaluations, but may take only 2<sup>34</sup>). And lack of collision resistance doesn't tell anything at all about the difficulty of finding partial preimages. However, Bitcoin depends on collision resistance of SHA256 in other places, so it is still important.</p>

CC BY-SA 3.0
2014-09-29T06:37:42.923Z
2014-09-29T06:37:42.923Z
abacabadabacaba
<blockquote>
  <p>Any collision resistant hashing function H<sub>k</sub> : {0,1}<sup>*</sup> → {0,1}<sup>k</sup> is pre-image resistant regarding the uniform distribution on {0,1}<sup>2k</sup>.</p>
</blockquote>

<p><code>A ⇒ B ⇔ ¬B ⇒ ¬A</code>: I.e. if a function isn't pre-image resistant it is not collision resistant either.</p>

<p>SHA256 is a function that maps a potentially unlimited set of numbers to a smaller set of numbers.</p>

<blockquote>
  <p>H<sub>k</sub> : {0,1}<sup>*</sup> → {0,1}<sup>k</sup></p>
</blockquote>

<p><strong>Collision resistance</strong> is a property that loosely says, it is difficult to find two <em>inverse images</em> <code>X ≠ X'</code> that have the same <em>image</em> <code>H(X) = H(X')</code>.</p>

<p>More to the point:<br>
A function <code>H</code> is <em>collision resistant</em>, if any algorithm can only find a collision with a negligible probability in probabilistic polynomial time.</p>

<p>I.e. if SHA256 would turn out to not be <em>collision resistant</em>, one could try to pick hashes that would succeed at the current difficulty, use the above predicted inverse function of SHA256 to calculate <em>inverse image</em> candidates, and finally check whether one can satisfy them with the currently available block input.</p>

<p>My gut feeling would be though, that it would be pretty difficult to find <em>inverse images</em> that also satisfy the required structure of the block input, especially getting right the hash of the parent block, and matching an address that one controls for the coinbase transaction.</p>

<p>Unfortunately, I have no idea whether the complexity of that would be greater or smaller than bruteforce mining.</p>

CC BY-SA 3.0
2014-09-25T15:10:16.973Z
I am currently studying for an exam whose topic includes Collision Resistance, pre-image resistance, and so forth. So, please take in account that I am by no means a cryptography expert before building on my answer. :)
Murch
CC BY-SA 3.0
2014-09-25T15:44:33.377Z
I thought that Pre-image resistance and Collision resistance are something akin to mutually exclusive?  Its more of a relationship between collision resistance and secondary pre-image resistance right?
mcdoomington
CC BY-SA 3.0
2014-09-25T20:52:21.927Z
@mcdoomington: Target Collision Resistance (or Second Pre-Image Resistance) is between the two: For big domains hashed to a smaller image sets it is `Collision Resistance ⇒ Second Pre-Image Resistance ⇒ Pre-Image resistance`. Also see [Does collision resistance imply (or not) second-preimage resistance?](http://crypto.stackexchange.com/a/17925/8801)
Murch
CC BY-SA 3.0
2014-09-25T15:04:10.083Z
2014-09-25T15:04:10.083Z
Murch
<p>I'm experimenting with some self study cryptography and I was curious about the two following scenarios (simple answers and/or in relation to bitcoin)</p>

<p>If SHA256 was found to lack pre-image resistance, would it make solving the puzzle easier?</p>

<p>Alternatively, if the algorithm was found to be not collision resistant - would the puzzle again be easier to solve?</p>

<p>Thanks</p>

<security><cryptography><sha256>
What would happen if SHA256's pre-image or collision resistance would be broken?
mcdoomington
# What would happen if SHA256's pre-image or collision resistance would be broken?

(Asked by: username_0 on 2014-09-25)

I'm experimenting with some self study cryptography and I was curious about the two following scenarios (simple answers and/or in relation to bitcoin)

If SHA256 was found to lack pre-image resistance, would it make solving the puzzle easier?

Alternatively, if the algorithm was found to be not collision resistant - would the puzzle again be easier to solve?

Thanks

**Tags:** security, cryptography, sha256


---

## 2 answers

### Answer by username_1 on 2014-09-29. Score: 0 | Accepted answer

Preimage resistance and collision resistance are not absolute, they are just matters of amount of computation that is necessary to solve certain problems. For example, for an ideal hash function with 256-bit output, an order of 2256 evaluations are needed to find a preimage, and an order of 2128 evaluations are needed to find a collision. Anything less is considered an attack.

For example, if you can find collisions with just 2124 evaluations (and not because you are lucky, but because you use some approach specific to the function), this is an attack, but it is not practical because 2124 is still immensely large.

Moreover, for Bitcoin mining, you need to find only partial preimages, not full preimages. For example, to find a value such that first 50 bits of its hash are zeros, you need 250 hash evaluations, assuming the hash is ideal. And there is a problem: if the hash is not preimage-resistant (so you need, for example, just 2240 evaluations to find a preimage, rather than 2256), this doesn't tell anything about resistance to finding partial preimages (so the above problem may still take 250 evaluations, but may take only 234). And lack of collision resistance doesn't tell anything at all about the difficulty of finding partial preimages. However, Bitcoin depends on collision resistance of SHA256 in other places, so it is still important.


---

### Answer by username_2 on 2014-09-25. Score: 1

> Any collision resistant hashing function Hk : {0,1}\* → {0,1}k is pre-image resistant regarding the uniform distribution on {0,1}2k.

`A ⇒ B ⇔ ¬B ⇒ ¬A`: I.e. if a function isn't pre-image resistant it is not collision resistant either.

SHA256 is a function that maps a potentially unlimited set of numbers to a smaller set of numbers.

> Hk : {0,1}\* → {0,1}k

**Collision resistance** is a property that loosely says, it is difficult to find two *inverse images* `X ≠ X'` that have the same *image* `H(X) = H(X')`.

More to the point:  
A function `H` is *collision resistant*, if any algorithm can only find a collision with a negligible probability in probabilistic polynomial time.

I.e. if SHA256 would turn out to not be *collision resistant*, one could try to pick hashes that would succeed at the current difficulty, use the above predicted inverse function of SHA256 to calculate *inverse image* candidates, and finally check whether one can satisfy them with the currently available block input.

My gut feeling would be though, that it would be pretty difficult to find *inverse images* that also satisfy the required structure of the block input, especially getting right the hash of the parent block, and matching an address that one controls for the coinbase transaction.

Unfortunately, I have no idea whether the complexity of that would be greater or smaller than bruteforce mining.

> **Comments:**
> **username_2**: I am currently studying for an exam whose topic includes Collision Resistance, pre-image resistance, and so forth. So, please take in account that I am by no means a cryptography expert before building on my answer. :)  
> **username_0**: I thought that Pre-image resistance and Collision resistance are something akin to mutually exclusive?  Its more of a relationship between collision resistance and secondary pre-image resistance right?  
> **username_2**: @username_0: Target Collision Resistance (or Second Pre-Image Resistance) is between the two: For big domains hashed to a smaller image sets it is `Collision Resistance ⇒ Second Pre-Image Resistance ⇒ Pre-Image resistance`. Also see [Does collision resistance imply (or not) second-preimage resistance?](http://crypto.stackexchange.com/a/17925/8801)  

---

