2
$\begingroup$

If we take every possible hash ($16^{64}$) and rehash it, the amount of possible outcomes for any given rehash is 1 out of $16^{64}$. So, all possible rehashes is equal to all possible unique hashes.

Assuming each rehash provided a unique hash, with no collisions, doesn't this imply any input larger or smaller than 64 bytes would collide with one of these values?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ There are collisions, by the pigeonhole principle. $\endgroup$
    – fgrieu ♦
    Jul 9 '17 at 22:10
  • $\begingroup$ @fgrieu So, if a pattern between hashes and rehashes exists (no idea if one does) then what, if anything, does that do to the strength/integrity of the function? $\endgroup$
    – That Guy
    Jul 9 '17 at 22:17
2
$\begingroup$

If you could hash $16^{64} = 2^{256}$ distinct inputs to a hash with a 256 bit output, then you would expect some collisions. (This is equivalent to you rehashing every possible hash in the domain if you hash the 16-byte representation of every non-negative integer < $2^{256}$)

How many collisions? First lets assume the output of a hash function is uniformly randomly distributed. The probability of 2 hash values being the same (being a collision) is $(1/2^{256}) = 2^{-256}$

We have $2^{256}$ outputs, so there are $\frac{2^{256}*(2^{256} - 1)}{2}$ pairs of output hashes. Each of these pairs has probability ${2^{-256}}$ of being the same. So the expected number of collisions is ${2^{-256}} * \frac{2^{256}*(2^{256} - 1)}{2} \approx 2^{255}$

So this implies that with 2^256 inputs, you would expect half of them to be collisions with each other, and therefore for any new input you hash, there is a 50% probability of it colliding with a hash you already know. However 2^256 is a massive number, and getting anywhere near that many hashes is computationally infeasible today.

--EDIT-- As pointed out by fgrieu, even though there are $2^{255}$ collisions, some of the collisions are on the same element, thus the amount of hash values reached is instead significantly less than $2^{255}$.

I have been unable to find a source or derivation of how many distinct collision hashes would be reached. (An equivalent question "what is the number of distinct shared birthdays in a given room for the birthday problem")

Improve this answer
$\endgroup$
9
  • $\begingroup$ Yeah, but if half are collisions... $\endgroup$
    – That Guy
    Jul 10 '17 at 8:04
  • 1
    $\begingroup$ @ThatGuy half of 2^256 is 2^255. Good luck storing that list of hashes for comparison. $\endgroup$
    – rmalayter
    Jul 11 '17 at 1:47
  • 1
    $\begingroup$ I don't think you understand the insignificance of these collisions. 2^80 is well into the realms of computational infeasibility for a government spending years trying to compute something. This requires 2^256 computations, and 2^255 * 16 bytes of memory. This isn't a cryptographic vulnerability of the hash function, its a property endemic to any function with pseudo-random output and a fixed range. $\endgroup$
    – Ninja_Coder
    Jul 11 '17 at 9:05
  • 1
    $\begingroup$ "Each of these pairs has probability $2^{−256}$ of being the same": yes; but these probabilities are not independent; e.g. if $H(a)=H(b)$ then $P(H(a)=H(c))=P(H(b)=H(c))$ ). This turns out to have a significant effect on the expected number of collisions (as you define it, that is counting $k!/2$ collisions for $k\ge2$ colliding values). Only the order of magnitude of your result is correct. $\endgroup$
    – fgrieu ♦
    Jul 12 '17 at 4:49
  • 2
    $\begingroup$ To answer your last question, if we throw n balls into n bins a bin will remain empty if all balls miss it which happens with probability (1-1/n)^n which equals 1/e . If we throw m=cn balls into n bins the probability of a bin being empty is 1/e^c and that is the portion of empty bins. The number of distinct values after hashing cn values with a range of n is therefor (1-1/e^c)*n $\endgroup$
    – Meir Maor
    Jul 12 '17 at 12:24

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.