2010/11/05

Constant-time string comparison

I recently spotted @fabpot's tweet about his Symfony2 commit to prevent timing attacks. It's a pretty simple change. Basically it just makes every password string comparison run through every character no matter if the match fails on any character. I don't use bitwise operators much so it took a sec to spot how it works.

The comparison code is:

$result = 0;
for ($i = 0; $i < strlen($password1); $i++) {
    $result |= ord($password1[$i]) ^ ord($password2[$i]);
}
return 0 === $result;

The key components are:

ord() # translate a character into it's ASCII value (an 8 bit int)
^     # bitwise xor
|=    # short for left assign value bitwise or'd with new value

Just for clarity, bitwise xor evaluates to 1 for 1/0 or 0/1 or 0/0 but evaluates to 0 for 1/1. So when comparing two integers by xor'ing the bits a perfect match will evaluate to 0. Anything but an exact match will evaluate to 1.

01110000 xor
01110000
00000000  // match

01110011 xor
01110010
00000011  // nope

This means that if we xor each integer value of each character and or the produced values together it will evaluate to 0 when the two strings match. And this is always accomplished in string length time.

00000000  or
00000000  or
...
00000000
00000000  // match

As an aside, bitwise operators can do some neat stuff. This one is a solution that my Pascal instructor in college mentioned as a fast cheap way to swap screen buffers. In this example we're just swapping variable values without an intermediate.

$a = 'a';
$b = 'b';

$a ^= $b;
$b ^= $a;
$a ^= $b;

echo $a;  // b
echo $b;  // a

↑