Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Timing attacks can have a devastating impact in scenarios where the secret is involved, often in cases where byte-wise array comparison is used.

Now there are those that advertise using constant time array comparison in any situation where data is compared that was derived from a secret, not only when comparing the secret itself. The rationale is "better safe than sorry". Although this is fine, I'm still wondering if it is really necessary all the time.

A particular case where I would tend to think that constant time array comparison is probably unnecessary is comparing stored password hashes with those provided by the user. Let's assume the password was properly stored using for example bcrypt. If the application uses short-circuiting array comparison, an attacker could gain information about the "number of correct bits" of arbitrarily chosen passwords by evaluating the time it takes for a response.

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?

I would be interested in the following:

  • Existence of theoretical results that prove that such an attack is (in-)feasible for one-way (compression) functions that do not assume the hash function to be (pseudo-)random
  • Negative/positive results for real-world hash functions such as MD5, SHA-1 etc.
share|improve this question

1 Answer 1

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

share|improve this answer
    
OK, it seems infeasible if we assume the hash function to be (pseudo-)random. But are there results for the weaker assumption of only a collision-resistant (compression) function? Regarding hashing dominating the comparison - statistics should still render it possible to find any bias, given a large enough set of samples. See for example Remote Timing Attacks Are Still Practical. –  emboss Nov 25 '11 at 1:22
1  
"even knowing the hash and salt would not give the attacker a significant enough advantage to derive the password" I disagree. It would give the attacker a way to perform an offline, unbounded, dictionary attack on the password. This is a strong attack on weak passwords, which is the standard assumption. (If it is guaranteed that passwords are strong, you do not need either salting or bcrypt - MD5 alone would be fine.) Without hash and salt, the attacker can only do an online attack, and the server can slow it down, so that only a few hundred passwords can be tried. –  curiousguy Nov 25 '11 at 1:41
    
@emboss "only a collision-resistant (compression) function" Hug? –  curiousguy Nov 25 '11 at 1:42
    
@curiousguy Today's hash functions are no (pseudo-) random functions. Collison resistance does not imply randomness per se. Maybe that could still allow the possibility of such an incremental attack for non-random hash functions? –  emboss Nov 25 '11 at 1:52
    
@curiousguy Of course, we would prefer if the attacker wouldn't know hash and salt (i.e. couldn't do an offline attack), but a password should normally hashed in a way that even an offline attack (for example from a leaked backup copy of the database, or a rogue sysadmin) will not compromise the passwords. (The rest of my answer is trying to show that we won't get that much information.) –  Paŭlo Ebermann Nov 25 '11 at 1:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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