Merge remote-tracking branch 'public/bug3122_memcmp_022' into bug3122_memcmp_023

Conflicts in various places, mainly node-related.  Resolved them in
favor of HEAD, with copying of tor_mem* operations from bug3122_memcmp_022.

	src/common/Makefile.am
	src/or/circuitlist.c
	src/or/connection_edge.c
	src/or/directory.c
	src/or/microdesc.c
	src/or/networkstatus.c
	src/or/router.c
	src/or/routerlist.c
	src/test/test_util.c

11 files changed, 194 insertions, 21 deletions

diff --git a/src/common/Makefile.am b/src/common/Makefile.am
index 20e3f5ae1..3a80eb80d 100644
--- a/src/common/Makefile.am
+++ b/src/common/Makefile.am
@@ -15,6 +15,7 @@ libor_a_SOURCES = \
   address.c					\
   compat.c					\
   container.c					\
+  di_ops.c					\
   log.c						\
   memarea.c					\
   mempool.c					\
@@ -38,6 +39,7 @@ noinst_HEADERS = 				\
   compat_libevent.h				\
   container.h					\
   crypto.h					\
+  di_ops.h					\
   ht.h						\
   memarea.h					\
   mempool.h					\
diff --git a/src/common/address.c b/src/common/address.c
index b61214915..65f429a4d 100644
--- a/src/common/address.c
+++ b/src/common/address.c
@@ -837,7 +837,7 @@ tor_addr_compare_masked(const tor_addr_t *addr1, const tor_addr_t *addr2,
         const uint8_t *a2 = tor_addr_to_in6_addr8(addr2);
         const int bytes = mbits >> 3;
         const int leftover_bits = mbits & 7;
-        if (bytes && (r = memcmp(a1, a2, bytes))) {
+        if (bytes && (r = tor_memcmp(a1, a2, bytes))) {
           return r;
         } else if (leftover_bits) {
           uint8_t b1 = a1[bytes] >> (8-leftover_bits);
diff --git a/src/common/compat.c b/src/common/compat.c
index 7a77f94dc..436d882f3 100644
--- a/src/common/compat.c
+++ b/src/common/compat.c
@@ -442,6 +442,8 @@ tor_vasprintf(char **strp, const char *fmt, va_list args)
  * <b>needle</b>, return a pointer to the first occurrence of the needle
  * within the haystack, or NULL if there is no such occurrence.
  *
+ * This function is <em>not</em> timing-safe.
+ *
  * Requires that nlen be greater than zero.
  */
 const void *
@@ -466,7 +468,7 @@ tor_memmem(const void *_haystack, size_t hlen,
   while ((p = memchr(p, first, end-p))) {
     if (p+nlen > end)
       return NULL;
-    if (!memcmp(p, needle, nlen))
+    if (fast_memeq(p, needle, nlen))
       return p;
     ++p;
   }
diff --git a/src/common/container.c b/src/common/container.c
index bc61226cb..eba5a2f70 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -216,7 +216,7 @@ smartlist_string_num_isin(const smartlist_t *sl, int num)
 }
 
 /** Return true iff <b>sl</b> has some element E such that
- * !memcmp(E,<b>element</b>,DIGEST_LEN)
+ * tor_memeq(E,<b>element</b>,DIGEST_LEN)
  */
 int
 smartlist_digest_isin(const smartlist_t *sl, const char *element)
@@ -224,7 +224,7 @@ smartlist_digest_isin(const smartlist_t *sl, const char *element)
   int i;
   if (!sl) return 0;
   for (i=0; i < sl->num_used; i++)
-    if (memcmp((const char*)sl->list[i],element,DIGEST_LEN)==0)
+    if (tor_memeq((const char*)sl->list[i],element,DIGEST_LEN))
       return 1;
   return 0;
 }
@@ -801,7 +801,7 @@ smartlist_pqueue_assert_ok(smartlist_t *sl,
 static int
 _compare_digests(const void **_a, const void **_b)
 {
-  return memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
+  return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
 }
 
 /** Sort the list of DIGEST_LEN-byte digests into ascending order. */
@@ -823,7 +823,7 @@ smartlist_uniq_digests(smartlist_t *sl)
 static int
 _compare_digests256(const void **_a, const void **_b)
 {
-  return memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN);
+  return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN);
 }
 
 /** Sort the list of DIGEST256_LEN-byte digests into ascending order. */
@@ -885,7 +885,7 @@ strmap_entry_hash(const strmap_entry_t *a)
 static INLINE int
 digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
 {
-  return !memcmp(a->key, b->key, DIGEST_LEN);
+  return tor_memeq(a->key, b->key, DIGEST_LEN);
 }
 
 /** Helper: return a hash value for a digest_map_t. */
diff --git a/src/common/container.h b/src/common/container.h
index 8a3a40527..b39d4ca07 100644
--- a/src/common/container.h
+++ b/src/common/container.h
@@ -259,7 +259,7 @@ char *smartlist_join_strings2(smartlist_t *sl, const char *join,
  * Example use:
  *  SMARTLIST_FOREACH_JOIN(routerstatus_list, routerstatus_t *, rs,
  *                     routerinfo_list, routerinfo_t *, ri,
- *                     memcmp(rs->identity_digest, ri->identity_digest, 20),
+ *                     tor_memcmp(rs->identity_digest, ri->identity_digest, 20),
  *                     log_info(LD_GENERAL,"No match for %s", ri->nickname)) {
  *    log_info(LD_GENERAL, "%s matches routerstatus %p", ri->nickname, rs);
  * } SMARTLIST_FOREACH_JOIN_END(rs, ri);
@@ -274,7 +274,7 @@ char *smartlist_join_strings2(smartlist_t *sl, const char *join,
  *    ri = smartlist_get(routerinfo_list, ri_sl_idx);
  *    while (rs_sl_idx < rs_sl_len) {
  *      rs = smartlist_get(routerstatus_list, rs_sl_idx);
- *      rs_ri_cmp = memcmp(rs->identity_digest, ri->identity_digest, 20);
+ *      rs_ri_cmp = tor_memcmp(rs->identity_digest, ri->identity_digest, 20);
  *      if (rs_ri_cmp > 0) {
  *        break;
  *      } else if (rs_ri_cmp == 0) {
diff --git a/src/common/crypto.c b/src/common/crypto.c
index 424fd09b6..3de6fdded 100644
--- a/src/common/crypto.c
+++ b/src/common/crypto.c
@@ -933,7 +933,7 @@ crypto_pk_public_checksig_digest(crypto_pk_env_t *env, const char *data,
     tor_free(buf);
     return -1;
   }
-  if (memcmp(buf, digest, DIGEST_LEN)) {
+  if (tor_memneq(buf, digest, DIGEST_LEN)) {
     log_warn(LD_CRYPTO, "Signature mismatched with digest.");
     tor_free(buf);
     return -1;
diff --git a/src/common/di_ops.c b/src/common/di_ops.c
new file mode 100644
index 000000000..c1e292fe2
--- /dev/null
+++ b/src/common/di_ops.c
@@ -0,0 +1,133 @@
+/* Copyright (c) 2011, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file di_ops.c
+ * \brief Functions for data-independent operations
+ **/
+
+#include "orconfig.h"
+#include "di_ops.h"
+
+/**
+ * Timing-safe version of memcmp.  As memcmp, compare the <b>sz</b> bytes
+ * at <b>a</b> with the <b>sz</b> bytes at <b>, and returns less than 0 if the
+ * bytes at <b>a</b> lexically precede those at <b>b</b>, 0 if the byte ranges
+ * are equal, and greater than zero if the bytes at <b>a</b> lexically follow
+ * those at <b>.
+ *
+ * This implementation differs from memcmp in that its timing behavior is not
+ * data-dependent: it should return in the same amount of time regardless of
+ * the contents of <b>a</b> and <b>b</b>.
+ */
+int
+tor_memcmp(const void *a, const void *b, size_t len)
+{
+  const uint8_t *x = a;
+  const uint8_t *y = b;
+  size_t i = len;
+  int retval = 0;
+
+  /* This loop goes from the end of the arrays to the start.  At the
+   * start of every iteration, before we decrement i, we have set
+   * "retval" equal to the result of memcmp(a+i,b+i,len-i).  During the
+   * loop, we update retval by leaving it unchanged if x[i]==y[i] and
+   * setting it to x[i]-y[i] if x[i]!= y[i].
+   *
+   * The following assumes we are on a system with two's-complement
+   * arithmetic.  We check for this at configure-time with the check
+   * that sets USING_TWOS_COMPLEMENT.  If we aren't two's complement, then
+   * torint.h will stop compilation with an error.
+   */
+  while (i--) {
+    int v1 = x[i];
+    int v2 = y[i];
+    int equal_p = v1 ^ v2;
+
+    /* The following sets bits 8 and above of equal_p to 'equal_p ==
+     * 0', and thus to v1 == v2.  (To see this, note that if v1 ==
+     * v2, then v1^v2 == equal_p == 0, so equal_p-1 == -1, which is the
+     * same as ~0 on a two's-complement machine.  Then note that if
+     * v1 != v2, then 0 < v1 ^ v2 < 256, so 0 <= equal_p - 1 < 255.)
+     */
+    --equal_p;
+
+    equal_p >>= 8;
+    /* Thanks to (sign-preserving) arithmetic shift, equal_p is now
+     * equal to -(v1 == v2), which is exactly what we need below.
+     * (Since we're assuming two's-complement arithmetic, -1 is the
+     * same as ~0 (all bits set).)
+     *
+     * (The result of an arithmetic shift on a negative value is
+     * actually implementation-defined in standard C.  So how do we
+     * get away with assuming it?  Easy.  We check.) */
+#if ((-60 >> 8) != -1)
+#error "According to cpp, right-shift doesn't perform sign-extension."
+#endif
+#ifndef RSHIFT_DOES_SIGN_EXTEND
+#error "According to configure, right-shift doesn't perform sign-extension."
+#endif
+
+    /* If v1 == v2, equal_p is ~0, so this will leave retval
+     * unchanged; otherwise, equal_p is 0, so this will zero it. */
+    retval &= equal_p;
+
+    /* If v1 == v2, then this adds 0, and leaves retval unchanged.
+     * Otherwise, we just zeroed retval, so this sets it to v1 - v2. */
+    retval += (v1 - v2);
+
+    /* There.  Now retval is equal to its previous value if v1 == v2, and
+     * equal to v1 - v2 if v1 != v2. */
+  }
+
+  return retval;
+}
+
+/**
+ * Timing-safe memory comparison.  Return true if the <b>sz</b> bytes at
+ * <b>a</b> are the same as the <b>sz</b> bytes at <b>, and 0 otherwise.
+ *
+ * This implementation differs from !memcmp(a,b,sz) in that its timing
+ * behavior is not data-dependent: it should return in the same amount of time
+ * regardless of the contents of <b>a</b> and <b>b</b>.  It differs from
+ * !tor_memcmp(a,b,sz) by being faster.
+ */
+int
+tor_memeq(const void *a, const void *b, size_t sz)
+{
+  /* Treat a and b as byte ranges. */
+  const uint8_t *ba = a, *bb = b;
+  uint32_t any_difference = 0;
+  while (sz--) {
+    /* Set byte_diff to all of those bits that are different in *ba and *bb,
+     * and advance both ba and bb. */
+    const uint8_t byte_diff = *ba++ ^ *bb++;
+
+    /* Set bits in any_difference if they are set in byte_diff. */
+    any_difference |= byte_diff;
+  }
+
+  /* Now any_difference is 0 if there are no bits different between
+   * a and b, and is nonzero if there are bits different between a
+   * and b.  Now for paranoia's sake, let's convert it to 0 or 1.
+   *
+   * (If we say "!any_difference", the compiler might get smart enough
+   * to optimize-out our data-independence stuff above.)
+   *
+   * To unpack:
+   *
+   * If any_difference == 0:
+   *            any_difference - 1 == ~0
+   *     (any_difference - 1) >> 8 == 0x00ffffff
+   *     1 & ((any_difference - 1) >> 8) == 1
+   *
+   * If any_difference != 0:
+   *            0 < any_difference < 256, so
+   *            0 < any_difference - 1 < 255
+   *            (any_difference - 1) >> 8 == 0
+   *            1 & ((any_difference - 1) >> 8) == 0
+   */
+
+  return 1 & ((any_difference - 1) >> 8);
+}
+
diff --git a/src/common/di_ops.h b/src/common/di_ops.h
new file mode 100644
index 000000000..4a212b0ca
--- /dev/null
+++ b/src/common/di_ops.h
@@ -0,0 +1,30 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2011, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file di_ops.h
+ * \brief Headers for di_ops.c
+ **/
+
+#ifndef TOR_DI_OPS_H
+#define TOR_DI_OPS_H
+
+#include "orconfig.h"
+#include "torint.h"
+
+int tor_memcmp(const void *a, const void *b, size_t sz);
+int tor_memeq(const void *a, const void *b, size_t sz);
+#define tor_memneq(a,b,sz) (!tor_memeq((a),(b),(sz)))
+
+/** Alias for the platform's memcmp() function.  This function is
+ * <em>not</em> data-independent: we define this alias so that we can
+ * mark cases where we are deliberately using a data-dependent memcmp()
+ * implementation.
+ */
+#define fast_memcmp(a,b,c) (memcmp((a),(b),(c)))
+#define fast_memeq(a,b,c)  (0==memcmp((a),(b),(c)))
+#define fast_memneq(a,b,c) (0!=memcmp((a),(b),(c)))
+
+#endif
diff --git a/src/common/torgzip.c b/src/common/torgzip.c
index e9079e0ba..2937c67de 100644
--- a/src/common/torgzip.c
+++ b/src/common/torgzip.c
@@ -378,7 +378,7 @@ tor_gzip_uncompress(char **out, size_t *out_len,
 compress_method_t
 detect_compression_method(const char *in, size_t in_len)
 {
-  if (in_len > 2 && !memcmp(in, "\x1f\x8b", 2)) {
+  if (in_len > 2 && fast_memeq(in, "\x1f\x8b", 2)) {
     return GZIP_METHOD;
   } else if (in_len > 2 && (in[0] & 0x0f) == 8 &&
              (ntohs(get_uint16(in)) % 31) == 0) {
diff --git a/src/common/util.c b/src/common/util.c
index e676530b2..d2140c3f3 100644
--- a/src/common/util.c
+++ b/src/common/util.c
@@ -516,7 +516,7 @@ strcmp_len(const char *s1, const char *s2, size_t s1_len)
     return -1;
   if (s1_len > s2_len)
     return 1;
-  return memcmp(s1, s2, s2_len);
+  return fast_memcmp(s1, s2, s2_len);
 }
 
 /** Compares the first strlen(s2) characters of s1 with s2.  Returns as for
@@ -558,17 +558,17 @@ strcasecmpend(const char *s1, const char *s2)
 /** Compare the value of the string <b>prefix</b> with the start of the
  * <b>memlen</b>-byte memory chunk at <b>mem</b>.  Return as for strcmp.
  *
- * [As memcmp(mem, prefix, strlen(prefix)) but returns -1 if memlen is less
- * than strlen(prefix).]
+ * [As fast_memcmp(mem, prefix, strlen(prefix)) but returns -1 if memlen is
+ * less than strlen(prefix).]
  */
 int
-memcmpstart(const void *mem, size_t memlen,
+fast_memcmpstart(const void *mem, size_t memlen,
                 const char *prefix)
 {
   size_t plen = strlen(prefix);
   if (memlen < plen)
     return -1;
-  return memcmp(mem, prefix, plen);
+  return fast_memcmp(mem, prefix, plen);
 }
 
 /** Return a pointer to the first char of s that is not whitespace and
@@ -724,14 +724,16 @@ tor_mem_is_zero(const char *mem, size_t len)
     0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0,
   };
   while (len >= sizeof(ZERO)) {
-    if (memcmp(mem, ZERO, sizeof(ZERO)))
+    /* It's safe to use fast_memcmp here, since the very worst thing an
+     * attacker could learn is how many initial bytes of a secret were zero */
+    if (fast_memcmp(mem, ZERO, sizeof(ZERO)))
       return 0;
     len -= sizeof(ZERO);
     mem += sizeof(ZERO);
   }
   /* Deal with leftover bytes. */
   if (len)
-    return ! memcmp(mem, ZERO, len);
+    return fast_memeq(mem, ZERO, len);
 
   return 1;
 }
@@ -740,7 +742,10 @@ tor_mem_is_zero(const char *mem, size_t len)
 int
 tor_digest_is_zero(const char *digest)
 {
-  return tor_mem_is_zero(digest, DIGEST_LEN);
+  static const uint8_t ZERO_DIGEST[] = {
+    0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0
+  };
+  return tor_memeq(digest, ZERO_DIGEST, DIGEST_LEN);
 }
 
 /** Return true iff the DIGEST256_LEN bytes in digest are all zero. */
diff --git a/src/common/util.h b/src/common/util.h
index 759f068b0..974b7d6fd 100644
--- a/src/common/util.h
+++ b/src/common/util.h
@@ -14,6 +14,7 @@
 #include "orconfig.h"
 #include "torint.h"
 #include "compat.h"
+#include "di_ops.h"
 #include <stdio.h>
 #include <stdlib.h>
 
@@ -181,8 +182,8 @@ int strcasecmpstart(const char *s1, const char *s2)
 int strcmpend(const char *s1, const char *s2) ATTR_PURE ATTR_NONNULL((1,2));
 int strcasecmpend(const char *s1, const char *s2)
   ATTR_PURE ATTR_NONNULL((1,2));
-int memcmpstart(const void *mem, size_t memlen,
-                const char *prefix) ATTR_PURE;
+int fast_memcmpstart(const void *mem, size_t memlen,
+                     const char *prefix) ATTR_PURE;
 
 void tor_strstrip(char *s, const char *strip) ATTR_NONNULL((1,2));
 long tor_parse_long(const char *s, int base, long min,