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

Jacob Appelbaum jacob at appelbaum.net
Sat May 7 00:08:13 UTC 2011

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

> 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-$ grep -r memcmp . | grep -i digest | wc -l
>    137
>     ~/tor-$ 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:

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

More information about the tor-dev mailing list