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

[Jacob Appelbaum]

Hi Marsh,

Thanks for writing to or-dev, welcome to the list!

On 05/06/2011 04:13 PM, Marsh Ray wrote:
> 
> 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.

After some of our discussions and some thinking, I opened this bug:
https://trac.torproject.org/projects/tor/ticket/3122

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

Nate's post is great and anyone reading this email should read the above
url for context. I'd also suggest this one:
http://rdist.root.org/2010/01/07/timing-independent-array-comparison/

> 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 generally agree - I think it's best to use a constant time comparison
unless you're *certain* that you want something else.

> 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 think it's probably a good idea to write a new set of functions, say
safe_memcmp and safe_strcmp, that are properly implemented. We can
#define over memcmp but I fear that it's better to specifically
eradicate each one by hand and really think things over on a case by
case basis.

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

I think so too.

All the best,
Jake