Does double hashing increase resistant against first preimage attacks?

Question

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?

Answer 1

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.