 Cryptography

# 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.