0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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? $\endgroup$
    – Morrolan
    Aug 9, 2022 at 15:51

1 Answer 1

Reset to default
2
$\begingroup$

if I find the prefix P2 in the database what is the false positive probability of me flagging H2 as being in the database?

Well, that depends on the probability distribution that S1, S2 are chosen from (in particular, how many possibilities are there for S2).

If S1, S2 are limited to 2 characters, the probability of a false hit is essentially 0; with so few possibilities, the probability that two different values for S would happen to have the same 64 bit hash is close to zero.

On the other hand, if S1, S2 are a gigabyte of random bits, the probability of a false hit is essentially 1; every 64 bit hash will have a huge number of potential preimages, and so it is quite unlikely that, even with a hit on P1, that you happened to stumble on S1 = S2.

Improve this answer
$\endgroup$
3
  • $\begingroup$ S1 and S2 are between 6 and 30 bytes with an average length of 12 $\endgroup$
    – Pedro Paixao
    Aug 9, 2022 at 18:47
  • 1
    $\begingroup$ @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... $\endgroup$
    – poncho
    Aug 9, 2022 at 18:57
  • $\begingroup$ Thank you @poncho. Strings are a-zA-Z0-9. Random but not uniformly distributed as some combinations do happen more than others. There’s much more strings all lower case for instance. $\endgroup$
    – Pedro Paixao
    Aug 10, 2022 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.