[cryptography] Digest comparison algorithm

Marsh Ray marsh at extendedsubset.com
Thu Dec 1 18:48:47 EST 2011


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.

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

For example,
> http://rdist.root.org/2009/05/28/timing-attack-in-google-keyczar-library/

A lot depends on the specifics of course. 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.

> 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 pointed this out as a potential problem in Tor.
https://trac.torproject.org/projects/tor/ticket/3122
They promptly fixed it
https://gitweb.torproject.org/tor.git/history/HEAD:/src/common/di_ops.c
and did some timing statistical tests on their data-independent memcmp() 
implementation. NickM links to some timing test code in one of the 
comments (not in Java though).

The right approach is to find a well-tested timing-independent library 
for your platforms and use it. Inspect the generated code to be sure it 
does what you're expecting (compilers can be surprisingly clever at 
optimizing things you want to be slow).

- Marsh



More information about the cryptography mailing list