Brute-force attack given small search-space and hash prefix Suppose we have a value $secret which is a random 56-bit (7-byte) string. Suppose an adversary wishes to discover $secret.  The adversary cannot directly see $secret, but he can see substr(sha1_hex("$secret $salt"), 0, 8) (where $salt
is public -- and perhaps irrelevant to our calculations).

Since $secret is only 56-bit, it may be vulnerable to a brute-force attack by a modern supercomputer -- if you can find an offline test. An attacker might use the hash-prefix as a test:


    function brute_force_hash_prefix($targetHashPrefix, $salt)
      $candidates = array()
      foreach possible $candidate which is 56-bits long
        $candidateHashPrefix = substr(sha1_hex("$candidate $salt"), 0, 8)
        if ($candidateHashPrefix == $targetHashPrefix)
          $candidates->add($candidate)
      return $candidates



However, the test is not deterministic -- the attacker only has the first 8 hex digits (32-bits) of the SHA-1 hash. This creates a risk of false-positives (ie the brute-force attack may return multiple $candidates which all yield the same first 8 hex digits).

The question: statistically speaking, how many $candidates should one expect to produce?

(Why would one care? If the odds are that only one $candidate will come through, then it's basically over.  Then again, if there are thousands or millions of candidates, then the attacker has narrowed the field...  but still needs to find some additional means for testing/filtering $candidate.)
If you have an $m-$bit output decent hash function (such as SHA1) and you're hashing $k-$bit values, and your list $L$ of candidates is not tiny ($2^{56}$ which is the size of possible candidates, isn't) the function will behave like a random mapping on any substring of its' output. 

If your prefix consists of 8 4-bit characters, then you'll 
be filtering roughly one out of every $2^{32}$ candidates during precomputation.

Thus, at the end of precomputation, you'll have $2^{24}$ candidates left.

In a large enough list is expected that whatever the correct input is, it has shown up as part of an unknown subset of roughly $2^{32}$ inputs in your filtered candidate list. Since you only have $2^{24}$ candidates left, it's likely that most of them are actually the unique candidate.