Merge branch 'bug4900_siphash_v2'

23 files changed, 448 insertions, 85 deletions

diff --git a/LICENSE b/LICENSE
index 8a6fccaf4..4ebab1823 100644
--- a/LICENSE
+++ b/LICENSE
@@ -101,6 +101,29 @@ src/ext/tor_queue.h is licensed under the following license:
  * SUCH DAMAGE.
 
 ===============================================================================
+src/ext/csiphash.c is licensed under the following license:
+
+ Copyright (c) 2013  Marek Majkowski <marek@popcount.org>
+
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ THE SOFTWARE.
+
+===============================================================================
 src/config/geoip is licensed under the following license:
 
 OPEN DATA LICENSE (GeoLite Country and GeoLite City databases)
diff --git a/changes/feature4900 b/changes/feature4900
new file mode 100644
index 000000000..378ce12ae
--- /dev/null
+++ b/changes/feature4900
@@ -0,0 +1,12 @@
+  o Minor features:
+
+    - Avoid hash-flooding denial-of-service attacks by using the secure
+      SipHash-2-4 hash function for our hashtables.  Without this
+      feature, an attacker could degrade performance of a targeted
+      client or server by flooding their data structures with a large
+      number of data entries all calculated to be stored at the same
+      hash table position, thereby degrading hash table
+      performance. With this feature, hash table positions are derived
+      from a randomized cryptographic key using SipHash-2-4, and an
+      attacker cannot predict which entries will collide.
+      Closes ticket 4900.
diff --git a/src/common/address.c b/src/common/address.c
index b9f2d9315..69049fa0a 100644
--- a/src/common/address.c
+++ b/src/common/address.c
@@ -874,6 +874,32 @@ tor_addr_copy(tor_addr_t *dest, const tor_addr_t *src)
   memcpy(dest, src, sizeof(tor_addr_t));
 }
 
