Merge remote-tracking branch 'public/3122_memcmp_squashed' into bug3122_memcmp_022

Conflicts throughout.  All resolved in favor of taking HEAD and
adding tor_mem* or fast_mem* ops as appropriate.

	src/common/Makefile.am
	src/or/circuitbuild.c
	src/or/directory.c
	src/or/dirserv.c
	src/or/dirvote.c
	src/or/networkstatus.c
	src/or/rendclient.c
	src/or/rendservice.c
	src/or/router.c
	src/or/routerlist.c
	src/or/routerparse.c
	src/or/test.c

11 files changed, 193 insertions, 22 deletions

diff --git a/src/common/Makefile.am b/src/common/Makefile.am
index b1e03cd710..2d009bd4fa 100644
--- a/src/common/Makefile.am
+++ b/src/common/Makefile.am
@@ -12,11 +12,11 @@ libor_extra_source=
 endif
 
 libor_a_SOURCES = address.c log.c util.c compat.c container.c mempool.c \
-	memarea.c util_codedigest.c $(libor_extra_source)
+	memarea.c di_ops.c util_codedigest.c $(libor_extra_source)
 libor_crypto_a_SOURCES = crypto.c aes.c tortls.c torgzip.c
 libor_event_a_SOURCES = compat_libevent.c
 
-noinst_HEADERS = address.h torlog.h crypto.h util.h compat.h aes.h torint.h tortls.h strlcpy.c strlcat.c torgzip.h container.h ht.h mempool.h memarea.h ciphers.inc compat_libevent.h tortls_states.h
+noinst_HEADERS = address.h torlog.h crypto.h util.h compat.h aes.h torint.h tortls.h strlcpy.c strlcat.c torgzip.h container.h ht.h mempool.h memarea.h ciphers.inc compat_libevent.h tortls_states.h di_ops.h
 
 common_sha1.i: $(libor_SOURCES) $(libor_crypto_a_SOURCES) $(noinst_HEADERS)
 	if test "@SHA1SUM@" != none; then \
diff --git a/src/common/address.c b/src/common/address.c
index aff517ca51..34e109fcf4 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 5797374c4b..ea7f9d7efc 100644
--- a/src/common/compat.c
+++ b/src/common/compat.c
@@ -413,6 +413,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 *
@@ -437,7 +439,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 7208d36803..5476c6008f 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;
 }
@@ -802,7 +802,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. */
@@ -886,7 +886,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 8a3a405273..b39d4ca07e 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 8d17a3daee..ff117e929f 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 0000000000..c1e292fe2f
--- /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 0000000000..4a212b0ca2
--- /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 e9079e0ba5..2937c67de2 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 38c0ad05e6..86f4141674 100644
--- a/src/common/util.c
+++ b/src/common/util.c
@@ -515,7 +515,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
@@ -557,17 +557,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
@@ -723,14 +723,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;
 }
@@ -739,7 +741,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 6b54856743..961b5875ad 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,