# False positive error rate of truncated hash match

I’m having difficulty calculating the false positive error probability of matching a prefix of a hash that was truncated to m bits.

Say I have string S1 that produces a SHA256 hash H1. I then save the the first 64 bits of H1, call it prefix P1 to a database.

I have another string S2 that produces a SHA256 hash H2, and 64 bit prefix P2.

If I can’t find prefix P2 in the database I know for sure that H2 is not on the database. False negative probability is 0, but if I find the prefix P2 in the database what is the false positive probability of me flagging H2 as being in the database?

• For SHA256 a common assumption is that it behaves as a random oracle - that is that its outputs are indistinguishable from those produced by a uniform random distribution. Then, your question becomes one of basic probability theory: Given two randomly chosen bit strings of length 64, what is the chance that the two are equal? Aug 9, 2022 at 15:51

• @PedroPaixao: it still depends on the number of possibilities (and the probability distribution, if not uniform); if each byte is selected randomly, then even if we have a limit of 12 bytes, that's still 96 bits; a collision in P1 is likely to be a false hit. On the other hand, if S1, S2 are (say) English sentences, well, there are fewer than $2^{64}$ grammatical English sentences of that length; the probability of a false hit would be minimal... Aug 9, 2022 at 18:57