1
$\begingroup$

From what I've researched, SHA's hex encoded string contains the characters [a-fA-F0-9]. If we represent it in Base64, it can contain [a-zA-Z0-9+/].

So the number of possible hash permutations are 22^64 and 59^64 respectively.

My question is, while we have infinite permutations for the input text, if the output hash is finite, then aren't all SHA algorithms meant to collide at some point?

I'm self taught. So please bear if this is a basic thing in cryptography.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Possible duplicate of For any hash value, is there an infinite number of inputs that hash to it? $\endgroup$
    – AleksanderCH
    Commented Aug 10, 2018 at 12:40
  • 2
    $\begingroup$ It is also worth noting that SHA output is a string of bits, and we encode in hex ([0-9a-f] where case for a-f doesn't matter, so 16^64 = 2^256) or base-64 (encoding 256 bits in 42.7 -> 43 characters, so 64^43 = 2^258, so we typically ignore two bits) for convenience when working with it as humans. $\endgroup$
    – Eugene Styer
    Commented Aug 10, 2018 at 13:27
  • $\begingroup$ Oh alright @EugeneStyer I didn't know that. But that doesn't answer my doubt. I went through what AleksanderRassasse has pointed out. But it was difficult for me to comprehend. I'll go through that answer once again. $\endgroup$
    – Subramanian Sridharan
    Commented Aug 10, 2018 at 13:48

1 Answer 1

Reset to default
2
$\begingroup$

My question is, while we have infinite permutations for the input text, if the output hash is finite, then aren't all SHA algorithms meant to collide at some point?

Due to the pigeonhole principle, all hash functions will collide at some point. Since there are more inputs than outputs, the existence of collisions is unavoidable.

The job of a cryptographic hash function is to make finding collisions cost so much that it will never happen, and to make finding preimages prohibitively expensive as well.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nitpicking: It‘s assumed that every hash value will collide, but you just can‘t be sure about that. There are certainly some hashes with collisions, but maybe there is a unknown flaw in the algorithm that would prevent the outcome of a certain hash value (or the possibility for infinite hashes for every possible hash-value). To reference the pigeonhole principle: There are 10 pigeons and 9 holes. It‘s certain that at least one hole has two or more pigeons. But they could also be one hole that is empty and one with three pigeons. $\endgroup$
    – AleksanderCH
    Commented Aug 11, 2018 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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