# 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? - How long is the hash? strcmp or === is going to have an extremely small difference between a matching string and an early bail. Have you timed to be sure that the string comparison could actually make a significant difference. (Unless of course you're comparing things many many times.) – Corbin Jul 10 '12 at 21:38 @Corbin The hash is 28 characters (160bits). I also thought the timing could not make a difference, especially over a net connection. But everything I read disagrees, so I decided it's better to be safe. – Ariel Jul 11 '12 at 1:34 I need to note that, with PHP, the major timing attack would be to provide a list of valid usernames by the time taken to process the info; therefore, even if your comparison function is right, you shouldn't do this: if (time_strcmp($_POST['username'],$retrievedUserName)) login ();. – Francisco Presencia Jan 9 '13 at 16:19 ## 3 Answers 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. - Thank you! Comments in order: I think L = max(strlen($s1), strlen($s2)) should be min, not max. The hash is always the same length, and the attacker controls the min length (and knows the normal length), so I'm not leaking information if it's quicker for a short string. I really like the OR idea and I will change it. (Although even without it maxint32 / 265 = 8MB which is more than enough for me.) Re the ponderings: The user sends me a hash (from a cookie I set earlier), not a password. i.e. the hash is the password, so via a timing attack they could guess the letters one at a time. – Ariel Jul 11 '12 at 1:31 @Ariel It was indeed supposed to be min. If the hash is a fixed length, I would kick out non-correct lengths immediately. The timing of that request would of course be way shorter than normal, but the attacker wouldn't gain any knowledge out of that other than what a correct hash length is (which they already know). – Corbin Jul 11 '12 at 1:35 @Ariel Are you sending the actual hashed password in the cookie? Hashed passwords are obviously safer to send around than plain text passwords, but they're still not safe. In fact, if anyone intercepted that cookie, they could permanently log in as the user. What you should do instead of using the actual password hash is create a list of temporary keys that are valid for authentication. For example, create a table of (user_id INT, auth_key char(128), valid_until TIMESTAMP). That way if one of those is leaked, the damage is relatively minimized. – Corbin Jul 11 '12 at 1:43 it's not the password hash, I wouldn't do that. It's short term authentication hash (like a random session key). The hash is made up of: the users hashed password, so if they change their password, (even back to what it was) the hash is invalided, their username, user_id, which is then used with a secret key in an hmac. For time limited hashes I also include a timestamp when calculating the hash, and an extra cookie with what the timestamp should be so I can verify. – Ariel Jul 11 '12 at 2:08 This way even if you had access to the database it still would not be enough to let you login - you also need access to the secret key. (And I'm working on making that key available only by executing code, not just by reading the source code. So you need not just read access, but also write access to get it.) – Ariel Jul 11 '12 at 2:09 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 :) - 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; }  - Yes, my code does assume that the attacker knows the correct string length. In my application it's always the same length. Note that this code will be MUCH slower because of all the mod divisions, so it should not be used unless needed. – Ariel Oct 30 '14 at 7:08 A problem: The idiv instruction (for the mod %) takes a variable amount of time on a CPU. So this is not actually a constant time comparison. I would solve this differently: I would string append as many spaces as the length of the$user string to the \$safe string. That avoids the constant modulus command - if they are not the same length it will anyway fail. I would add that to my code rather than this because the PHP string xor is faster than doing it individually in the loop like here. –  Ariel Oct 30 '14 at 7:20
Interesting. Is the time variability of modulus deterministic based on the expression? At any rate sounds like you've got a good handle on things! My suggestion is problem more pedantry than practical in your case. –  Mark Fox Oct 30 '14 at 8:13
Yes, deterministic. Some divisors are easier than others, specifically those that divide evenly. Which is a problem because it's is precisely those that are sensitive to the string length. –  Ariel Oct 30 '14 at 8:45