Thursday, February 5, 2015

Constant-time String Comparison

I mentioned hash_equals last post.  One of the things the documentation notes is that, should the string lengths not match, hash_equals will quickly return false and effectively reveal the length difference.

It seems to be a fairly common perception that this is a problem.  Take this StackOverflow answer:
This function still has a minor problem here:
if(strlen($a) !== strlen($b)) { 
    return false;
}
It lets you use timing attacks to figure out the correct length of the password, which lets you not bother guessing any shorter or longer passwords.
I believe an implementation that doesn’t fail fast on different lengths still leaks information, though.  Most of them (i.e. every one I’ve seen, including ones I’ve written before having this insight) compare all characters through the shorter of the two strings.  If an attacker can time comparisons and control the length of one string, then when the ‘constant time’ algorithm quits taking longer for longer strings, the attacker knows their supplied string is the longer one.

Therefore, I don’t believe “fail fast on different string lengths” is something to be concerned with.  If the threat model is concerned with a timing attack, then simply moving it around the function doesn’t actually form a defense.

No comments: