Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
1  
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
1  
@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
1  
@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
1  
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
1  
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 :)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.