Is this SHA-256 modification still valid?

Question

We typically model a hash function (in particular $\mathrm{SHA}$-$256$) as a function $H:\{0,1\}^{2^{64}-1} \to \{0,1\}^{256}$ with some special properties that makes them useful in practice. In this case, the probability for a collision is around $2^{-256}$ which is assumed to be infeasible in practice.

Now (because $256$ bits seems too long to handle for me), I want to cut some of them off and still keeping an (almost) infeasible probability of having a collision. In other words, which is the correct amount of bits I have to truncate so that I still have a good collision resistance? It is just $2^{-m}$, where $m$ denotes the bits that you keep from the beginning?

To illustrate what I mean, Imagine that the beginning of two outputs of $H$ are $1011100...$ and $1011000...$. If I just decide to cut off $4$ bites then I have a collision ($1011$), otherwise I don't.

Where could I find when (and why) a probability is "low enough" in practice? I assume it is something related with computer's limits...

---

The idea behind this question is using tracking hashes easy to handle by users. An upper bound for the number of users is $2$ millions. Since $256$ bits is too large (it is still large if you use base-$16$ or base-$64$), we though to prune some amount of bits if it is secure to do that. Two users with the same pruned hash would mean a disaster.

Answer 1

We typically model a hash function (in particular $\mathrm{SHA}$-$256$) as a function $H:\{0,1\}^{2^{64}-1} \to \{0,1\}^{256}$ with some special properties that makes them useful in practice.

Well, that definition is indeed rather particular to SHA-256. The output size is of course depending on the hash function, and e.g. SHA-3-256 has an infinite input space.

In this case, the probability for a collision is around $2^{-256}$ which is assumed to be infeasible in practice.

No, for the function the probability for creating a collision using many tries is closer to $2^{-128}$ because of the birthday bound. You're showing the chance of a pre-image happening, and that only for a single try. Discussing collision resistance for hashes over any two distinct messages doesn't make much sense.

Where could I find when (and why) a probability is "low enough" in practice? I assume it is something related with computer's limits...

Depends on how the hash function is used and the threat model of the particular use case. If you'd ask me about a generic minimal security limit then I'd go for 128 bits (presuming only attacks using classical computers). That would mean a 256 bit hash when it comes to collision resistance - and not pruning any bits.

Now for particular use cases you may go lower. You may want to keep in mind that generating $2^{128}$ hashes is not practical; the birthday bound assumes you compare many hashes after all. So there is probably some leeway when it comes to memory requirements for any attack.

Keyed hashes (HMAC) are a different matter entirely. There you would only need 128 bits to achieve 128 bit security.