2
$\begingroup$

Let's take Bitcoin as an example. Bitcoin uses SHA256, which can be vulnerable to collision and preimage attacks - although this is extremely unlikely to happen in the near-future.

However, let's say an evil genius figures out how to compromise Bitcoin by developing a way to perform a first preimage attack against SHA256 (in other words, he finds an input that hashes to a specific output; i.e., given y, he finds an x such that h(x) = y). But Bitcoin uses double hashing, rather than just hashing once.

Therefore, my question is this: does double-hashing increase the resistance of SHA256 against a first preimage attack?

$\endgroup$
1
$\begingroup$

Define $g(x)=h(h(x)).$ If the original preimage attack has complexity $C,$ and success probability $p$ then depending on what kind of structural properties of SHA256 it uses, you should be able to use the same principle and have complexity $2C=O(C)$ at the cost of reduced success probability $p^2.$

After all the preimage of $y$ under $g$ is just the preimage of the preimage of $y$ under $h,$ and if the original attack works it should not depend on some deep properties of $x$ but only the properties of the hash function $h$.

In particular, it should work to find the preimage of $z=h^{-1}(y)$ when you apply it to $z.$

It's up to you whether you call this an "improvement" or not. It's very marginal if we operate in a regime where success probability is nearly $1.$

There is the convention in computer science that a randomized algorithm is deemed to be successful if its success probability $p$ obeys $p\geq 2/3,$ so you can read the above comment in this light.

CoDomain Issue: As in the comments, we can only use the preimage $h^{-1}(y)$ as input to the next stage if it falls into the hash output space. This is more tricky; if we assume $h$ behaves like a random function on its codomain then each output $y$ will have no preimages with probability roughly $e^{-1},$ and otherwise an average of $1/(1-e^{-1})$ preimages with the highest possible number likely to be around $\log(n)/\log\log(n)$ where $n=2^{256}.$ So the complexity of a preimage attack restricted to the codomain will be comparable to the regularly assumed complexity of an arbitrary preimage attack under the random oracle model which is that to be successful with probability $q$ you need to try $q n$ random inputs.

See the report (search on http://cacr.uwaterloo.ca/): Stinson, D.R., Some Observations on the Theory of Cryptographic Hash Functions CACR Research Report, September 12, 2002.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This assumes success probability of 1. If we have only success probability P. After double hashing it will.go down to $P^2$. Which could be significant. $\endgroup$ – Meir Maor Jan 30 at 4:57
  • 1
    $\begingroup$ The preimages you can find with work $C$ may fall outside the codomain of the hash function (e.g. they may be too long to be valid hashes). If this is the case the attack could not be used as you describe. $\endgroup$ – Maeher Jan 30 at 17:09

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.