Constant time string comparision in PHP to prevent timing attacks

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?

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.

StackExchange Code Review Q#13512, answer score: 5