4
$\begingroup$

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.)

$\endgroup$
6
  • $\begingroup$ What's a character, in terms of bits, in your implementation? Is the output of sha1_hex() in hex, so each character is 4 bits of the hash, and the first 8 characters are the first 32 bits of the SHA1 hash? $\endgroup$
    – D.W.
    May 6, 2015 at 7:14
  • $\begingroup$ Correct. The prefix is 8 hex digits or 32 bits. $\endgroup$
    – Tim Otten
    May 6, 2015 at 7:58
  • $\begingroup$ I encourage you to edit the question to incorporate this information. Comments exist to help you improve the question; clarifications shouldn't be left in the comments, as they can disappear at any time, and readers shouldn't need to read the comments to understand what you're asking. $\endgroup$
    – D.W.
    May 6, 2015 at 8:54
  • $\begingroup$ Good point. Updated. $\endgroup$
    – Tim Otten
    May 6, 2015 at 9:01
  • $\begingroup$ One more question would be: What is the actual goal of this? If the attacker can only see a partial hash, why is that? Is this used in some scheme, and only the first 32 bits are checked? This would be pretty terrible. What happens if an attacker finds a matching candidate, which is not the actual secret? $\endgroup$
    – tylo
    May 6, 2015 at 9:15

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ I'm reading " the attacker only has the first 8 characters of the SHA1 " as meaning the first $8\cdot4=32$ bits of the hash. Thus it is expected about $2^{24}$ candidates. $\endgroup$
    – fgrieu
    May 6, 2015 at 5:12
  • $\begingroup$ @fgrieu: fair enough, I am not a practicing cryptographer, hence my possible confusion. $\endgroup$
    – kodlu
    May 6, 2015 at 5:12
  • $\begingroup$ Confirmed - I did mean a prefix of 8 hex digits (32 bits), so 56-32=24 bits (~16 million candidates) makes sense. (Aside: Agree 2^56 is not a small search space. It's hard to convey the thought in a pithy title -- basically, it's in a range where a contemporary supercomputer can brute-force.) $\endgroup$
    – Tim Otten
    May 6, 2015 at 5:21
  • $\begingroup$ Oops, fixed! I must have traded some sleep time. $\endgroup$
    – kodlu
    May 6, 2015 at 5:21
  • $\begingroup$ This answer is incorrect. It assumes we only have 8 bits of the hash, but as the OP has clarified, we actually have 32 bits of the hash. $\endgroup$
    – D.W.
    May 6, 2015 at 8:55
3
$\begingroup$

We learn the first 32 bits of the SHA1 hash of the secret (well, it's actually the SHA1 hash of the secret concatenated with some known stuff, but that amounts to the same thing). We can enumerate all $2^{56}$ possibilities for the secret. We expect that about $1/2^{32}$ of them will produce a matching 32-bit value, so about $2^{24}$ candidates for the secret will remain.

An attacker would need some other source of information to recognize which of those $2^{24}$ candidates is the correct one.

$\endgroup$

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.