[cryptography] Digest comparison algorithm

Jon Callas jon at callas.org
Thu Dec 1 20:46:17 EST 2011

On Dec 1, 2011, at 3:53 PM, Alfonso De Gregorio wrote:

> If the attacker has direct control over the challenge/digest, the side
> channel may turn to be observable. The attacker could query adaptively
> the authentication server and exploit the timing information to
> recover the hashed secret - gaining access. If the hash is not salted,
> a secret preimage can be found with a TMTO attack.

Potentially yes, indeed. But the logic that you use to prevent that might also have timing issues.

If I were writing in C, I might do something slightly evil like just compare 16 bytes regardless, but that could give problems in a language like Java, which might take an exception if the challenge is short. There's the additional problem that unless you compare an algorithm ID, too, there's the chance that you'd get a cross-hash collision (one were the first 16 bytes of SHA256 matches the MD5), even. I didn't even address the question of why MD5 was being used for this without an HMAC, as I took that as a constraint.

It also occurred to me that there are architectures where comparison/subtraction isn't constant time (a negative result takes an extra micro-op) and if you're really anal, you should use an idiom like:

	failure |= x ^ y;

and compare to zero at the end. You could even do this with sizes larger than a byte, if you can somehow cast a byte array into something larger, and then just inline the whole thing.

So it's really a more involved question than it appears on first blush -- and that's why crypto is hard!


More information about the cryptography mailing list