[tor-dev] memcmp() & co. timing info disclosures?

[Marsh Ray]

Greetings all,

I happened to download the tor-0.2.2.25-alpha.tar.gz source yesterday 
and I noticed something. Apologies in advance if this has already been 
discussed and resolved, I did a cursory web search and didn't see anything.

There are a lot of places in the code where memcmp() is called on memory 
buffers that look like they might contain various hashes or digests:

    ~/tor-0.2.2.25-alpha$ grep -r memcmp . | grep -i digest | wc -l
    137

     ~/tor-0.2.2.25-alpha$ grep -r memcmp . | grep -i key | wc -l
     14

The built-in memcmp typically runs in time proportional to the common 
prefix of the two memory buffers being compared. In networked 
applications, this is often a significant source of timing information. 
Sometimes these are severe enough to result in disclosure of secret key 
material. A good resource for remote timing attacks is Nate Lawson's blog:

http://rdist.root.org/2010/07/19/exploiting-remote-timing-attacks/

Some cases look particularly concerning. For example, in the following 
code 'handshake_reply' appears to be supplied by the remote party and it 
is compared with something called "key material".

src/or/onion.c:331:
   if (memcmp(key_material, handshake_reply+DH_KEY_LEN, DIGEST_LEN)) {
     /* H(K) does *not* match. Something fishy. */
      log_warn(LD_PROTOCOL,"Digest DOES NOT MATCH on onion handshake. "
            "Bug or attack.");
     goto err;
   }

In the worst-case, the attacker could simply supply different values of 
handshake_reply, observe how long each takes to compare, and figure out 
the value of key_material statistically byte-by-byte.

Perhaps this key material is never used again, or there are other 
reasons this timing informaion is not useful. But in general, it's very 
difficult to determine whether or not such a timing info disclosure 
represents a vulnerability or how difficult it would be to exploit. 
Expert programmers seem to consistently underestimate the severtiy of 
these weaknesses, perhaps because they are so subtle. I've just started 
learning about Tor so it's not possible for me to review every instance.

I think the quickest and easiest solution would be to replace every 
usage of memcmp and str*cmp in the source with an alternate version that 
guarantees a constant time comparison.

I'd expect this could be done with negligible performance impact, 
especially for short comparisons like 20-byte hash values.

Regards,

- Marsh