SHA-1: number of possible inputs, number of possible outputs, how many inputs have the same output,

Question

From Wikipedia I read SHA-1 function produces an output of 160 bits and expects a max message size of $2^{64}-1$ bits. Is that right?

If I order all possible inputs I would produce $\approx 2^{2^{64}}$ different bit array inputs, right?

Not sure at this point if message 0 is different from message 00.

Can we say that SHA-1 receives a bit array of maximum $2^{64}-1$ elements as input? If the bit array has less than $2^{64}-1$ elements it is like receiving 0's for the rest (or maybe start receiving 0's until...)?

I'm not good at big numbers... Maybe the difference is small. If 0 bit array is different than 00 bit array maybe still the number of possible inputs is $\approx 2^{2^{64}}$.

Then $2^{160}$ is $\approx 2^{2^8}$.

So there are $2^{2^{64}}$ possible inputs for $2^{2^{8}}$ possible outputs. It means that there are $\approx \frac{2^{2^{64}}}{2^{2^8}}$ inputs for each output. But $\frac{2^{2^{64}}}{2^{2^8}}$ is $\approx 2^{2^{64}}$.

If $2^{2^{64}}$ is the whole universe it looks like almost the whole universe is inside each bucket (hash output).

Does it mean that if I take randomly two different inputs of the set of $2^{2^{64}}$ elements the probability that they belong to the same bucket is very high?

Answer 1

From Wikipedia I read SHA-1 function produces an output of 160 bits and expects a max message size of $2^{64}-1$ bits. Is that right?

Yup, looks right.

If I order all possible inputs I would produce approx. $2^{2^{64}}$ different bit array inputs, right?

Yes. The number of possible inputs is the sum of the number of possible $l$-bit strings for $l$ from $0$ to $2^{64}-1$:

$$\sum_{l=0}^{2^{64}-1} 2^l \;=\; 2^{2^{64}} - 1$$

If the bit array has less than $2^{64}-1$ elements it is like receiving 0's for the rest (or maybe start receiving 0's until...)?

Actually, SHA-1's padding is designed to prevent this from occurring. If $\text{SHA-1}$ is to be a secure cryptographic hash function, it shouldn't be possible to come up with any two messages $m_1$, $m_2$ such that $\text{SHA-1}(m_1) = \text{SHA-1}(m_2)$ (i.e. a hash collision). If it were true that $\text{SHA-1}(m) = \text{SHA-1}(m \| 0)$ ($\|$ is concatenation), that would violate this requirement.

If $2^{2^{64}}$ is the whole universe it looks like almost the whole universe is inside each bucket (hash output).

That's a good intuition. $2^{160}$ is a huge number, but $2^{2^{64}}$ is beyond astronomical (it's estimated that there are fewer than $2^{266}$ atoms in the visible universe). This is what makes cryptographic hash functions so interesting. We know that there is an incredibly astronomically massive number of colliding input pairs, but we just can't find any (or at least, we can't with a good hash function: SHA-1 is broken, and someone has most likely already found a collision).

Does it mean that if I take randomly two different inputs of the set of $2^{2^{64}}$ elements the probability that they belong to the same bucket is very high?

If a bucket means a given hash output, then no, the probability is quite low. Let's assume that SHA-1 was a strong, unbroken hash function. Choose one input from the set of $2^{2^{64}}-1$, call it $m_1$, and let $h_1 = \text{SHA-1}(m_1)$. Note that $h_1$ is one of $2^{160}$ possible values. Now choose at random the second input, call it $m_2$, and let $h_2 = \text{SHA-1}(m_2)$. The probability that $h_2$ ended up being the same value as $h_1$ is $1/2^{160}$.

This explanation might better match your intuition: The $2^{2^{64}}-1$ possible inputs are divided into $2^{160}$ equal-sized buckets (approximately equal-sized, at least). All of these buckets are massive, but there are so many buckets that the probability of choosing two values in the same bucket is still quite low.