How can short-circuit hash equality be exploited?

Question

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?

Answer 1

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 2²⁰ most re-used passwords (vs eg 2¹²⁸ for the hash itself).