6

I recently came across some password code that hashed the password and then compared it with the saved hash in the naive way: one character at a time, short-circuiting as soon as a non-match was found. We agreed it was a security bug and fixed it.

However, this code piqued my curiosity: suppose an attacker is able to glean from the timing of password checking the number of hash digits that match. How could this bug be exploited in practice? I understand security should be deep and you need not find a practical exploit to take a security measure - I'm asking purely out of curiosity.

For example, the attacker might try progressively extending the hash one character at a time. But if the hash is n digits long, the attacker eventually needs to extend from n-1 digits to n digits. Assuming a good hash function, this seems to require a full pre-image attack. Assuming the attacker can compute the hash, which requires the attacker to have the salt if there is one, this attack could largely be performed client-side (given n digits in base b, a maximum of n*b queries to the server are required). But hash functions are chosen to resist pre-image attacks so is this exploit practical?

Improve this question
3
  • 1
    If there is no salt, you could do a dictionary attack where most of the work is client side, and only those n*b requests need to go over the network. That would be a major weakness. But with a salt... I don't see how you could attack that. Not sure though. Very interesting question. – Anders May 11 '18 at 13:17
  • @Anders Good point that this requires the attacker to have the salt. I don't think we rely on the privacy of the salt so I guess we assume the attacker has it. – Reinstate Monica May 11 '18 at 13:45
  • I'm tempted to say that the odds of the attacker having the salt but not the full hash is low, but on the other hand it is always prudent to assume that all information that is not explicitly secret is completely public. – Anders May 11 '18 at 13:48
3

This answer on crypto.SE outlines the attack Anders points out in the comments. Even if there is a salt it's still best practice to make it a time-safe comparison simply because salts are assumed to be public information, though in practice it seems unlikely it'd be a big issue unless you divulge the salt without also divulging the password hash.

Your assumption about this attack requiring a first pre-image attack on the hash seems logical, but it has a major problem: the pre-image space that matters is the pre-image space of hashed passwords, not of the hash itself (i.e. the preimage of H(p) where p is a password rather than H(d) where d is any data). This is a problem even with a slow hash because that pre-image space can be much smaller, such as trying the 220 most re-used passwords (vs eg 2128 for the hash itself).

Improve this answer
1
  • So this attack requires a brute force of the dictionary but allows it to be done largely client side. – Reinstate Monica May 11 '18 at 13:59

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.