Timing attack - Is safe to check if strings have the same length?

Question

In Node, you can use crypto.timingSafeEqual() to check if two strings are equal in a timing-attack safe way. But, they must have the same length, so you have to do something like that:

return stringOne.length === stringTwo.length && crypto.timingSafeEqual(Buffer.from(stringOne), Buffer.from(stringTwo))

Is this approach safe? In my opinion, it's not, because it can leak the length of the string! Surprisingly, I discovered that hash_equals() of PHP works in a similar way:

// Source code from php-src/ext/hash/hash.c

if (Z_STRLEN_P(known_zval) != Z_STRLEN_P(user_zval)) {
        RETURN_FALSE;
}

known_str = Z_STRVAL_P(known_zval);
user_str = Z_STRVAL_P(user_zval);

/* This is security sensitive code. Do not optimize this for speed. */
for (j = 0; j < Z_STRLEN_P(known_zval); j++) {
    result |= known_str[j] ^ user_str[j];
}

Do you consider this approach safe?

score 5 · Accepted Answer · answered Jul 03 '19 at 02:10

You are correct this implementation of constant-time string comparison will leak information about the length of some string that is being compared against an attacker controlled string.

However, if this is checking strings for authentication purposes, you never should be comparing raw strings. You would first hash (preferably with a salted key-stretched hashing function like bcrypt or PBKDF2) the entered password with the salt taken from the database and compare against the hashed password from the database.

In such a scenario where a password login could potentially work, the lengths of the compared hashes will always be identical (regardless of what string the attacker enters). Now, there may be scenarios where the lengths aren't identical; e.g., maybe you used to use sha256crypt but decided to migrate user hashes to bcrypt. So you explicitly check whether the user-entered password works against either hash which have different lengths, and there's no vulnerability if different lengthed hashes fail quickly. (Obviously it makes more sense to use an identifier to track the hashing algorithm you used). Or you use client side code to hash first and then transmit the hash and the attacker tweaks the sent hash length. If they send an incorrect length, there's no problem to fail quickly (it's not like the correct hash length is a secret).

You do have to be careful about writing code like the following python code:

def bad_constant_time_str_compare(str1, str2):
   ret_val = 0
   for c1, c2 in zip(str1, str2):
       ret_val |= ord(c1) ^ ord(c2)
   return ret_val == 0

which seems like it should work, until you recognize that bad_constant_time_str_compare('hello', 'h') returns True because of how zip works (stopping at the length of the shortest string).

You could fix this with say:

def better_constant_time_str_compare(str1, str2):
   ret_val = 0
   for c1, c2 in zip(str1, str2):
       ret_val |= ord(c1) ^ ord(c2)
   return ret_val == 0 and len(str1) == len(str2)

but if you think about it, it is still vulnerable to timing attacks leaking the length of the string.

Finally, you should recognize that constant time string comparison in principle leaks information about the length of the two strings being compared -- the running time will be proportional to the number of comparisons run. You could try to mask that (e.g., add random wait time), but in principle any secure system will not be weakened in any practical way by knowing the length of the strings being compared.

Timing attack - Is safe to check if strings have the same length?

1 Answers1