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 14The 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