Constant time string comparision in PHP to prevent timing attacks

Question

I've been advised that when checking the password hash for a user I should use a string comparison function that always takes the same amount of time, to avoid timing attacks.

So I wrote this:

//this is a constant time string compare,
//it does not exit early even if the strings don't match
//it is case sensitve
//the time to compare is the time needed for the shorter string
//(if they are not the same length)
function time_strcmp($str1, $str2)
{
  $res = $str1 ^ $str2;
  $ret = strlen($str1) ^ strlen($str2); //not the same length, then fail ($ret != 0)
  for($i = strlen($res) - 1; $i >= 0; $i--) $ret += ord($res[$i]);
  return !$ret;
}

(I do it this way instead of checking equality in a loop just in case of optimization. Not sure if PHP does any, but it might in the future.)

Anyway, since this is such a critical part of the code, returning true when it shouldn't would completely defeat security.

Can anyone give me a code review? Or a better way?

Answer 1

Disclaimer

I have no formal education in security or cryptography, nor any kind of meaningful experience with either.

This post is basically me rambling, hopefully correctly :-).

Correctness

This is a very informal (and rough) analysis, but hopefully it will assure you that your function is indeed correct.

---

function time_strcmp($str1, $str2)
{
    $res = $str1 ^ $str2;
    $ret = strlen($str1) ^ strlen($str2); //not the same length, then fail ($ret != 0)
    for($i = strlen($res) - 1; $i >= 0; $i--) $ret += ord($res[$i]);
    return !$ret;
}

Assume that $str1 and $str2 are arrays of bytes, each n1 and n2 bytes long, respectively.

In PHP, the ^ operator is defined for strings such that:

$s1 ^ $s2 == chr(ord($s1[0]) ^ ord($s2[0])) . chr(ord($s1[1]) ^ ord($s2[1])) . ... chr(ord($s1[L]) ^ $s2[L])
with L = min(strlen($s1), strlen($s2))

You've used this to your advantage in that any matching characters bytes mask to 0, and any non-matching bytes will mask to a value that is greater than 0.

So $res will be filled with 0s only if $s1 === $s2 with:

$l = min(strlen($str1), strlen($str2));
$s1 = substr($str1, 0, $l);
$s2 = substr($str2, 0, $l);

(1) So basically $res will be 0-filled only if the strings exactly match or if one of strings in its entirety is a prefix of the other.

---

$ret = strlen($str1) ^ strlen($str2);

(2) $ret will be 0 only if $str1 and $str2 are of the same length.

(For later, let this be denoted $ret0)

---

for($i = strlen($res) - 1; $i >= 0; $i--) {
    $ret += ord($res[$i]);
}

(3) $ret will now be equal to the sum of the value of all of the bytes of $res.

Let the amount added to $ret in this loop be denoted $ret1.

(4) From (1), we can conclude that $ret1 will be 0 only if the strings exactly match or one of the strings is a prefix of the other.

---

Recall:

$ret = $ret0 + $ret1;

From (2) and (4) we can conclude that $ret will be 0 only if strings are of the same length and no bytes differ in them. This means that $ret will be 0 iff $str1 === $str2.

So yes, your function is functionally correct.

---

Timing

I can't comment much on this. You will of course want to make sure that the length of the shortest string is always the same, otherwise there will be a difference in timing.

Also, I believe strlen() is O(1) in PHP, but you may want to verify that.

---

Minor suggestion #1

There's a very unlikely problem with adding the values of the bytes. If there exist a sufficient number of unequal bytes, their values may exceed the maximum of an integer. Bitwise operators are undefined (I believe) for floating types in PHP. What you could do instead of adding is use bitwise OR.

(I realized the overflow when seeing it, but the bitwise OR, I lifted from: here)

---

Ponderings

Typically hashing algorithms output hashes of the same length for all inputs. This means that a difference in values is likely your concern.

For example, with a short circuited comparison:

'abcd' === 'abce' 
'abcd' === 'bbcd'

The first one will take more time to execute than the second since the second will bail out on the first letter.

Consider now what this timing attack would allow you to determine. It would allow you to determine part of the hash, not the password (though if you could actually determine the hash in full, you would have already found a collision and thus have gotten into the system).

This seems fairly harmless to me just because of the cascading changes in hashing algorithms.

Just because I know that A is more of the hash than B is does not mean that I'm any closer to finding the hash unless I know how to change A in a manner such that the first N bytes of hash(A) do not change. Being able to figure that out would be a major security problem for any cryptographic hash.

I feel like there's something I'm missing here, so if I've completely missed the point in this section, please tell me.

Answer 2

Starting from the top:

function time_strcmp($str1, $str2)

It's important to distinguish between the known and given string; the length of a given string is public, but the length of the known string must be secret. Therefore both arguments should have a name that conveys this difference.

$res = $str1 ^ $str2;

Doing this will clip $res to the shortest of both strings and so the number of loop cycles is not solely dependent on the given string length.

$ret = strlen($str1) ^ strlen($str2); //not the same length, then fail ($ret != 0)

This is a good approach, because bit representations are always different when the numbers they represent are different (assuming all bits are used in the operation).

for($i = strlen($res) - 1; $i >= 0; $i--) $ret += ord($res[$i]);

This may lead to an integer overflow, e.g. a 4MB+ string comprising 255 characters on a 32-bit system.

Proposal

Consider the following function:

function time_strcmp($known_str, $given_str)
{
    if (strlen($known_str) == 0) {
        throw new InvalidArgumentException("This function cannot safely compare against an empty given string");
    }

    $res = strlen($given_str) ^ strlen($known_str);
    $given_len = strlen($given);
    $known_len = strlen($known);

    for ($i = 0; $i < $given_len; ++$i) {
        $res |= ord($known_str[$i % $known_len]) ^ ord($given_str[$i]);
    }

    return $res === 0;
}

The caveat is that the known string must not be empty, which is quite unlikely :)

Answer 3

It's a lovely little implementation: short and sweet. However, I see a core weakness.

There is a strong argument that constant time string comparisons need to be constant for the length of the given string — not the known string. That's because the given string is under an attackers control.

Argument names

It's important to differentiate which string you have control over, and which string an attacker has control over. I'd like to echo Jack's naming suggestion:

function time_strcmp($known_str, $given_str)

Protecting the length of known

Because your implementation picks the shortest length to compare it opens up the possibility of leaking the length of the known string. The attacker picks an arbitrarily long length for the given string, and simply reduces the length till timing normalizes: known length leaked. I'll defer to @Jack's rewrite as an example to solve this issue.

Now, depending on a given situation length leaks may not matter much (if for instance the attacker can glean what the given string's length should be — like of a session cookie of uniform size or some other fixed length public token) but it's a weakness in the current design.

The best implementation I've found — I am not the author only linking and copy/pasting for the sake of richness in comparison — makes the security details more explicit:

function timingSafeEquals($safe, $user) {
    // Prevent issues if string length is 0
    $safe .= chr(0);
    $user .= chr(0);

    $safeLen = strlen($safe);
    $userLen = strlen($user);

    // Set the result to the difference between the lengths
    $result = $safeLen - $userLen;

    // Note that we ALWAYS iterate over the user-supplied length
    // This is to prevent leaking length information
    for ($i = 0; $i < $userLen; $i++) {
        // Using % here is a trick to prevent notices
        // It's safe, since if the lengths are different
        // $result is already non-0
        $result |= (ord($safe[$i % $safeLen]) ^ ord($user[$i]));
    }

    // They are only identical strings if $result is exactly 0...
    return $result === 0;
}