3
$\begingroup$

Let us assume that we have a string $w$ such that it belongs the set $C$, where every member of $C$ is not null, and contains every string of characters that can be permuted (numbers, letters etc.). For a secure crypto-hash function such as SHA-512, is it possible to generate an infinite amount of hash collisions given an unbounded amount of time and computation for every possible string $w$?

$\endgroup$
  • 1
    $\begingroup$ A hash function maps an infinite set to a finite set. Therefore we will have infinitely many collisions. So the answer is yes. $\endgroup$ – eins6180 May 25 '18 at 19:29
3
$\begingroup$

If you model the hash function as a random oracle with the domain of the (infinite) set of all strings and a finite countable set for the codomain, then it is always possible to find another collision by the pigeon-hole principal.

SHA-512 is not one of those functions because it is only defined for a finite set of inputs.


But there are even more pedantic responses to your question. (Things one's teacher might say, like infinity is not a number.) One such response is that you say you have infinite time but do not note there is enough space to store a list of inputs corresponding to each possible output.

If you have a random oracle, then you can still compute any number of collisions without any memory besides that necessary to prevent repeat inputs. One strategy is to pick any element of the domain (say the all-zero bit string), iterate over all possible inputs, and print each input where the output matches your chosen element as you find such inputs.

That strategy works for a random oracle, but technically you could define a hash function that returns the all-zero bit string for only a finite number of inputs. (It's no problem doing this for a theoretical hash function definition because there are still a non-zero number of holes you can stuff the infinite amount of pigeons which might otherwise want to nest in hole zero to some other hole that can fit infinitely many pigeons.)

Then you would print every one of the inputs that map to zero and continue in an infinite loop, never finding any more collisions, despite the fact that collisions are still occurring. (This search strategy just can't remember other outputs.)

The pigeon-hole principal for unlimited pigeons and finite holes necessarily means there is no limit on the number of collisions even for a non-random-oracle function. You just made an unlucky choice of limited-storage-space algorithm implementation. Some other choices of search strategy are still able to find an unlimited collisions for the same function, of course.


No matter what, the infinite domain / finite countable co-domain part matters. Having a bounded number of inputs obviously prevents there from being an infinite number of outputs. The countable part is another pedantic thing. If your function returned a real number (or any continuous quantity) instead one of a finite number of discrete values, then it's possible for an oracle (random or not) to pick outputs that do not equal any previously returned.


I think it's okay to pretend SHA-512 fits the model I mentioned at the top. Some numbers are so huge that they're not practically distinguishable from infinity on real world computers.

$\endgroup$
5
$\begingroup$

Yes and no.

SHA-512 is by definition limited to strings of at most $2^{128}$ bits long. So there is only a finite set of possible inputs, not an infinite set. But you're guaranteed to have many collisions even in that finite set, because there are only $2^{512}$ holes to put $2^{2^{128}}$ pigeons into.

SHA3-512,* in contrast, is not limited to any finite input space. So there are collisions of infinitely many strings, in principle.

But you're not likely to find any. Unless you know something about SHA-512 or SHA3-512 that I don't, you would have to try approximately $2^{256}$ before you would be likely to find a single collision. I assure you most decidedly that ain't nobody got time for that.


* It's also silly to use SHA3-512 for any purpose. Its design was selected for political, not technical, reasons after certain well-known news in 2013. There's no substantive reason to use it instead of SHAKE256-512.

$\endgroup$
  • $\begingroup$ I'm curious about your SHA3 vs SHAKE256 footnote. Do you know where I can find more details about it? $\endgroup$ – Joseph Sible-Reinstate Monica Jun 1 '18 at 15:16
  • 2
    $\begingroup$ @JosephSible The cost of a preimage or collision attack on SHAKE256-512 is ${\sim}2^{256}$ hash evaluations. The cost of a collision attack on SHA3-512 is also ${\sim}2^{256}$ hash evaluations, but the cost of a preimage attack is ${\sim}2^{512}$ hash evaluations, which makes SHA3-512 ridiculously slow for no good reason (${\sim}2^{256}$ is already unimaginable-squared). This happened because NIST didn't want to be seen meddling with the design of SHA-3 in the months after Snowden documents revealed NSA's sabotage of crypto standards. $\endgroup$ – Squeamish Ossifrage Jun 1 '18 at 16:50

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.