1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ The probability $p$ of collision depends on the number $n$ of hashes. For SHA-256 modeled as an ideal $b=256$-bit hash, it is $p=2^{-b}$ for $n=2$ hashes. See my Birthday problem for cryptographic hashing, 101 for how $p$ evolves as a function of $n$ and $b$ (here $b$ is $256$ minus the bits removed). This is not an answer because the question does not define it's validity criteria. It's not even clear that probability of collision is what matters in the application. $\endgroup$ – fgrieu♦ Sep 15 '20 at 15:45
  • 2
    $\begingroup$ Related What are the consequences of removing a single byte from a sha256 hash? $\endgroup$ – kelalaka Sep 15 '20 at 18:42
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ "probability for creating a collision using many tries is closer to $2^{−128}$" is correct, for some value of many like $2^{64.5}$. But I think that you want to say that the probability of collision becomes sizable (>39%) after $2^{−128}$ tries. $\endgroup$ – fgrieu♦ Sep 15 '20 at 16:30
  • $\begingroup$ @frieu Yeah, I've found the formula, but I've yet to check some interesting values. $\endgroup$ – Maarten Bodewes♦ Sep 15 '20 at 18:04
  • $\begingroup$ @fgrieu Well, if you have some values please insert them because it is getting late and I have decided to quit around 23:00 CET. Probably only have time friday. $\endgroup$ – Maarten Bodewes♦ Sep 15 '20 at 20:47
  • $\begingroup$ @MaartenBodewes I don't see why $128$ bits is a good amount. I also added the idea that originated the question, if that helps. $\endgroup$ – Bean Guy Sep 16 '20 at 8:06
  • $\begingroup$ I'm not entirely sure about the use of the hash in this case or what security it brings. If the attacker can not add additional hashes to the set that is being verified then 128 bits could be enough (or you could add 21 bits to keep to 128 bit security). However, what protection the hash itself provides is unclear to me. Maybe you do require a HMAC instead - but this gets into a consulting service fast... $\endgroup$ – Maarten Bodewes♦ Sep 16 '20 at 11:02

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.