Hash collisions in sha512 hash of secp256k1 public keys

Question

For a sha512 hash of a secp256k1 public key, how many other public keys could generate that hash? I would assume zero since the key size is equal to the hash length (secp256k1 public keys are 64 bytes, 512-bit), and there are only $2^{256}$ public keys as the private keys are 256-bit.

Answer 1

The output of the SHA512 is 512-bit, so there are at most $2^{512}$ different outputs.

For random inputs, the expected hash collision with 50% probability is $\sqrt(2^{512}) = 2^{256}$ by Birthday Paradox ($\sqrt(n)$).

The public keys of secp256k1 have 64-byte = 512-bit. To calculate SHA512 hash the input values are padded so that the input size is always multiple of 1024. After $2^{256}$ SHA512 hash of the public keys, we expect to find collisions with 50% probability.

• SHA512: For finding a collision with birthday attack for SHA512 is almost impossible. You will need immense time, storage, and power for $2^{256}$ input values.

• SHA256: For finding a collision with birthday attack for SHA256 is almost the same as breaking AES-128 by brute force, need for $2^{128}$ hash values. If we assume that the BitCoin miners top peak performance is $\approx 2^{91}$ hashes in a year, you will need $2^{37}$ years with the same computing platform and power consumption.

Answer 2

There's likely to be some collisions in the SHA-512 hashes of secp256k1 public keys, but so few it doesn't matter.

Let's model SHA-512 as a uniform 512-bit function, and let's approximate the number of distinct secp256k1 public keys as about $2^{256}$. (Really it's closer to $2^{256} - 2^{128}$, but that's an insignificant difference here.) So we are throwing $n \approx 2^{256}$ balls into $k = 2^{512}$ bins. This is a standard instance of the birthday paradox. We might first ask for bounds on the probability of collisions, but the number of balls is about the square root of the number of bins, so probability is quite high, and thus the bounds aren't very useful and the approximations don't illuminate much: there's probably at least one collision.

What's the expected number of collisions, i.e. the average over all possible hash functions $H$ with uniform weights of the number of keys that do not have unique hashes? It is slightly simpler to ask first for the expected number of distinct outputs: for each hash $y$, how many keys $x$ are hashed to $y$? Independently, we have $\Pr[H(x) = y] = 1/k = 1/2^{256}$, and there are about $n = 2^{256}$ keys, so for each $y$,

\begin{align} \Pr[\exists x. H(x) = y] &= 1 - \Pr[\forall x. H(x) \ne y] \\ &= 1 - \prod_x \Pr[H(x) \ne y] \\ &= 1 - \prod_x \bigl(1 - \Pr[H(x) \ne y]\bigr) \\ &= 1 - \prod_x \bigl(1 - 1/2^{512}\bigr) \\ &= 1 - \bigl(1 - 1/2^{512}\bigr)^{2^{256}} \\ &= 1 - \bigl(1 - 1/2^{512}\bigr)^{2^{512} 2^{-256}} \\ &\approx 1 - e^{-2^{-256}} \\ &= 1 - (1 - 2^{-256} + 2^{-512}/2 - 2^{-1024}/6 + \cdots) \\ &\approx 2^{-256} - 2^{-513}. \end{align}

By linearity of expectations, this is the expected fraction of distinct outputs among the $2^{512}$ possibilities, so the expected number of distinct outputs is about $2^{512} (2^{-256} - 2^{-513}) = 2^{256} - 1/2$. In other words, the expected number of keys that share a hash with any other keys is $1/2$.

Even if there are any there, you probably won't find that expected half a needle in a haystack of $2^{256}$ possibilities.