1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ suggestion: use of double dollar sign, added parenthesis, added spacing$$\sum_{l=0}^{2^{64}-1} 2^l\;=\;2^{(2^{64})} - 1$$ $\endgroup$ – fgrieu Apr 13 '16 at 20:08
  • $\begingroup$ Thanks for the explanation. It makes sense. I think my intuition breaks when stating that "almost the whole universe is inside one of each bucket". From a quantity perspective is true but the elements belonging to a given bucket are not close to each other. Its "positions" in space are chaotic and intermixed with elements of other buckets. $\endgroup$ – Eduard Apr 14 '16 at 9:10
  • $\begingroup$ So choosing two of them and being in the same bucket is still hard. Having the notion of how big infinity is makes any finite set small. But still in the realm of finite sets, when the cardinality of each set differs a lot it is hard to visualize it. $\endgroup$ – Eduard Apr 14 '16 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.