+/** Copy a tor_addr_t from <b>src</b> to <b>dest</b>, taking extra case to
+ * copy only the well-defined portions. Used for computing hashes of
+ * addresses.
+ */
+void
+tor_addr_copy_tight(tor_addr_t *dest, const tor_addr_t *src)
+{
+  tor_assert(src != dest);
+  tor_assert(src);
+  tor_assert(dest);
+  memset(dest, 0, sizeof(tor_addr_t));
+  dest->family = src->family;
+  switch (tor_addr_family(src))
+    {
+    case AF_INET:
+      dest->addr.in_addr.s_addr = src->addr.in_addr.s_addr;
+      break;
+    case AF_INET6:
+      memcpy(dest->addr.in6_addr.s6_addr, src->addr.in6_addr.s6_addr, 16);
+    case AF_UNSPEC:
+      break;
+    default:
+      tor_fragile_assert();
+    }
+}
+
 /** Given two addresses <b>addr1</b> and <b>addr2</b>, return 0 if the two
  * addresses are equivalent under the mask mbits, less than 0 if addr1
  * precedes addr2, and greater than 0 otherwise.
@@ -995,19 +1021,17 @@ tor_addr_compare_masked(const tor_addr_t *addr1, const tor_addr_t *addr2,
   }
 }
 
-/** Return a hash code based on the address addr */
-unsigned int
+/** Return a hash code based on the address addr. DOCDOC extra */
+uint64_t
 tor_addr_hash(const tor_addr_t *addr)
 {
   switch (tor_addr_family(addr)) {
   case AF_INET:
-    return tor_addr_to_ipv4h(addr);
+    return siphash24g(&addr->addr.in_addr.s_addr, 4);
   case AF_UNSPEC:
     return 0x4e4d5342;
-  case AF_INET6: {
-    const uint32_t *u = tor_addr_to_in6_addr32(addr);
-    return u[0] + u[1] + u[2] + u[3];
-    }
+  case AF_INET6:
+    return siphash24g(&addr->addr.in6_addr.s6_addr, 16);
   default:
     tor_fragile_assert();
     return 0;
diff --git a/src/common/address.h b/src/common/address.h
index 77e585534..d41c2f570 100644
--- a/src/common/address.h
+++ b/src/common/address.h
@@ -167,7 +167,7 @@ int tor_addr_compare_masked(const tor_addr_t *addr1, const tor_addr_t *addr2,
  * "exactly". */
 #define tor_addr_eq(a,b) (0==tor_addr_compare((a),(b),CMP_EXACT))
 
-unsigned int tor_addr_hash(const tor_addr_t *addr);
+uint64_t tor_addr_hash(const tor_addr_t *addr);
 int tor_addr_is_v4(const tor_addr_t *addr);
 int tor_addr_is_internal_(const tor_addr_t *ip, int for_listening,
                           const char *filename, int lineno);
@@ -192,6 +192,7 @@ const char * tor_addr_to_str(char *dest, const tor_addr_t *addr, size_t len,
                              int decorate);
 int tor_addr_parse(tor_addr_t *addr, const char *src);
 void tor_addr_copy(tor_addr_t *dest, const tor_addr_t *src);
+void tor_addr_copy_tight(tor_addr_t *dest, const tor_addr_t *src);
 void tor_addr_from_ipv4n(tor_addr_t *dest, uint32_t v4addr);
 /** Set <b>dest</b> to the IPv4 address encoded in <b>v4addr</b> in host
  * order. */
diff --git a/src/common/container.c b/src/common/container.c
index 476dc8291..f489430ca 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -1004,7 +1004,7 @@ strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
 static INLINE unsigned int
 strmap_entry_hash(const strmap_entry_t *a)
 {
-  return ht_string_hash(a->key);
+  return (unsigned) siphash24g(a->key, strlen(a->key));
 }
 
 /** Helper: compare digestmap_entry_t objects by key value. */
@@ -1018,13 +1018,7 @@ digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
 static INLINE unsigned int
 digestmap_entry_hash(const digestmap_entry_t *a)
 {
-#if SIZEOF_INT != 8
-  const uint32_t *p = (const uint32_t*)a->key;
-  return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
-#else
-  const uint64_t *p = (const uint64_t*)a->key;
-  return p[0] ^ p[1];
-#endif
+  return (unsigned) siphash24g(a->key, DIGEST_LEN);
 }
 
 HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
diff --git a/src/common/container.h b/src/common/container.h
index d6c80b808..93f0b7114 100644
--- a/src/common/container.h
+++ b/src/common/container.h
@@ -7,6 +7,7 @@
 #define TOR_CONTAINER_H
 
 #include "util.h"
+#include "siphash.h"
 
 /** A resizeable list of pointers, with associated helpful functionality.
  *
@@ -620,11 +621,11 @@ typedef struct {
 static INLINE void
 digestset_add(digestset_t *set, const char *digest)
 {
-  const uint32_t *p = (const uint32_t *)digest;
-  const uint32_t d1 = p[0] + (p[1]>>16);
-  const uint32_t d2 = p[1] + (p[2]>>16);
-  const uint32_t d3 = p[2] + (p[3]>>16);
-  const uint32_t d4 = p[3] + (p[0]>>16);
+  const uint64_t x = siphash24g(digest, 20);
+  const uint32_t d1 = (uint32_t) x;
+  const uint32_t d2 = (uint32_t)( (x>>16) + x);
+  const uint32_t d3 = (uint32_t)( (x>>32) + x);
+  const uint32_t d4 = (uint32_t)( (x>>48) + x);
   bitarray_set(set->ba, BIT(d1));
   bitarray_set(set->ba, BIT(d2));
   bitarray_set(set->ba, BIT(d3));
@@ -636,11 +637,11 @@ digestset_add(digestset_t *set, const char *digest)
 static INLINE int
 digestset_contains(const digestset_t *set, const char *digest)
 {
-  const uint32_t *p = (const uint32_t *)digest;
-  const uint32_t d1 = p[0] + (p[1]>>16);
-  const uint32_t d2 = p[1] + (p[2]>>16);
-  const uint32_t d3 = p[2] + (p[3]>>16);
-  const uint32_t d4 = p[3] + (p[0]>>16);
+  const uint64_t x = siphash24g(digest, 20);
+  const uint32_t d1 = (uint32_t) x;
+  const uint32_t d2 = (uint32_t)( (x>>16) + x);
+  const uint32_t d3 = (uint32_t)( (x>>32) + x);
+  const uint32_t d4 = (uint32_t)( (x>>48) + x);
   return bitarray_is_set(set->ba, BIT(d1)) &&
          bitarray_is_set(set->ba, BIT(d2)) &&
          bitarray_is_set(set->ba, BIT(d3)) &&
diff --git a/src/common/crypto.c b/src/common/crypto.c
index 9bdb1f41f..49dc55a3e 100644
--- a/src/common/crypto.c
+++ b/src/common/crypto.c
@@ -132,6 +132,9 @@ crypto_get_rsa_padding(int padding)
 }
 
 /** Boolean: has OpenSSL's crypto been initialized? */
+static int crypto_early_initialized_ = 0;
+
+/** Boolean: has OpenSSL's crypto been initialized? */
 static int crypto_global_initialized_ = 0;
 
 /** Log all pending crypto errors at level <b>severity</b>.  Use
@@ -242,15 +245,46 @@ crypto_openssl_get_header_version_str(void)
   return crypto_openssl_header_version_str;
 }
 
+/** Make sure that openssl is using its default PRNG. Return 1 if we had to
+ * adjust it; 0 otherwise. */
+static int
+crypto_force_rand_ssleay(void)
+{
+  if (RAND_get_rand_method() != RAND_SSLeay()) {
+    log_notice(LD_CRYPTO, "It appears that one of our engines has provided "
+               "a replacement the OpenSSL RNG. Resetting it to the default "
+               "implementation.");
+    RAND_set_rand_method(RAND_SSLeay());
+    return 1;
+  }
+  return 0;
+}
+
+/** Set up the siphash key if we haven't already done so. */
+int
+crypto_init_siphash_key(void)
+{
+  static int have_seeded_siphash = 0;
+  struct sipkey key;
+  if (have_seeded_siphash)
+    return 0;
+
+  if (crypto_rand((char*) &key, sizeof(key)) < 0)
+    return -1;
+  siphash_set_global_key(&key);
+  have_seeded_siphash = 1;
+  return 0;
+}
+
 /** Initialize the crypto library.  Return 0 on success, -1 on failure.
  */
 int
-crypto_global_init(int useAccel, const char *accelName, const char *accelDir)
+crypto_early_init(void)
 {
-  if (!crypto_global_initialized_) {
+  if (!crypto_early_initialized_) {
     ERR_load_crypto_strings();
     OpenSSL_add_all_algorithms();
-    crypto_global_initialized_ = 1;
+
     setup_openssl_threading();
 
     if (SSLeay() == OPENSSL_VERSION_NUMBER &&
@@ -272,6 +306,26 @@ crypto_global_init(int useAccel, const char *accelName, const char *accelDir)
                  crypto_openssl_get_version_str());
     }
 
+    crypto_force_rand_ssleay();
+
+    if (crypto_seed_rng(1) < 0)
+      return -1;
+    if (crypto_init_siphash_key() < 0)
+      return -1;
+  }
+  return 0;
+}
+
+/** Initialize the crypto library.  Return 0 on success, -1 on failure.
+ */
+int
+crypto_global_init(int useAccel, const char *accelName, const char *accelDir)
+{
+  if (!crypto_global_initialized_) {
+    crypto_early_init();
+
+    crypto_global_initialized_ = 1;
+
     if (useAccel > 0) {
 #ifdef DISABLE_ENGINES
       (void)accelName;
@@ -335,17 +389,13 @@ crypto_global_init(int useAccel, const char *accelName, const char *accelDir)
       log_info(LD_CRYPTO, "NOT using OpenSSL engine support.");
     }
 
-    if (RAND_get_rand_method() != RAND_SSLeay()) {
-      log_notice(LD_CRYPTO, "It appears that one of our engines has provided "
-                 "a replacement the OpenSSL RNG. Resetting it to the default "
-                 "implementation.");
-      RAND_set_rand_method(RAND_SSLeay());
+    if (crypto_force_rand_ssleay()) {
+      if (crypto_seed_rng(1) < 0)
+        return -1;
     }
 
     evaluate_evp_for_aes(-1);
     evaluate_ctr_for_aes();
-
-    return crypto_seed_rng(1);
   }
   return 0;
 }
diff --git a/src/common/crypto.h b/src/common/crypto.h
index 6ce3697c9..3666d5f9a 100644
--- a/src/common/crypto.h
+++ b/src/common/crypto.h
@@ -110,6 +110,7 @@ typedef struct crypto_dh_t crypto_dh_t;
 /* global state */
 const char * crypto_openssl_get_version_str(void);
 const char * crypto_openssl_get_header_version_str(void);
+int crypto_early_init(void);
 int crypto_global_init(int hardwareAccel,
                        const char *accelName,
                        const char *accelPath);
@@ -256,6 +257,7 @@ uint64_t crypto_rand_uint64(uint64_t max);
 double crypto_rand_double(void);
 struct tor_weak_rng_t;
 void crypto_seed_weak_rng(struct tor_weak_rng_t *rng);
+int crypto_init_siphash_key(void);
 
 char *crypto_random_hostname(int min_rand_len, int max_rand_len,
                              const char *prefix, const char *suffix);
diff --git a/src/common/include.am b/src/common/include.am
index 814786b77..d0ea40ea6 100644
--- a/src/common/include.am
+++ b/src/common/include.am
@@ -61,6 +61,7 @@ LIBOR_A_SOURCES = \
   src/common/util.c					\
   src/common/util_codedigest.c				\
   src/common/sandbox.c					\
+  src/ext/csiphash.c					\
   $(libor_extra_source)
 
 LIBOR_CRYPTO_A_SOURCES = \
diff --git a/src/ext/csiphash.c b/src/ext/csiphash.c
new file mode 100644
index 000000000..30be40b51
--- /dev/null
+++ b/src/ext/csiphash.c
@@ -0,0 +1,153 @@
+/* <MIT License>
+ Copyright (c) 2013  Marek Majkowski <marek@popcount.org>
+
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ THE SOFTWARE.
+ </MIT License>
+
+ Original location:
+    https://github.com/majek/csiphash/
+
+ Solution inspired by code from:
+    Samuel Neves (supercop/crypto_auth/siphash24/little)
+    djb (supercop/crypto_auth/siphash24/little2)
+    Jean-Philippe Aumasson (https://131002.net/siphash/siphash24.c)
+*/
+
+#include "torint.h"
+#include "siphash.h"
+/* for tor_assert */
+#include "util.h"
+/* for memcpy */
+#include <string.h>
+
+#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && \
+	__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+#  define _le64toh(x) ((uint64_t)(x))
+#elif defined(_WIN32)
+/* Windows is always little endian, unless you're on xbox360
+   http://msdn.microsoft.com/en-us/library/b0084kay(v=vs.80).aspx */
+#  define _le64toh(x) ((uint64_t)(x))
+#elif defined(__APPLE__)
+#  include <libkern/OSByteOrder.h>
+#  define _le64toh(x) OSSwapLittleToHostInt64(x)
+#else
+
+/* See: http://sourceforge.net/p/predef/wiki/Endianness/ */
+#  if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__)
+#    include <sys/endian.h>
+#  else
+#    include <endian.h>
+#  endif
+#  if defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
+	__BYTE_ORDER == __LITTLE_ENDIAN
+#    define _le64toh(x) ((uint64_t)(x))
+#  else
+#    define _le64toh(x) le64toh(x)
+#  endif
+
+#endif
+
+#define ROTATE(x, b) (uint64_t)( ((x) << (b)) | ( (x) >> (64 - (b))) )
+
+#define HALF_ROUND(a,b,c,d,s,t)			\
+	a += b; c += d;				\
+	b = ROTATE(b, s) ^ a;			\
+	d = ROTATE(d, t) ^ c;			\
+	a = ROTATE(a, 32);
+
+#define DOUBLE_ROUND(v0,v1,v2,v3)		\
+	HALF_ROUND(v0,v1,v2,v3,13,16);		\
+	HALF_ROUND(v2,v1,v0,v3,17,21);		\
+	HALF_ROUND(v0,v1,v2,v3,13,16);		\
+	HALF_ROUND(v2,v1,v0,v3,17,21);
+
+#if (defined(__i386) || defined(__i386__) || defined(_M_IX86) ||	\
+     defined(__x86_64) || defined(__x86_64__) ||			\
+     defined(_M_AMD64) || defined(_M_X64) || defined(__INTEL__))
+#   define UNALIGNED_OK 1
+#endif
+
+uint64_t siphash24(const void *src, unsigned long src_sz, const struct sipkey *key) {
+	uint64_t k0 = key->k0;
+	uint64_t k1 = key->k1;
+	uint64_t b = (uint64_t)src_sz << 56;
+	const uint64_t *in = (uint64_t*)src;
+
+        uint64_t t;
+        uint8_t *pt, *m;
+
+	uint64_t v0 = k0 ^ 0x736f6d6570736575ULL;
+	uint64_t v1 = k1 ^ 0x646f72616e646f6dULL;
+	uint64_t v2 = k0 ^ 0x6c7967656e657261ULL;
+	uint64_t v3 = k1 ^ 0x7465646279746573ULL;
+
+	while (src_sz >= 8) {
+#ifdef UNALIGNED_OK
+		uint64_t mi = _le64toh(*in);
+#else
+		uint64_t mi;
+		memcpy(&mi, in, 8);
+		mi = _le64toh(mi);
+#endif
+		in += 1; src_sz -= 8;
+		v3 ^= mi;
+		DOUBLE_ROUND(v0,v1,v2,v3);
+		v0 ^= mi;
+	}
+
+	t = 0; pt = (uint8_t*)&t; m = (uint8_t*)in;
+	switch (src_sz) {
+	case 7: pt[6] = m[6];
+	case 6: pt[5] = m[5];
+	case 5: pt[4] = m[4];
+#ifdef UNALIGNED_OK
+	case 4: *((uint32_t*)&pt[0]) = *((uint32_t*)&m[0]); break;
+#else
+	case 4: pt[3] = m[3];
+#endif
+	case 3: pt[2] = m[2];
+	case 2: pt[1] = m[1];
+	case 1: pt[0] = m[0];
+	}
+	b |= _le64toh(t);
+
+	v3 ^= b;
+	DOUBLE_ROUND(v0,v1,v2,v3);
+	v0 ^= b; v2 ^= 0xff;
+	DOUBLE_ROUND(v0,v1,v2,v3);
+	DOUBLE_ROUND(v0,v1,v2,v3);
+	return (v0 ^ v1) ^ (v2 ^ v3);
+}
+
+
+static int the_siphash_key_is_set = 0;
+static struct sipkey the_siphash_key;
+
+uint64_t siphash24g(const void *src, unsigned long src_sz) {
+	tor_assert(the_siphash_key_is_set);
+	return siphash24(src, src_sz, &the_siphash_key);
+}
+
+void siphash_set_global_key(const struct sipkey *key)
+{
+	tor_assert(! the_siphash_key_is_set);
+	the_siphash_key.k0 = key->k0;
+	the_siphash_key.k1 = key->k1;
+	the_siphash_key_is_set = 1;
+}
diff --git a/src/ext/ht.h b/src/ext/ht.h
index 62c458ad0..e76b4aa4d 100644
--- a/src/ext/ht.h
+++ b/src/ext/ht.h
@@ -86,6 +86,7 @@ ht_string_hash(const char *s)
 }
 #endif
 
+#if 0
 /** Basic string hash function, from Python's str.__hash__() */
 static INLINE unsigned
 ht_string_hash(const char *s)
@@ -100,6 +101,7 @@ ht_string_hash(const char *s)
   h ^= (unsigned)(cp-(const unsigned char*)s);
   return h;
 }
+#endif
 
 #ifndef HT_NO_CACHE_HASH_VALUES
 #define HT_SET_HASH_(elm, field, hashfn)        \
diff --git a/src/ext/include.am b/src/ext/include.am
index ea7e58e79..26e194e88 100644
--- a/src/ext/include.am
+++ b/src/ext/include.am
@@ -10,7 +10,8 @@ EXTHEADERS = \
   src/ext/strlcat.c	\
   src/ext/strlcpy.c	\
   src/ext/tinytest_macros.h \
-  src/ext/tor_queue.h
+  src/ext/tor_queue.h	\
+  src/ext/siphash.h
 
 noinst_HEADERS+= $(EXTHEADERS)
 
diff --git a/src/ext/siphash.h b/src/ext/siphash.h
new file mode 100644
index 000000000..d9b34b898
--- /dev/null
+++ b/src/ext/siphash.h
@@ -0,0 +1,13 @@
+#ifndef SIPHASH_H
+#define SIPHASH_H
+
+struct sipkey {
+  uint64_t k0;
+  uint64_t k1;
+};
+uint64_t siphash24(const void *src, unsigned long src_sz, const struct sipkey *key);
+
+void siphash_set_global_key(const struct sipkey *key);
+uint64_t siphash24g(const void *src, unsigned long src_sz);
+
+#endif
diff --git a/src/or/channel.c b/src/or/channel.c
index a345bab20..9f6887588 100644
--- a/src/or/channel.c
+++ b/src/or/channel.c
@@ -95,12 +95,7 @@ typedef struct channel_idmap_entry_s {
 static INLINE unsigned
 channel_idmap_hash(const channel_idmap_entry_t *ent)
 {
-  const unsigned *a = (const unsigned *)ent->digest;
-#if SIZEOF_INT == 4
-  return a[0] ^ a[1] ^ a[2] ^ a[3] ^ a[4];
-#elif SIZEOF_INT == 8
-  return a[0] ^ a[1];
-#endif
+  return (unsigned) siphash24g(ent->digest, DIGEST_LEN);
 }
 
 static INLINE int
diff --git a/src/or/dns.c b/src/or/dns.c
index a1fe0de1d..a88a46eb7 100644
--- a/src/or/dns.c
+++ b/src/or/dns.c
@@ -239,7 +239,7 @@ cached_resolves_eq(cached_resolve_t *a, cached_resolve_t *b)
 static INLINE unsigned int
 cached_resolve_hash(cached_resolve_t *a)
 {
-  return ht_string_hash(a->address);
+  return (unsigned) siphash24g((const uint8_t*)a->address, strlen(a->address));
 }
 
 HT_PROTOTYPE(cache_map, cached_resolve_t, node, cached_resolve_hash,
diff --git a/src/or/fp_pair.c b/src/or/fp_pair.c
index 4d8a835c8..55e4c89a4 100644
--- a/src/or/fp_pair.c
+++ b/src/or/fp_pair.c
@@ -32,17 +32,8 @@ fp_pair_map_entries_eq(const fp_pair_map_entry_t *a,
 static INLINE unsigned int
 fp_pair_map_entry_hash(const fp_pair_map_entry_t *a)
 {
-  const uint32_t *p;
-  unsigned int hash;
-
-  p = (const uint32_t *)(a->key.first);
-  /* Hashes are 20 bytes long, so 5 times uint32_t */
-  hash = p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
-  /* Now XOR in the second fingerprint */
-  p = (const uint32_t *)(a->key.second);
-  hash ^= p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
-
-  return hash;
+  tor_assert(sizeof(a->key) == DIGEST_LEN*2);
+  return (unsigned) siphash24g(&a->key, DIGEST_LEN*2);
 }
 
 /*
diff --git a/src/or/geoip.c b/src/or/geoip.c
index dc4730c81..6088f5d19 100644
--- a/src/or/geoip.c
+++ b/src/or/geoip.c
@@ -486,10 +486,12 @@ static HT_HEAD(clientmap, clientmap_entry_t) client_history =
 static INLINE unsigned
 clientmap_entry_hash(const clientmap_entry_t *a)
 {
-  unsigned h = tor_addr_hash(&a->addr);
+  unsigned h = (unsigned) tor_addr_hash(&a->addr);
+
   if (a->transport_name)
-    h += ht_string_hash(a->transport_name);
-  return ht_improve_hash(h);
+    h += (unsigned) siphash24g(a->transport_name, strlen(a->transport_name));
+
+  return h;
 }
 /** Hashtable helper: compare two clientmap_entry_t values for equality. */
 static INLINE int
diff --git a/src/or/main.c b/src/or/main.c
index 959c41b64..a191d1c61 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -2319,6 +2319,13 @@ tor_init(int argc, char *argv[])
   /* Have the log set up with our application name. */
   tor_snprintf(progname, sizeof(progname), "Tor %s", get_version());
   log_set_application_name(progname);
+
+  /* Set up the crypto nice and early */
+  if (crypto_early_init() < 0) {
+    log_err(LD_GENERAL, "Unable to initialize the crypto subsystem!");
+    return 1;
+  }
+
   /* Initialize the history structures. */
   rep_hist_init();
   /* Initialize the service cache. */
diff --git a/src/or/microdesc.c b/src/or/microdesc.c
index 11249910c..8052ca998 100644
--- a/src/or/microdesc.c
+++ b/src/or/microdesc.c
@@ -45,12 +45,7 @@ struct microdesc_cache_t {
 static INLINE unsigned int
 microdesc_hash_(microdesc_t *md)
 {
-  unsigned *d = (unsigned*)md->digest;
-#if SIZEOF_INT == 4
-  return d[0] ^ d[1] ^ d[2] ^ d[3] ^ d[4] ^ d[5] ^ d[6] ^ d[7];
-#else
-  return d[0] ^ d[1] ^ d[2] ^ d[3];
-#endif
+  return (unsigned) siphash24g(md->digest, sizeof(md->digest));
 }
 
 /** Helper: compares <b>a</b> and </b> for equality for hash-table purposes. */
diff --git a/src/or/nodelist.c b/src/or/nodelist.c
index 402fb2e96..03fa836d4 100644
--- a/src/or/nodelist.c
+++ b/src/or/nodelist.c
@@ -43,14 +43,7 @@ typedef struct nodelist_t {
 static INLINE unsigned int
 node_id_hash(const node_t *node)
 {
-#if SIZEOF_INT == 4
-  const uint32_t *p = (const uint32_t*)node->identity;
-  return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
-#elif SIZEOF_INT == 8
-  const uint64_t *p = (const uint32_t*)node->identity;
-  const uint32_t *p32 = (const uint32_t*)node->identity;
-  return p[0] ^ p[1] ^ p32[4];
-#endif
+  return (unsigned) siphash24g(node->identity, DIGEST_LEN);
 }
 
 static INLINE unsigned int
diff --git a/src/or/policies.c b/src/or/policies.c
index be4da5506..05377ec20 100644
--- a/src/or/policies.c
+++ b/src/or/policies.c
@@ -597,21 +597,25 @@ policy_eq(policy_map_ent_t *a, policy_map_ent_t *b)
 
 /** Return a hashcode for <b>ent</b> */
 static unsigned int
-policy_hash(policy_map_ent_t *ent)
+policy_hash(const policy_map_ent_t *ent)
 {
-  addr_policy_t *a = ent->policy;
-  unsigned int r;
-  if (a->is_private)
-    r = 0x1234abcd;
-  else
-    r = tor_addr_hash(&a->addr);
-  r += a->prt_min << 8;
-  r += a->prt_max << 16;
-  r += a->maskbits;
-  if (a->policy_type == ADDR_POLICY_REJECT)
-    r ^= 0xffffffff;
+  const addr_policy_t *a = ent->policy;
+  addr_policy_t aa;
+  memset(&aa, 0, sizeof(aa));
+
+  aa.prt_min = a->prt_min;
+  aa.prt_max = a->prt_max;
+  aa.maskbits = a->maskbits;
+  aa.policy_type = a->policy_type;
+  aa.is_private = a->is_private;
+
+  if (a->is_private) {
+    aa.is_private = 1;
+  } else {
+    tor_addr_copy_tight(&aa.addr, &a->addr);
+  }
 
-  return r;
+  return (unsigned) siphash24g(&aa, sizeof(aa));
 }
 
 HT_PROTOTYPE(policy_map, policy_map_ent_t, node, policy_hash,
diff --git a/src/test/bench.c b/src/test/bench.c
index ae311b53c..c9cc101b7 100644
--- a/src/test/bench.c
+++ b/src/test/bench.c
@@ -544,6 +544,7 @@ main(int argc, const char **argv)
   reset_perftime();
 
   crypto_seed_rng(1);
+  crypto_init_siphash_key();
   options = options_new();
   init_logging();
   options->command = CMD_RUN_UNITTESTS;
diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c
index 22adc6cc3..b1252a11d 100644
--- a/src/test/test_crypto.c
+++ b/src/test/test_crypto.c
@@ -9,6 +9,7 @@
 #include "test.h"
 #include "aes.h"
 #include "util.h"
+#include "siphash.h"
 #ifdef CURVE25519_ENABLED
 #include "crypto_curve25519.h"
 #endif
@@ -1111,6 +1112,102 @@ test_crypto_curve25519_persist(void *arg)
 
 #endif
 
+static void
+test_crypto_siphash(void *arg)
+{
+  /* From the reference implementation, taking
+        k = 00 01 02 ... 0f
+        and in = 00; 00 01; 00 01 02; ...
+  */
+  const uint8_t VECTORS[64][8] =
+    {
+      { 0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72, },
+      { 0xfd, 0x67, 0xdc, 0x93, 0xc5, 0x39, 0xf8, 0x74, },
+      { 0x5a, 0x4f, 0xa9, 0xd9, 0x09, 0x80, 0x6c, 0x0d, },
+      { 0x2d, 0x7e, 0xfb, 0xd7, 0x96, 0x66, 0x67, 0x85, },
+      { 0xb7, 0x87, 0x71, 0x27, 0xe0, 0x94, 0x27, 0xcf, },
+      { 0x8d, 0xa6, 0x99, 0xcd, 0x64, 0x55, 0x76, 0x18, },
+      { 0xce, 0xe3, 0xfe, 0x58, 0x6e, 0x46, 0xc9, 0xcb, },
+      { 0x37, 0xd1, 0x01, 0x8b, 0xf5, 0x00, 0x02, 0xab, },
+      { 0x62, 0x24, 0x93, 0x9a, 0x79, 0xf5, 0xf5, 0x93, },
+      { 0xb0, 0xe4, 0xa9, 0x0b, 0xdf, 0x82, 0x00, 0x9e, },
+      { 0xf3, 0xb9, 0xdd, 0x94, 0xc5, 0xbb, 0x5d, 0x7a, },
+      { 0xa7, 0xad, 0x6b, 0x22, 0x46, 0x2f, 0xb3, 0xf4, },
+      { 0xfb, 0xe5, 0x0e, 0x86, 0xbc, 0x8f, 0x1e, 0x75, },
+      { 0x90, 0x3d, 0x84, 0xc0, 0x27, 0x56, 0xea, 0x14, },
+      { 0xee, 0xf2, 0x7a, 0x8e, 0x90, 0xca, 0x23, 0xf7, },
+      { 0xe5, 0x45, 0xbe, 0x49, 0x61, 0xca, 0x29, 0xa1, },
+      { 0xdb, 0x9b, 0xc2, 0x57, 0x7f, 0xcc, 0x2a, 0x3f, },
+      { 0x94, 0x47, 0xbe, 0x2c, 0xf5, 0xe9, 0x9a, 0x69, },
+      { 0x9c, 0xd3, 0x8d, 0x96, 0xf0, 0xb3, 0xc1, 0x4b, },
+      { 0xbd, 0x61, 0x79, 0xa7, 0x1d, 0xc9, 0x6d, 0xbb, },
+      { 0x98, 0xee, 0xa2, 0x1a, 0xf2, 0x5c, 0xd6, 0xbe, },
+      { 0xc7, 0x67, 0x3b, 0x2e, 0xb0, 0xcb, 0xf2, 0xd0, },
+      { 0x88, 0x3e, 0xa3, 0xe3, 0x95, 0x67, 0x53, 0x93, },
+      { 0xc8, 0xce, 0x5c, 0xcd, 0x8c, 0x03, 0x0c, 0xa8, },
+      { 0x94, 0xaf, 0x49, 0xf6, 0xc6, 0x50, 0xad, 0xb8, },
+      { 0xea, 0xb8, 0x85, 0x8a, 0xde, 0x92, 0xe1, 0xbc, },
+      { 0xf3, 0x15, 0xbb, 0x5b, 0xb8, 0x35, 0xd8, 0x17, },
+      { 0xad, 0xcf, 0x6b, 0x07, 0x63, 0x61, 0x2e, 0x2f, },
+      { 0xa5, 0xc9, 0x1d, 0xa7, 0xac, 0xaa, 0x4d, 0xde, },
+      { 0x71, 0x65, 0x95, 0x87, 0x66, 0x50, 0xa2, 0xa6, },
+      { 0x28, 0xef, 0x49, 0x5c, 0x53, 0xa3, 0x87, 0xad, },
+      { 0x42, 0xc3, 0x41, 0xd8, 0xfa, 0x92, 0xd8, 0x32, },
+      { 0xce, 0x7c, 0xf2, 0x72, 0x2f, 0x51, 0x27, 0x71, },
+      { 0xe3, 0x78, 0x59, 0xf9, 0x46, 0x23, 0xf3, 0xa7, },
+      { 0x38, 0x12, 0x05, 0xbb, 0x1a, 0xb0, 0xe0, 0x12, },
+      { 0xae, 0x97, 0xa1, 0x0f, 0xd4, 0x34, 0xe0, 0x15, },
+      { 0xb4, 0xa3, 0x15, 0x08, 0xbe, 0xff, 0x4d, 0x31, },
+      { 0x81, 0x39, 0x62, 0x29, 0xf0, 0x90, 0x79, 0x02, },
+      { 0x4d, 0x0c, 0xf4, 0x9e, 0xe5, 0xd4, 0xdc, 0xca, },
+      { 0x5c, 0x73, 0x33, 0x6a, 0x76, 0xd8, 0xbf, 0x9a, },
+      { 0xd0, 0xa7, 0x04, 0x53, 0x6b, 0xa9, 0x3e, 0x0e, },
+      { 0x92, 0x59, 0x58, 0xfc, 0xd6, 0x42, 0x0c, 0xad, },
+      { 0xa9, 0x15, 0xc2, 0x9b, 0xc8, 0x06, 0x73, 0x18, },
+      { 0x95, 0x2b, 0x79, 0xf3, 0xbc, 0x0a, 0xa6, 0xd4, },
+      { 0xf2, 0x1d, 0xf2, 0xe4, 0x1d, 0x45, 0x35, 0xf9, },
+      { 0x87, 0x57, 0x75, 0x19, 0x04, 0x8f, 0x53, 0xa9, },
+      { 0x10, 0xa5, 0x6c, 0xf5, 0xdf, 0xcd, 0x9a, 0xdb, },
+      { 0xeb, 0x75, 0x09, 0x5c, 0xcd, 0x98, 0x6c, 0xd0, },
+      { 0x51, 0xa9, 0xcb, 0x9e, 0xcb, 0xa3, 0x12, 0xe6, },
+      { 0x96, 0xaf, 0xad, 0xfc, 0x2c, 0xe6, 0x66, 0xc7, },
+      { 0x72, 0xfe, 0x52, 0x97, 0x5a, 0x43, 0x64, 0xee, },
+      { 0x5a, 0x16, 0x45, 0xb2, 0x76, 0xd5, 0x92, 0xa1, },
+      { 0xb2, 0x74, 0xcb, 0x8e, 0xbf, 0x87, 0x87, 0x0a, },
+      { 0x6f, 0x9b, 0xb4, 0x20, 0x3d, 0xe7, 0xb3, 0x81, },
+      { 0xea, 0xec, 0xb2, 0xa3, 0x0b, 0x22, 0xa8, 0x7f, },
+      { 0x99, 0x24, 0xa4, 0x3c, 0xc1, 0x31, 0x57, 0x24, },
+      { 0xbd, 0x83, 0x8d, 0x3a, 0xaf, 0xbf, 0x8d, 0xb7, },
+      { 0x0b, 0x1a, 0x2a, 0x32, 0x65, 0xd5, 0x1a, 0xea, },
+      { 0x13, 0x50, 0x79, 0xa3, 0x23, 0x1c, 0xe6, 0x60, },
+      { 0x93, 0x2b, 0x28, 0x46, 0xe4, 0xd7, 0x06, 0x66, },
+      { 0xe1, 0x91, 0x5f, 0x5c, 0xb1, 0xec, 0xa4, 0x6c, },
+      { 0xf3, 0x25, 0x96, 0x5c, 0xa1, 0x6d, 0x62, 0x9f, },
+      { 0x57, 0x5f, 0xf2, 0x8e, 0x60, 0x38, 0x1b, 0xe5, },
+      { 0x72, 0x45, 0x06, 0xeb, 0x4c, 0x32, 0x8a, 0x95, }
+    };
+
+  const struct sipkey K = { U64_LITERAL(0x0706050403020100),
+                            U64_LITERAL(0x0f0e0d0c0b0a0908) };
+  uint8_t IN[64];
+  int i, j;
+
+  (void)arg;
+
+  for (i = 0; i < 64; ++i)
+    IN[i] = i;
+
+  for (i = 0; i < 64; ++i) {
+    uint64_t r = siphash24(IN, i, &K);
+    for (j = 0; j < 8; ++j) {
+      tt_int_op( (r >> (j*8)) & 0xff, ==, VECTORS[i][j]);
+    }
+  }
+
+ done:
+  ;
+}
+
 static void *
 pass_data_setup_fn(const struct testcase_t *testcase)
 {
@@ -1152,6 +1249,7 @@ struct testcase_t crypto_tests[] = {
   { "curve25519_encode", test_crypto_curve25519_encode, 0, NULL, NULL },
   { "curve25519_persist", test_crypto_curve25519_persist, 0, NULL, NULL },
 #endif
+  { "siphash", test_crypto_siphash, 0, NULL, NULL },
   END_OF_TESTCASES
 };