[cryptography] Digest comparison algorithm

ianG iang at iang.org
Fri Dec 2 17:20:12 EST 2011


On 2/12/11 10:48 AM, 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;
>>        }

I ignored the above length comparison, assuming the attacker knew it was 
md5...  From a software point of view, we'd return a packet error, not a 
password error.

>>        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.

OK, I'm getting it - my bad.  md5(secret) is the valuable part, not secret.

But...

>> 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).
>
> Nate Lawson has some great resources on his blog.
> http://rdist.root.org/2010/07/19/exploiting-remote-timing-attacks/
>
> "Further research in 2007 showed that differences as small as 20 
> microseconds over the Internet and 100 nanoseconds over the LAN could 
> be distinguished with about 1000 samples."

So, unlikely.  Or, iow, what machines take 20 microseconds to show a 
difference of 15 ops with potentially 2 adds or 2 xors per op?  Or, even 
100 nanoseconds?

> A lot depends on the specifics of course.

Yes, a lot missing...

> For example, can the attacker supply the "digest" directly? A lot of 
> message authentication schemes seem to involve that type of thing 
> (e.g., using HMAC instead of plain MD5).
>
> Or perhaps the attacker supplies the 'secret', as in a 
> password-validation routine. (Of course that's not the only problem in 
> this routine for doing password validation). The attacker could supply 
> various passwords. He knows the MD5s of the values he supplies. The 
> timing comparison tells him how many bytes of the hash he has correct.
>
> Although it would be difficult for him to do a full primary preimage 
> attack on MD5 itself needed to extract the full hash value via timing, 
> he probably would not have to. He just needs to work out the first few 
> bytes of the hash value to enable an offline dictionary attack. E.g. 
> Just by learning the first two bytes he can eliminate 65535/65536ths 
> of the possible passwords.

Right, this I did not see.  md5(secret) is potentially as valuable as 
secret itself because presumably secret never changes for each call, and 
thus the md5 is of no security in the comparison.  Which may be all that 
is necessary.

At this point, as Marsh & Alfonso point out, learning the first byte(s) 
allows for the possibility of offline dictionary attacks.

>> I would like to run some tests,

How much do you really care?  On this group, as you see, we'll assume 
the worst, and we'll impose our assumptions to make your worst 
nightmares a pleasant memory.  But our assumptions might not be relevant.

If the eventual target isn't worth anything and you want to take 
ordinary precautions, I'd suggest:   use Jon's XOR construction (what I 
wanted to write but my excuse is timing attacks by a mad bus driver).  
And move on...

If there is any more time, spend it trying to get rid of the 
hash-over-one-secret thing.

I'm assuming you don't care, coz of md5(secret).  If you do care more, 
the answer is probably to use a better construct, HMAC or 
challenge/response of some form.  E.g., better algorithm and leave the 
side channel stuff until later.


iang




More information about the cryptography mailing list