Or, a gentle introduction to timing attacks

One of my favorite things about software security is making people aware of what they didn’t KNOW they didn’t know. That’s not a typo, by the way. And this topic is one such example. Enjoy!

When I see a system that compares passwords, my first response is “Why are you handling passwords?” No modern system should handle passwords directly unless there’s an ancient legacy reason. Even then I’d consider ways to get away from handling the passwords.

With that said, I have seen more than one system over the years that DID need to compare secret data such as passwords.

And every single one of them got it wrong!

I think we have all seen code like the code below at some point.

static bool DoPasswordsMatch(string pwd1, string pwd2)
{
    if (pwd1.Length != pwd2.Length)
        return false;

    for (int i = 0; i < pwd1.Length; i++)
        if (pwd1[i] != pwd2[i])
            return false;

    return true;
}

The code checks if the passwords are the same length, and if they are not, then clearly the passwords are not the same so the function exits.

If the passwords are same length then the code does a byte-by-byte compare of the strings and if there is a mismatch at any point the function returns.

If all is well, and the passwords match the function returns true.

This code is broken because of timing attacks. In the example code, if an attacker provides one password and the password is not the same length as the real password, then the function exits quickly. In other words the attacker can now know the passwords are not the same length.

It’s this ‘short-circuiting’ that causes the problem.

Note this issue is not restricted to passwords, your code could compare AppID secrets or any other authentication secret.

Plenty has been written on this topic over the years:

https://blog.ircmaxell.com/2014/11/its-all-about-time.html 

https://wiki.php.net/rfc/timing_attack

https://stackoverflow.com/questions/25844354/timing-attack-in-php

https://security.stackexchange.com/questions/111040/should-i-worry-about-remote-timing-attacks-on-string-comparison

https://security.stackexchange.com/questions/97798/feasibility-of-time-based-database-brute-force-attacks-on-websites

https://stackoverflow.com/questions/37633688/constant-time-equals

So how do you fix this? For systems that MUST perform some form of comparison of secret strings, using code like the following will mitigate the risk substantially. It does so by removing all forms of short-circuit logic.

bool TimeConstantCompare(string hashName, string s1, string s2)
 {
     var h1 = HashAlgorithm.Create(hashName).ComputeHash(Encoding.UTF8.GetBytes(s1));
     var h2 = HashAlgorithm.Create(hashName).ComputeHash(Encoding.UTF8.GetBytes(s2));
     int accum = 0;

     for (int i = 0; i < h1.Length; i++)
         accum |= (h1[i] ^ h2[i]);

     return accum == 0;
 }

The way this code works is it first hashes the two strings; for example, hashName is SHA256 and this yields two series of bytes of equal length. Now the fun starts – the code walks over the two series of bytes XOR-ing each byte, if the bytes are the same the result is zero. If the bytes are not the same, then the result is non-zero. The result is then OR-ed with an accumulator, this means that if ANY bytes are not the same, the non-zero result is carried forward.

At the end of the function, if the accumulator is zero, then the bytes are the same which means the two strings match. All in constant time!

I posted some C# code up on GitHub.

tl;dr: Don’t compare passwords. If you MUST compare passwords don’t do a naive string compare. Use a time-constant compare instead.