Timing attacks in password hash comparisons

Question

I had a discussion with a friend today about his password hash comparison. I argued that you can't return false on the first hash mismatch you have and I sent him a link to an article about a Java timing attack that happened in Java 6.

public static boolean isEqual(byte digesta[], byte digestb[]) {
    for (int i = 0; i < digesta.length; i++) {
        if (digesta[i] != digestb[i]) {
            return false;
        }
    }
    return true;
}

And my version, which I think is correct:

public static boolean isEqual(byte digesta[], byte digestb[]) {
    boolean isEquals = true;   
    //this avoid a possible timing attack
    for (int i = 0; i < digesta.length; i++) {
        if (digesta[i] != digestb[i]) {
            isEquals = false;
        }
    }
    return isEquals;
}

Which, for me, indicates there is a possible timing attack that could be done because you return false if there is a mismatch in the hash. He argued that this would not be a risk in the application and that the important thing is that the password is salted and hashed and that will probably will not affect the security of the application.

Am I paranoid about the security of my application?

Answer 1

The first algorithm is sensitive to timing attacks, while the second looks better (but I don't know for sure if it's vulnerable or not). However, there is a bug with potential security implications in the second version: What happends if the two strings have different lengths?

Timing attacks are a real security issue that it is reasonable to be worried about, so you are right to bring the issue up. I could partly agree with your friend in that it is more important to use salt and a good hashing algorithm. This however does not mean that timing attacks are not important or should not be taken seriously. They should.

However, in this case, it is not obvious how an attacker could pull off a timing attack. Since the input (the password) is hashed with a salt, the attacker probably can't freely control what any of the compared hashes will be. That means it might not be possible to search your way to a matching hash. But all this depends on how the entire system is built, not just on the string comparison algorithm.

One good way to deal with all of this is to use a good library for the hashing. A well written library should take care of both salting and defense against timing attacks for you, without you having to go through the hassle to write all the code yourself.

Answer 2

You're both right, but you've both missed the point :)

You are correct: this is a classic example of a timing weakness and creates a possible side channel attack.

Your coder is correct: given network travel times and other mitigating factors that you naturally put in (brute force detection, up lockout, etc...) it is very unlikely that an exploit is possible.

However, that isn't my main concern. This is a classic example of a timing vulnerability, AKA this is a pretty basic security vulnerability. Therefore I would assume that whoever wrote this code is not as experienced with managing passwords and hashes as they probably think they are. This leads to a very natural question: what else did they unknowingly get wrong?

Without a full code/system review from someone who is an expert in this area, you'll never know the answer to that question. As a result I suggest you take @Ander's advice: switch to a standard library.

Answer 3

The second piece of code you showed is still susceptible to timing attacks. This is because how many times the if-branch is taken, and in what sequence it is taken, are dependent on the input data.

Here is an algorithm that is resistant to timing attacks on any reasonable CPU:

public static boolean isEqual(byte digesta[], byte digestb[]) {
    if (digesta.length != digestb.length)
        return false;
    int difference = 0;
    for (int i = 0; i < digesta.length; i++)
        difference |= digesta[i] ^ digestb[i];
    return difference == 0;
}

Answer 4

You are correct. Because you wrote the code to check the hash character by character (why are you doing that?), it would be possible to use timing to work out the correct hash character by character. But that would be no different from trying random passwords. You just know which of your attempts resulted in a close hash. It doesn't inform your next guesses.

Add to that the idea that you should also have numerous other protections against brute-force attacks, and this is not a big threat.

Answer 5

If the password is stored plainly clearly the first code can cause a remote timing attack. The second one only leaks about the number of if condition satisfied. Can this leak be used for remote timing? It is not clear without a real.

If the second is written the if condition as ( using C)

int strctcmp(const char*digesta, const char*digestb)
{
  int equal = 0;
  for (; *digesta && *digestb; ++digesta, ++digestb)
  {
    equal |= *digesta != *digestb;
  }
  return equal;
}

then it is a true constant time that eliminates the information of the number of equalities. The string length are always equal since the attacker cannot control the length. Coding is not enough and one also need to consider the compiler optimization. Therefore one either check the result or use in assembly. There is a great page about constant timing on BearSSL pages written by the Thomas Pornin.

When the salt is introduced and a password hashing is applied like Scrypt, PBKDf2, Argon2 the remote timing attack becomes impossible for both cases if the salt is not known. Since the attacker can only get the comparison timing of hashed passwords. We expect them to have avalanche criteria, which is a bit change in the input flips each output bit with 50%. So the attacker has no knowledge about the result in order to get information.

If the salt is known, then the attacker can use this knowledge to produce the necessary hash values as vectors to execute a remote attack. Producing the test vectors will require too much time since we cannot control the output of a hash. So in this case it is impossible to good passwords. If the password is weak, then the attacker can try all and compare the timing too. Wait, are you allowing that much password testing, then reconsider your system security.

Conclusion: Your friend is correct, If salted and hashed correctly, and the incorrect trial limit is set then there is no problem.

Answer 6

... maybe the second isn't vulnerable to a timing attack until it runs through an optimizer. Java runs code optimization passes for over 20 years, haven't they? i bet the 2nd implementation is vulnerable in practice, if you inspect the java bytecode it compiles to...

the traditional way to do a constant-time string comparison is:

bool is_string_equal_constant_time(const string &str1, const string &str2){
    if(str1.size()!=str2.size()){
        throw invalid_argument("both strings must be the same length to compare them in constant-time! sha2 hash em or something");
    }
    int result=0;
    for (size_t i = 0; i < str1.size(); ++i) {
        result |= str1[i] ^ str2[i];
    }
    return (result==0);
}

and i'm guessing there's a good reason it's done that way (PS: i don't do java, i don't know how to do it in java, but this is how it's done in C++, it should be easy to port to Java for someone who knows java.)

Answer 7

The answer to this is the single most important aspect of cryptography: you need a threat model. Your threat model dominates answers like these. The correct answer for how to keep your little sister out of your diary is very different from the answer when dealing with state level actors.

Salting and hashing defend against a different kind of attack than these timing-attack-free algorithms are trying to deal with. Salting and hashing is all about how you protect against an adversary that can get their hands on your data at rest -- i.e. the passwords file on your hard drive. If they can get their hands on that, salting and hashing is an essential part of protecting that data.

But that's only one threat model. There's other threat models that worry about timing attacks, where an adversary finds a way to execeute code on your computer while it is online. This creates totally different attack vectors. For example, you may lock down your data perfectly, so that an adversary could never crack the passwords given that they steal the hard drive, but you permit them to run some small scripts as part of the normal business uses of this server. Suddenly they can use this to create a timing attack.

Or worse, you wisely isolate this server so that it only runs your secure software, because you knew that these timing attacks were not in your threat model. Then, one day, someone decides to save a bunch of money by virtualizing these computers and sticks your secure application on a physical computer that's shared with a less secure app. Thanks to virtualization, you know your data is safe, but an attacker can go after you by using the less secure server and leveraging timing attacks.

So the question becomes "what is your threat model." What sort of adversary are you trying to defend against? Are you just trying to keep some data safe from script kiddies? Or are you worried about a state-level actor expending millions of dollars worth of resources to attack your computer? Sometimes you may have to consider timing attacks. Other times, you may not.