# SHA256 Collisions

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?

• There are collisions, by the pigeonhole principle.
– fgrieu
Jul 9, 2017 at 22:10
• @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? Jul 9, 2017 at 22:17

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")

• Yeah, but if half are collisions... Jul 10, 2017 at 8:04
• @ThatGuy half of 2^256 is 2^255. Good luck storing that list of hashes for comparison. Jul 11, 2017 at 1:47
• 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. Jul 11, 2017 at 9:05
• "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.
– fgrieu
Jul 12, 2017 at 4:49
• 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 Jul 12, 2017 at 12:24