[cryptography] Digest comparison algorithm

Jon Callas jon at callas.org
Thu Dec 1 18:31:26 EST 2011

On Dec 1, 2011, at 2:37 PM, Jerrie Union wrote:

> I’m wondering, if it’s running as some authenticated server application, if 
> it should be considered as resistant to time attacks nowadays. I’m aware that’s
> not a good practice, but I’m not clear if I should consider it as exploitable over the
> network (on both intranet and internet scenarios). 
> I would like to run some tests, but I’m not sure if I should follow some specific
> approach. Anyone has done some research recently?

I agree with Ian. You have correctly observed that the check algorithm is not constant time. This is a flaw. But you're doing a hash, and consequently that flaw may not be observable. It is therefore a very small flaw. 

I might rewrite the routine differently than Ian did. Let me apologize in advance for being a C guy writing Java, but I'd do approximately this:

public boolean check(digest, secret) {
     int failure = 0;
     hash = md5(secret);                                                                             

     failure |= (digest.length != hash.length);   // Is the hash of the same length?

     for (i = 0; i < min(digest.length, secret.length); i++) {                                                       
            failure |= (digest[i] != hash[i]);	// Check each byte for non-match

     return failure == 0;   // return true if we didn't fail. Yeah, confusing.

I don't guarantee that this works, but it looks okay from here. The intent is that you always OR together a length check and each byte check, with a low-order 1 bit indicating a failure. Then you reverse polarity and convert to a boolean. I hope I didn't embarrass myself in this pseudocode.

You have to have a wart in one of two places. I chose to have a wart that if the sizes mismatch, you still do the byte checks. Alternatively, if you return early on a size mismatch, you leak a size mismatch, which is small potatoes in the grand scheme of things. My way of doing it leaks the size mismatch and its size if you can somehow force in a secret of variable size. I went back and forth on which is better and decided I don't care at the end.

I don't think there's anything wrong with what Ian did, but I stuck to having most of my work be an OR because I'm that paranoid.


More information about the cryptography mailing list