Would SHA-256(SHA-256(x)) produce collisions?

Question

Was reviewing some Bitcoin public-key hash literature and the use of RIPEMD-160 and the SHA-256 as below:

 RIPEMD160(SHA256(ECDSA_publicKey))

The Proof-of-work on the other hand uses SHA256 two times (instead of RIPEMD-160).

There is some notes on why RIPEMD160 was chosen (here).

Considering the 256-bit output space of SHA256, what would happen (theoritically) if one were to use SHA256 on a SHA256 output? For example:

SHA256(SHA256(x))

Would this be a bijective mapping? or Surjective mapping?

Can such mapping be used, in any way, to break the SHA-256?

Since SHA-256 is supposed to be a one-to-one function, there is no way the SHA256(SHA256(x)) could be injective function (since the input space and output space are both 256-bits). But if it is not injective, then SHA-256 cannot be one-to-one function for longer message (>256-bit input). How is this contradiction being worked out in the algorithm?

Answer 1

First of all, note that, SHA-256 operates on a minimum of 512-bit messages. The message is always padded to be a multiple of 512-bit ( see padding below). For double SHA256(SHA256(m)), after the first hash, the result is padded to 512-bit.

padding: The SHA-256 message format |L|1|0..0|message size in 64 bits|. L is the original message bits to be hashed, it is followed by 1, and many zeros except the last 64-bit so that the padded message is multiple of 512-bit, minimally. The last 64-bit is the message size. The maximal message that can fit into one 512-bit hash block is 447-bit.

So, if $x = \operatorname{SHA256}(m) $ the it will be padded as

| x 256-bit| 1 | 0000's 191-bit | 64-bit size of x) |

for the next SHA-256 calculation.

Now, the input-out space will be exactly 256-bit. In this case, we don't know it is one-to-one or not. The space is huge for calculations. If it is one-to-one then it will be a permutation, too. There are $2^{256}!$ permutations and there are $(2^{256})^{(2^{256})}$ functions. It will be amazing if it is a permutation. For simplicity, take 5-bit as an example, there are 32! permutations ~112-bit and there are $32^{32}$ functions ~161-bit. If we consider that the restricted SHA-256 is a randomly selected function then the probability of being permutation is around $\frac{1}{2^{50}}$. See a glimpse from WolframAlpha in a logarithmic scale.

Since SHA-256 is supposed to be a one-to-one function

SHA-256 is not a one-to-one function. It is a one-way function i.e. you cannot revert it. Since the minimum input size 512-bit and the output size is always 256-bit, there is no way to be one-to-one.

Would this be a bijective mapping? or Surjective mapping?

It would be surjective mapping.

But if it is not injective, then SHA-256 cannot be one-to-one function for longer message (>256-bit input).

It is not one-to-one.

Would SHA-256(SHA-256(x)) produce collisions?

If we consider that you are talking about hashing bitcoin public keys, it has 33 bytes compressed and 65 bytes uncompressed public keys.

If the key is uncompressed, it has 520-bit therefore by the pigeonhole principle there will be collisions.

If the key is compressed, it has 264-bit again therefore by the pigeonhole principle there will be collisions, the output is 256-bit.

Note that SHA-256(SHA-256(x)) will be still collision-resistant.

Can such mapping be used, in any way, to break the SHA-256?

See this question Weaknesses” in SHA-256d? for the nice answer of FGrieu.

Answer 2

SHA256(SHA256(x))

Would this be a bijective mapping? or Surjective mapping?

SHA-256 is almost certainly not injective on 256-bit inputs, so it is almost certainly not a bijection or a surjection onto 256-bit outputs either. And if SHA-256 is not injective, then applying it twice can't be injective—if $x \ne x'$ are distinct preimages of $h$ under SHA-256, then they are preimages of $\operatorname{SHA256}(h)$ under the composition.

Why do I say SHA-256 is almost certainly not injective? A reasonable model for SHA-256 is a uniform random function. The vast majority of functions from 256-bit strings to 256-bit strings are not injective. Only the permutations of 256-bit strings are injective. There are $F = \bigl(2^{256}\bigr)^{2^{256}}$ functions from 256-bit strings to 256-bit strings, and only $P = 2^{256}!$ permutations of 256-bit strings, which by Stirling's approximation is roughly $$P = 2^{256}! \approx \sqrt{2\pi 2^{256}} \bigl(2^{256}/e\bigr)^{2^{256}} \!= \sqrt{2\pi 2^{256}} e^{-2^{256}} \bigl(2^{256}\bigr)^{2^{256}} \!= \sqrt{2\pi}\,2^{128} e^{-2^{256}} F.$$ That is, the fraction of functions which are permutations—which is the probability that a uniform random function is actually a permutation—is $$P/F \approx \sqrt{2\pi}\,e^{128 \log 2 - 2^{256}} \approx 1/2^{2^{256}}$$ which is so staggeringly improbable that it is roughly comparable to flipping a coin for every atom in the Milky Way galaxy—about $1.5 \times 10^{12}$ solar masses by recent estimates, with one solar mass equal to about $2 \times 10^{30}\,\mathrm{kg}$ based on the solar mass parameter $G \cdot M_S \approx 1.327\,124 \times 10^{20}\,\mathrm{m^3\,s^{-2}}$ and the gravitational constant $G \approx 6.674 \times 10^{-11}\,\mathrm{m^3\,kg^{-1}\,s^{-2}}$ reported by the IAU NSFA Current Best Estimates; assuming it consists entirely of hydrogen atoms at $1.67 \times 10^{-27}\,\mathrm{kg}$ a pop, that's a total of about $2 \times 10^{69}$ atoms—and having them all come up heads. And having the entire population of Shanghai, about thirty million people, repeat the experiment with the same all-heads outcomes.

That said, just because there almost certainly are collisions doesn't mean we have a way to find them.

Can such mapping be used, in any way, to break the SHA-256?

No. If it could then we would consider SHA-256 to be broken. However, protocols that use $\operatorname{SHA256}(\operatorname{SHA256}(x))$ may be broken even if SHA-256 is not.

Since SHA-256 is supposed to be a one-to-one function, there is no way the SHA256(SHA256(x)) could be injective function (since the input space and output space are both 256-bits). But if it is not injective, then SHA-256 cannot be one-to-one function for longer message (>256-bit input). How is this contradiction being worked out in the algorithm?

SHA-256 is almost certainly not a one-to-one function. Rather, it is conjectured to be collision-resistant, meaning that nobody has found a way to find two distinct messages $x \ne x'$ that SHA-256 maps to the same hash, short of a generic search (i.e., a search that treats SHA-256 as a black box) that would take longer than humanity has left before it roasts the planet. Which admittedly is not a very long time, but the generic search would take much longer than that anyway even if you spent all humanity's available energy on running the generic search in parallel.