Short version: I think there is no danger doing short-cut comparison of salted hashes of passwords, if the salt is hidden to the attacker.
Long version:
Using timing attacks in this case will in no way tell an attacker more than what he would know if he had the actual stored hash and salt ... and brypt's security parameter (iteration count exponent) should be chosen such that even knowing the hash and salt would not give the attacker a significant enough advantage to derive the password (since he would have to brute-force the password from this).
On the other hand, if the attacker does know neither the used salt nor the stored hash, I would guess that a timing of the comparison of calculated and stored hash will not give any information at all, since every (even single bit) change of the password input will result in a completely different hash.
(This applies to every pseudo-random function, not only bcrypt. We actually need only the avalanche effect here.) See below for a more formal elaboration.
Other than this, normally the hashing process itself is included in the measuring, which takes much longer than the final comparison at the end, and thus will dominate the total measured time. I don't know how much this hashing time will variate, though.
Mathematical version:
Now my question is whether this can be transformed into a
"better than brute force" attack? Is there a possibility for
an incremental attack, i.e. is it possible to construct a
password with n+1 correct bits from a password with n correct
bits other than using brute-force guessing?
So we have a function c_h(y), which is the number of leading bits
matching between H(s, y) and h. Let m be the total number of bits of H's output.
Assume we have an algorithm A which can do your attack, i.e. an algorithm which,
for a hash h (unknown to A) and a given message x with c_h(x) = n, finds a message x' with c_h(x) >= n+1, in time better than exponential in n.
(Simple brute-forcing the hash is exponential in n.) We can assume that this algorithm has O(1) oracle access to c_h(y) for arbitrary y.
Then we can from this construct an algorithm B which will do a preimage attack on a given hash h and salt s, i.e. finds a message z with H(s,z) = h. It works as follows:
- The oracle for A is simply done by calculating
H(s,y) and
comparing it with h, counting the correct bits until the first non-match.
- We choose an arbitrary message
x_0, calculate n_0 = c_h(x_0).
- For each i > 0:
- We pass
x_(i-1) to A, and get back x_i with n_i = c_h(x_i) > n_(i-1).
- if
n_i = m, stop and return z = x_i.
The output of B is a preimage for (s, h).
As each n_i is larger than the previous one, this will take at most m passes through the loop, with each pass taking at most o(exp(n_i)) time, i.e. in total o(exp(m)). Thus we got a sub-exponential preimage-finding algorithm.
This shows that, assuming H is preimage-resistant, there can't be an algorithm which efficiently produces longer partial matches from shorter partial matches, given the match length as an oracle.
(I assume one can refine my timing approximation a bit better.)
Notes regarding the comments:
As the comment thread is getting quite long, I'll try to resume the important points here:
With weak passwords, an offline dictionary attack on password hashes
will become feasible, which would be our algorithm B. This is why
we want to choose the bcrypt work factor high enough.
Still, I see
no way to get from a fast B (offline preimage attack with given salt)
to a fast A (online partial preimage finder from hash prefix length oracle)
algorithm, only the other way around.
I expect that even for functions which are preimage-broken there
would be no easy way to get our online attack, as long as they
still fit the avalanche criterion.
Real-life hash functions are not really random (which is caused
by their iterative design), but this does not really affect their
suitability for password hashing, which works on inputs shorter
than the block size.
The important property here is preimage resistance, not collision resistance.
(Every collision resistant function is second-preimage resistant, and
second-preimage resistant functions are preimage resistant - though
we usually expect a higher resistance against (second) preimage attacks
than given by this reduction from collision resistance, due to the generic
birthday attack to find collisions.) This means this proof applies
to MD5 (which is broken collision-wise), as long as there is no preimage
attack.
The proof above does not rely on the hash function being a random oracle,
it just uses an oracle access to c_h(y), which abstracts the timing
measure for the
