[cryptography] Digest comparison algorithm

Alfonso De Gregorio adg at crypto.lo.gy
Fri Dec 2 04:23:54 EST 2011


On Fri, Dec 2, 2011 at 2:46 AM, Jon Callas <jon at callas.org> wrote:
> 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!
>
>        Jon


I never thought I had suggested a logic to prevent the leak. Far from
it, my short email was never intended to convey one. Rather, it was
simply aimed at pointing out the importance to avoid branch conditions
that depend on secret data.

Anyway, implementing a constant-time comparison in high-level
languages can be tricky (though never as hard as crypto, I couldn't
agree more). When dealing with Java, here it is how I do: depending on
the encoding used, I normalize the input (while the reference value
was previously normalized), and I call constant-time comparison in C
glued with some JNI code.

As always, I very welcome improvements and alternative methods.

Cheers,

-- alfonso     blogs at http://Plaintext.crypto.lo.gy   tweets @secYOUre



More information about the cryptography mailing list