[tor-bugs] #3122 [Tor Client]: Write and use constant-time comparison functions

[Tor Bug Tracker & Wiki]

#3122: Write and use constant-time comparison functions
-------------------------+--------------------------------------------------
 Reporter:  rransom      |          Owner:  ioerror
     Type:  enhancement  |         Status:  new    
 Priority:  major        |      Milestone:         
Component:  Tor Client   |        Version:         
 Keywords:               |         Parent:         
   Points:               |   Actualpoints:         
-------------------------+--------------------------------------------------

Comment(by cypherpunks):

 [I sent this as an email to tor-dev 45 minutes or so ago but haven't seen
 it come through. I just signed up for the list so perhaps first posts are
 modded.]

 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

-- 
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/3122#comment:2>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online