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

$\endgroup$
  • $\begingroup$ "that hash" $\: \mapsto \:$ "that data" $\;\;\;$ ? $\;\;\;\;\;\;\;\;$ $\endgroup$ – user991 Apr 4 '15 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. Apr 4 '15 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$ – portforwardpodcast Apr 5 '15 at 11:34
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.

$\endgroup$
  • $\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 Apr 4 '15 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. Apr 4 '15 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 Apr 5 '15 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. Apr 5 '15 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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