1
$\begingroup$

I am working on a project testing a hash that protects some data, and I've already eliminated hash length extension attacks as a possible point of compromise, and I'm trying to educate myself on all the variables.

Say I have some data that is hashed via SHA1 - will knowing parts of that hash (the end piece - basically a known value with an unknown prepended salt) help in breaking the hash/finding the salt at all, other than speeding up a brute force?

By knowing a portion of the hashed data, and the hashed output, would that help in finding the missing, unknown portion of the hashed data? Would it matter if this was hashed using a nonce, and you have multiple versions of the partial data and ending hash? (For example, two hundred hashes, all with the same salt, same known data, changing nonce)

From everything I've read, I BELIEVE the answer to all of the above is "No, it's of no help, you still need to spend years brute forcing it", correct? I just want to cover all my bases before I put faith, and my I'm-no-expert-why-are-you-asking-me seal of approval on/in a security setup I don't have direct control over (If it were up to me I'd HMAC it - but it's not - and I cannot).

Improve this question
$\endgroup$
3
  • $\begingroup$ "that hash" $\: \mapsto \:$ "that data" $\;\;\;$ ? $\;\;\;\;\;\;\;\;$ $\endgroup$
    – user991
    Commented Apr 4, 2015 at 0:09
  • $\begingroup$ You mean knowing some of the input to SHA1, or knowing some of the output? (you talk about knowing parts of the hash, but usually when we say "the hash" we mean the output of SHA1, not the input) $\endgroup$
    – D.W.
    Commented Apr 4, 2015 at 5:25
  • $\begingroup$ I think it helps more if the data is only long enough to fill the output sha1 buffer one time. If the data is longer knowing the end bytes helps less $\endgroup$
    – benathon
    Commented Apr 5, 2015 at 11:34

1 Answer 1

Reset to default
1
$\begingroup$

It all depends on whether the rest of the input is guessable.

The best attack we know for finding the input to SHA1, given the output and partial knowledge about the input, is a brute-force attack:

  • For each candidate at the full input, try hashing that input with SHA1 and see if it matches the known output.

So, the running time of the attack will be proportional to the number of candidates we need to try. If part of the input is known, the running time will depend on how easy it is to guess/predict the rest of the input.

For instance, if the unknown part of the input is a 4-digit PIN, and the rest of the input is all known, then the system is definitely vulnerable. There are only $10^4 = 10000$ candidates for the full input, so you can try each one of them. This won't take very long.

As another example, if the unknown part of the input is a 128-bit secret value, and you have no way of predicting that input, and all 128-bit values are equally likely, then the system is safe. There are $2^{128}$ candidates for the input, and you can't try them all. Also, they're all equally likely, so you can't even get a speed-up by trying the most likely candidates first -- all the candidates are equally likely.

In general, if the entropy of the secret part is at least 128 bits, you should be good.

Improve this answer
$\endgroup$
4
  • $\begingroup$ And knowing the hashed values with an incremental nonce doesn't help a bit either, correct? Like I said - I'm almost positive I know the answer was "no, just brute force" but want to be absolutely sure. $\endgroup$
    – InfernusDoleo
    Commented Apr 4, 2015 at 5:46
  • $\begingroup$ @InfernusDoleo, I can't answer that, because it's not clear what you intend the full input to the hash to be. If you want a more detailed answer, list all the parts of the input to the hash and what is known about each. An incrementing nonce counts as a known/predictable part of the input, since it can be predicted. $\endgroup$
    – D.W.
    Commented Apr 4, 2015 at 17:50
  • $\begingroup$ There is a secret key, which is large... 26 characters I believe, then a key thats based on the requesting IP and username (cannot control that completely, but it's known), and then a nonce. So about half of the data is unknown. Will knowing any of the end data help? (Other than obviously appending it before brute forcing). Like I said - the secret key doesnt change. So it's possible to get 200, 2000, 20000 hashes where the ONLY change is the nonce. With that much input data, is that a help at all? $\endgroup$
    – InfernusDoleo
    Commented Apr 5, 2015 at 3:15
  • $\begingroup$ @InfernusDoleo, you'll be fine, if that 26-character secret key is truly secret and chosen uniformly using a crypto-quality randomness source. That large secret key means that the space of candidate inputs is very large, so brute-force won't work. The fact that you can see many outputs with related inputs doesn't help given that the secret key is so large. $\endgroup$
    – D.W.
    Commented Apr 5, 2015 at 17:58

Your Answer

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

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