Probability of SHA256 Collisions for Certain Amount of Hashed Values

Question

I wonder if you can help me figure out that question:

Is there a known probability function f: N -> [0,1], that computes the probability of a sha256 collision for a certain amount of values to be hashed? The values might fulfill some simplicity characteristics to reduce the complexity of the problem e.g. all of them are of equal difference to each other with a constant difference t or whatever is needed to somehow reduce it to manageable complexity.

In other words: How likely is it to have sha256 hash collisions in a "simple" set of n values?

Yeah, I'ld like to hear your thoughts about that :) Thanks for all helpful comments / answers in advance!

EDIT
Background is: I wonder if it is possible to decide when the change to a 'higher' hash function (like changing from sha256 to sha512) makes sense - not only by having an eye on experiments but by theory.

Answer 1

The wikipedia page for the Birthday problem gives the details, including the exact formula.

As an approximation you can use:

$$p \approx 1-\exp(-\frac{\tfrac{1}{2}n(n-1)}{2^{256}}) \approx 1-\exp\left(-\frac{n^2}{2 \cdot 2^{256}}\right) \approx 1-\exp\left(-\tfrac{1}{2} \left(\frac{n}{2^{128}}\right)^2\right)$$

If $n \ll 2^{256/2}$ and thus $p \ll 1$ you can use the approximation $\exp(x) \approx 1+x$ and obtain:

$$p \approx \tfrac{1}{2} \left(\frac{n}{2^{128}}\right)^2$$

This means that the probability is negligible as long as you have significantly less that $2^{128}$ values. (For an idea of "how significantly" less, refer to the table on the Wikipedia page, "Desired probability of random collision".) That's the case for any realistic amount of data, so an unbroken 256 bit hash is good enough and there is no need to upgrade to 512 bits.