# Approximate size of image of SHA512

Let $$s: \{0,1\}^* \to \{0,1\}^{512}$$ be the SHA512 hash (where $$\{0,1\}^*$$ is the countable set of all finite $$\{0,1\}$$ strings.

Is it known whether $$|\text{im}(s)|/2^{512} \geq 0.5$$?

If yes, what is the largest $$n\in\mathbb{N}$$ such that $$|\text{im}(s)|/2^{512} \geq 1 - (1/2)^n$$?

• If we model SHA-512 as uniform random then this is answer; SHA-512 - How difficult is it to find a hash digest beginning with at least twelve zeros? Apr 24, 2022 at 8:32
• @kelalaka I interpret the question as "How close to surjective is SHA512". Assuming it is uniformly random also assumes it is surjective. Apr 24, 2022 at 10:57
• @meshcollider that was their previous question that Fgriue answered. In short, we don't know about that. Apr 24, 2022 at 14:29

Here we are throwing $$k$$ balls into $$n$$ bins. An output bin remains empty if all the balls miss it which happens with a probability $$(1-1/n)^k = \left[(1-1/n)^n\right]^{k/n} where $$n=2^{512}$$ and $$k>n$$. If we want this probability to be strictly less than $$1/n^2$$ we need to solve
$$e^{-k/n}<\frac{1}{n^2}=e^{- 2 \ln n}$$ which gives $$k>2 n \ln n.$$
We can now apply the union bound (which is weak but the question is about infinite domain size, so this is fine) on the complement of this event and note that since there are $$n$$ bins the probability that any bin is empty is strictly less than $$n(1/n^2)=1/n.$$
This gives $$k>2^{513+\log_2 \ln 512}$$ if I haven’t made a computational error.