Cryptography
sha-256 group-theory one-way-function cryptocurrency
Updated Fri, 20 May 2022 20:07:35 GMT

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


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?




Solution

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.





Comments (5)

  • +1 – nitpick: It is widely believed when limited to 256 bit input sha256 has collisions but no one can prove this currently. — Sep 21, 2019 at 16:48  
  • +0 – @MeirMaor thanks. I was considered to include that (I'm expecting this, too), but couldn't find a proper reference. Dou you know one? — Sep 21, 2019 at 16:51  
  • +0 – A reference for what? Our inability to show SHA256 has no known collision, that we have not even a non constructive proof of such existing. In general symmetric cryptography building blocks tend to come with very little in the waybof proof. Even if we were magically given a 256 bit pseudo random function it stall has an infentesimal but non zero chance of being collision free. — Sep 21, 2019 at 17:01  
  • +0 – not, exactly a paper, not from a random person like me :) — Sep 21, 2019 at 17:03  
  • +4 – It would be rather surprising if SHA-256 limited to 256-bit inputs were a surjective mapping. If it were, it would necessarily also be injective, and therefore a permutation on 256-bit strings, so SHA-256(SHA-256(x)) would also be a permutation on 256-bit strings, and neither of them wold have any collisions among 256-bit inputs. — Sep 21, 2019 at 18:44