[cryptography] Digest comparison algorithm

Jerrie Union jerrieunion at gmail.com
Thu Dec 1 19:15:34 EST 2011

On Dec 1, 2011, at 11:48 PM, Marsh Ray wrote:

> On 12/01/2011 04:37 PM, Jerrie Union wrote:
>> public boolean check(digest, secret) {
>>       hash = md5(secret);
>>       if (digest.length != hash.length)  {
>>         return false;
>>       }
>>       for (i = 0; i<  digest.length; i++) {
>>         if (digest[i] != hash[i]) {
>>               return false;
>>         }
>>       }
>> I’m wondering, if it’s running as some authenticated server application, if
>> it should be considered as resistant to time attacks nowadays.
> Not resistant. It's a timing oracle. Very dangerous.

How should the attacker mount the attack after hash[0] has been recovered?
I guess for a given digest D if the attacker guess the character at position 1 (D[1])
 by supplying the secret S there’s no easy way to recover D[2] because the md5
function will introduce noise in every single bit of the output as you change a single
bit in the input.

Maybe, by having a huge precomputed table the attacker can attempt to mount a timing attack 
in this way:
1. guess the first byte of the digest by exploiting the timing attack
2. for every digest in the rainbow table starting with the previously guessed byte:
3. try to send the plaintext and time the response to recover the second byte

The same process could be iterated until the fully string is recovered. 

Does it make sense?

More information about the cryptography mailing list