hs: Add solve and verify PoW functions

Signed-off-by: David Goulet <dgoulet@torproject.org>

7 files changed, 307 insertions, 11 deletions

diff --git a/configure.ac b/configure.ac
index c0b531c81d..babc65fa8f 100644
--- a/configure.ac
+++ b/configure.ac
@@ -403,6 +403,9 @@ AC_DEFUN([ADD_MODULE], [
 m4_foreach_w([module], MODULES, [ADD_MODULE([module])])
 AC_SUBST(TOR_MODULES_ALL_ENABLED)
 
+dnl Blake2 check for Equi-X support.
+PKG_CHECK_MODULES([LIBB2], [libb2])
+
 dnl check for the correct "ar" when cross-compiling.
 dnl   (AM_PROG_AR was new in automake 1.11.2, which we do not yet require,
 dnl    so kludge up a replacement for the case where it isn't there yet.)
diff --git a/src/app/include.am b/src/app/include.am
index 5494d904a3..33365bfcac 100644
--- a/src/app/include.am
+++ b/src/app/include.am
@@ -20,7 +20,8 @@ src_app_tor_LDADD = libtor.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ $(TOR_LIBS_CRYPTLIB) \
 	@TOR_LIB_WS32@ @TOR_LIB_IPHLPAPI@ @TOR_LIB_SHLWAPI@ @TOR_LIB_GDI@ @TOR_LIB_USERENV@ \
 	@CURVE25519_LIBS@ @TOR_SYSTEMD_LIBS@ \
-	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@
+	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@ \
+	@LIBB2_LIBS@
 
 if COVERAGE_ENABLED
 src_app_tor_cov_SOURCES = $(src_app_tor_SOURCES)
@@ -32,5 +33,6 @@ src_app_tor_cov_LDADD = src/test/libtor-testing.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ $(TOR_LIBS_CRYPTLIB) \
 	@TOR_LIB_WS32@ @TOR_LIB_IPHLPAPI@ @TOR_LIB_SHLWAPI@ @TOR_LIB_GDI@ \
 	@CURVE25519_LIBS@ @TOR_SYSTEMD_LIBS@ \
-	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@
+	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@ \
+	@LIBB2_LIBS@
 endif
diff --git a/src/feature/hs/hs_pow.c b/src/feature/hs/hs_pow.c
new file mode 100644
index 0000000000..2b36da93db
--- /dev/null
+++ b/src/feature/hs/hs_pow.c
@@ -0,0 +1,280 @@
+/* Copyright (c) 2017-2020, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file hs_pow.c
+ * \brief Contains code to handle proof-of-work computations
+ * when a hidden service is defending against DoS attacks.
+ **/
+
+typedef unsigned __int128 uint128_t;
+
+#include <blake2.h>
+#include <stdio.h>
+
+#include "ext/ht.h"
+#include "feature/hs/hs_descriptor.h"
+#include "feature/hs/hs_pow.h"
+#include "lib/crypt_ops/crypto_rand.h"
+
+/** Replay cache set up */
+/** Cache entry for (nonce, seed) replay protection. */
+typedef struct nonce_cache_entry_t {
+  HT_ENTRY(nonce_cache_entry_t) node;
+  uint128_t nonce;
+  uint32_t seed_head;
+} nonce_cache_entry_t;
+
+/** Return true if the two (nonce, seed) replay cache entries are the same */
+static inline int
+nonce_cache_entries_eq_(const struct nonce_cache_entry_t *entry1,
+                        const struct nonce_cache_entry_t *entry2)
+{
+  return entry1->nonce == entry2->nonce &&
+         entry1->seed_head == entry2->seed_head;
+}
+
+/** Hash function to hash the (nonce, seed) tuple entry. */
+static inline unsigned
+nonce_cache_entry_hash_(const struct nonce_cache_entry_t *ent)
+{
+  return (unsigned)siphash24g(&ent->nonce, HS_POW_NONCE_LEN) + ent->seed_head;
+}
+
+static HT_HEAD(nonce_cache_table_ht, nonce_cache_entry_t)
+  nonce_cache_table = HT_INITIALIZER();
+
+HT_PROTOTYPE(nonce_cache_table_ht, nonce_cache_entry_t, node,
+             nonce_cache_entry_hash_, nonce_cache_entries_eq_);
+
+HT_GENERATE2(nonce_cache_table_ht, nonce_cache_entry_t, node,
+             nonce_cache_entry_hash_, nonce_cache_entries_eq_, 0.6,
+             tor_reallocarray_, tor_free_);
+
+/** We use this to check if an entry in the replay cache is for a particular
+ * seed head, so we know to remove it once the seed is no longer in use. */
+static int
+nonce_cache_entry_has_seed(nonce_cache_entry_t *ent, void *data)
+{
+  /* Returning nonzero makes HT_FOREACH_FN remove the element from the HT */
+  return ent->seed_head == *(uint32_t *)data;
+}
+
+/** Helper: Increment a given nonce and set it in the challenge at the right
+ * offset. Use by the solve function. */
+static inline void
+increment_and_set_nonce(uint128_t *nonce, uint8_t *challenge)
+{
+  (*nonce)++;
+  memcpy(challenge + HS_POW_SEED_LEN, nonce, HS_POW_NONCE_LEN);
+}
+
+/* Helper: Build EquiX challenge (C || N || INT_32(E)) and return a newly
+ * allocated buffer containing it. */
+static uint8_t *
+build_equix_challenge(const uint8_t *seed, const uint128_t nonce,
+                      const uint32_t effort)
+{
+  /* Build EquiX challenge (C || N || INT_32(E)). */
+  size_t offset = 0;
+  uint8_t *challenge = tor_malloc_zero(HS_POW_CHALLENGE_LEN);
+
+  memcpy(challenge, seed, HS_POW_SEED_LEN);
+  offset += HS_POW_SEED_LEN;
+  memcpy(challenge + offset, &nonce, HS_POW_NONCE_LEN);
+  offset += HS_POW_NONCE_LEN;
+  set_uint32(challenge + offset, tor_htonl(effort));
+  offset += HS_POW_EFFORT_LEN;
+  tor_assert(HS_POW_CHALLENGE_LEN == offset);
+
+  return challenge;
+}
+
+/** Helper: Return true iff the given challenge and solution for the given
+ * effort do validate as in: R * E <= UINT32_MAX. */
+static bool
+validate_equix_challenge(const uint8_t *challenge, const equix_solution *sol,
+                         const uint32_t effort)
+{
+  /* Fail if R * E > UINT32_MAX. */
+  uint8_t hash_result[HS_POW_HASH_LEN];
+  blake2b_state b2_state;
+
+  if (BUG(blake2b_init(&b2_state, HS_POW_HASH_LEN) < 0)) {
+    return false;
+  }
+
+  /* Construct: blake2b(C || N || E || S) */
+  blake2b_update(&b2_state, challenge, HS_POW_CHALLENGE_LEN);
+  blake2b_update(&b2_state, (const uint8_t *) sol, HS_POW_EQX_SOL_LEN);
+  blake2b_final(&b2_state, hash_result, HS_POW_HASH_LEN);
+
+  /* Scale to 64 bit so we can avoid 32 bit overflow. */
+  uint64_t RE = tor_htonl(get_uint32(hash_result)) * (uint64_t) effort;
+
+  return RE <= UINT32_MAX;
+}
+
+/** Solve the EquiX/blake2b PoW scheme using the parameters in pow_params, and
+ * store the solution in pow_solution_out. Returns 0 on success and -1
+ * otherwise. Called by a client. */
+int
+hs_pow_solve(const hs_pow_desc_params_t *pow_params,
+             hs_pow_solution_t *pow_solution_out)
+{
+  int ret = -1;
+  uint128_t nonce;
+  uint8_t *challenge = NULL;
+  equix_ctx *ctx = NULL;
+
+  tor_assert(pow_params);
+  tor_assert(pow_solution_out);
+
+  /* Select E (just using suggested for now) */
+  uint32_t effort = pow_params->suggested_effort;
+
+  /* Generate a random nonce N. */
+  crypto_rand((char *)&nonce, sizeof(uint128_t));
+
+  /* Build EquiX challenge (C || N || INT_32(E)). */
+  challenge = build_equix_challenge(pow_params->seed, nonce, effort);
+
+  ctx = equix_alloc(EQUIX_CTX_SOLVE);
+  equix_solution solution[EQUIX_MAX_SOLS];
+
+  /* We'll do a maximum of the nonce size iterations here which is the maximum
+   * number of nonce we can try in an attempt to find a valid solution. */
+  log_debug(LD_REND, "Solving proof of work");
+  for (uint64_t i = 0; i < UINT64_MAX; i++) {
+    /* Calculate S = equix_solve(C || N || E) */
+    if (!equix_solve(ctx, challenge, HS_POW_CHALLENGE_LEN, solution)) {
+      ret = -1;
+      goto end;
+    }
+    const equix_solution *sol = &solution[0];
+
+    equix_result result = equix_verify(ctx, challenge,
+                                       HS_POW_CHALLENGE_LEN, sol);
+    if (result != EQUIX_OK) {
+      /* Go again with a new nonce. */
+      increment_and_set_nonce(&nonce, challenge);
+      continue;
+    }
+
+    /* Validate the challenge against the solution. */
+    if (validate_equix_challenge(challenge, sol, effort)) {
+      /* Store the nonce N. */
+      pow_solution_out->nonce = nonce;
+      /* Store the effort E. */
+      pow_solution_out->effort = effort;
+      /* We only store the first 4 bytes of the seed C. */
+      pow_solution_out->seed_head = get_uint32(pow_params->seed);
+      /* Store the solution S */
+      memcpy(&pow_solution_out->equix_solution, sol,
+             sizeof(pow_solution_out->equix_solution));
+
+      /* Indicate success and we are done. */
+      ret = 0;
+      break;
+    }
+
+    /* Did not pass the R * E <= UINT32_MAX check. Increment the nonce and
+     * try again. */
+    increment_and_set_nonce(&nonce, challenge);
+  }
+
+ end:
+  tor_free(challenge);
+  equix_free(ctx);
+  return ret;
+}
+
+/** Verify the solution in pow_solution using the service's current PoW
+ * parameters found in pow_state. Returns 0 on success and -1 otherwise. Called
+ * by the service. */
+int
+hs_pow_verify(const hs_pow_service_state_t *pow_state,
+              const hs_pow_solution_t *pow_solution)
+{
+  int ret = -1;
+  uint8_t *challenge = NULL;
+  nonce_cache_entry_t search, *entry = NULL;
+  equix_ctx *ctx = NULL;
+  const uint8_t *seed = NULL;
+
+  tor_assert(pow_state);
+  tor_assert(pow_solution);
+
+  /* Notice, but don't fail, if E = POW_EFFORT is lower than the minimum
+   * effort. We will take whatever valid cells arrive, put them into the
+   * pqueue, and get to whichever ones we get to. */
+  if (pow_solution->effort < pow_state->min_effort) {
+    log_info(LD_REND, "Effort %d used in solution is less than the minimum "
+                      "effort %d required by the service. That's ok.",
+                       pow_solution->effort, pow_state->min_effort);
+  }
+
+  /* Find a valid seed C that starts with the seed head. Fail if no such seed
+   * exists. */
+  if (get_uint32(pow_state->seed_current) == pow_solution->seed_head) {
+    seed = pow_state->seed_current;
+  } else if (get_uint32(pow_state->seed_previous) == pow_solution->seed_head) {
+    seed = pow_state->seed_previous;
+  } else {
+    log_err(LD_REND, "Seed head didn't match either seed.");
+    goto done;
+  }
+
+  /* Fail if N = POW_NONCE is present in the replay cache. */
+  search.nonce = pow_solution->nonce;
+  search.seed_head = pow_solution->seed_head;
+  entry = HT_FIND(nonce_cache_table_ht, &nonce_cache_table, &search);
+  if (entry) {
+    log_warn(LD_REND, "Found (nonce, seed) tuple in the replay cache.");
+    goto done;
+  }
+
+  /* Build the challenge with the param we have. */
+  challenge = build_equix_challenge(seed, pow_solution->nonce,
+                                    pow_solution->effort);
+
+  if (!validate_equix_challenge(challenge, &pow_solution->equix_solution,
+                                pow_solution->effort)) {
+    log_warn(LD_REND, "Equi-X solution and effort was too large.");
+    goto done;
+  }
+
+  /* Fail if equix_verify(C || N || E, S) != EQUIX_OK */
+  ctx = equix_alloc(EQUIX_CTX_SOLVE);
+
+  equix_result result = equix_verify(ctx, challenge, HS_POW_CHALLENGE_LEN,
+                                     &pow_solution->equix_solution);
+  if (result != EQUIX_OK) {
+    log_warn(LD_REND, "Verification of EquiX solution in PoW failed.");
+    goto done;
+  }
+
+  /* PoW verified successfully. */
+  ret = 0;
+
+  /* Add the (nonce, seed) tuple to the replay cache. */
+  entry = tor_malloc_zero(sizeof(nonce_cache_entry_t));
+  entry->nonce = pow_solution->nonce;
+  entry->seed_head = pow_solution->seed_head;
+  HT_INSERT(nonce_cache_table_ht, &nonce_cache_table, entry);
+
+ done:
+  tor_free(challenge);
+  equix_free(ctx);
+  return ret;
+}
+
+/** Remove entries from the (nonce, seed) replay cache which are for the seed
+ * beginning with seed_head. */
+void
+hs_pow_remove_seed_from_cache(uint32_t seed)
+{
+  /* If nonce_cache_entry_has_seed returns 1, the entry is removed. */
+  HT_FOREACH_FN(nonce_cache_table_ht, &nonce_cache_table,
+                nonce_cache_entry_has_seed, &seed);
+}
diff --git a/src/feature/hs/hs_pow.h b/src/feature/hs/hs_pow.h
index 2ad5c2b04c..cd4f228565 100644
--- a/src/feature/hs/hs_pow.h
+++ b/src/feature/hs/hs_pow.h
@@ -110,4 +110,13 @@ typedef struct hs_pow_solution_t {
   equix_solution equix_solution;
 } hs_pow_solution_t;
 
+/* API */
+int hs_pow_solve(const hs_pow_desc_params_t *pow_params,
+                 hs_pow_solution_t *pow_solution_out);
+
+int hs_pow_verify(const hs_pow_service_state_t *pow_state,
+                  const hs_pow_solution_t *pow_solution);
+
+void hs_pow_remove_seed_from_cache(uint32_t seed);
+
 #endif /* !defined(TOR_HS_POW_H) */
diff --git a/src/feature/hs/include.am b/src/feature/hs/include.am
index efe85543cd..f4966e6c54 100644
--- a/src/feature/hs/include.am
+++ b/src/feature/hs/include.am
@@ -15,6 +15,7 @@ LIBTOR_APP_A_SOURCES += 				\
 	src/feature/hs/hs_intropoint.c		\
 	src/feature/hs/hs_metrics.c			\
 	src/feature/hs/hs_ob.c			\
+	src/feature/hs/hs_pow.c			\
 	src/feature/hs/hs_service.c		\
 	src/feature/hs/hs_stats.c		\
 	src/feature/hs/hs_sys.c		\
diff --git a/src/test/fuzz/include.am b/src/test/fuzz/include.am
index 9fece7d004..a97dca1489 100644
--- a/src/test/fuzz/include.am
+++ b/src/test/fuzz/include.am
@@ -14,7 +14,8 @@ FUZZING_LIBS = \
 	@TOR_SYSTEMD_LIBS@ \
 	@TOR_LZMA_LIBS@ \
 	@TOR_ZSTD_LIBS@ \
-	@TOR_TRACE_LIBS@
+	@TOR_TRACE_LIBS@ \
+	@LIBB2_LIBS@
 
 oss-fuzz-prereqs: \
     src/test/libtor-testing.a
diff --git a/src/test/include.am b/src/test/include.am
index deff450490..2ecea43333 100644
--- a/src/test/include.am
+++ b/src/test/include.am
@@ -301,7 +301,7 @@ src_test_test_switch_id_LDADD = \
 	$(TOR_UTIL_TESTING_LIBS) \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ \
 	@TOR_LIB_WS32@ @TOR_LIB_IPHLPAPI@ @TOR_LIB_SHLWAPI@ @TOR_LIB_USERENV@ \
-	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@
+	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@ @LIBB2_LIBS@
 src_test_test_LDFLAGS = @TOR_LDFLAGS_zlib@ $(TOR_LDFLAGS_CRYPTLIB) \
 	@TOR_LDFLAGS_libevent@
 src_test_test_LDADD = \
@@ -309,7 +309,7 @@ src_test_test_LDADD = \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \
 	$(TOR_LIBS_CRYPTLIB) @TOR_LIB_WS32@ @TOR_LIB_IPHLPAPI@ @TOR_LIB_SHLWAPI@ @TOR_LIB_GDI@ @TOR_LIB_USERENV@ \
 	@CURVE25519_LIBS@ \
-	@TOR_SYSTEMD_LIBS@ @TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@
+	@TOR_SYSTEMD_LIBS@ @TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@ @LIBB2_LIBS@
 
 src_test_test_slow_CPPFLAGS = $(src_test_test_CPPFLAGS)
 src_test_test_slow_CFLAGS = $(src_test_test_CFLAGS)
@@ -337,7 +337,7 @@ src_test_bench_LDADD = \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \
 	$(TOR_LIBS_CRYPTLIB) @TOR_LIB_WS32@ @TOR_LIB_IPHLPAPI@ @TOR_LIB_SHLWAPI@ @TOR_LIB_GDI@ @TOR_LIB_USERENV@ \
 	@CURVE25519_LIBS@ \
-	@TOR_SYSTEMD_LIBS@ @TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@
+	@TOR_SYSTEMD_LIBS@ @TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@ @LIBB2_LIBS@
 
 src_test_test_workqueue_LDFLAGS = @TOR_LDFLAGS_zlib@ $(TOR_LDFLAGS_CRYPTLIB) \
 	@TOR_LDFLAGS_libevent@
@@ -346,7 +346,7 @@ src_test_test_workqueue_LDADD = \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \
 	$(TOR_LIBS_CRYPTLIB) @TOR_LIB_WS32@ @TOR_LIB_IPHLPAPI@ @TOR_LIB_SHLWAPI@ @TOR_LIB_GDI@ @TOR_LIB_USERENV@ \
 	@CURVE25519_LIBS@ \
-	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@
+	@TOR_LZMA_LIBS@ @TOR_ZSTD_LIBS@ @TOR_TRACE_LIBS@ @LIBB2_LIBS@
 
 src_test_test_timers_CPPFLAGS = $(src_test_test_CPPFLAGS)
 src_test_test_timers_CFLAGS = $(src_test_test_CFLAGS)
@@ -357,7 +357,7 @@ src_test_test_timers_LDADD = \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \
 	$(TOR_LIBS_CRYPTLIB) @TOR_LIB_WS32@ @TOR_LIB_IPHLPAPI@ @TOR_LIB_SHLWAPI@ @TOR_LIB_GDI@ @TOR_LIB_USERENV@ \
 	@CURVE25519_LIBS@ \
-	@TOR_LZMA_LIBS@ @TOR_TRACE_LIBS@
+	@TOR_LZMA_LIBS@ @TOR_TRACE_LIBS@ @LIBB2_LIBS@
 src_test_test_timers_LDFLAGS = $(src_test_test_LDFLAGS)
 
 # ADD_C_FILE: INSERT HEADERS HERE.
@@ -391,7 +391,7 @@ src_test_test_ntor_cl_LDADD = \
 	libtor.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ \
 	$(TOR_LIBS_CRYPTLIB) @TOR_LIB_WS32@ @TOR_LIB_IPHLPAPI@ @TOR_LIB_SHLWAPI@ @TOR_LIB_GDI@ @TOR_LIB_USERENV@ \
-	@CURVE25519_LIBS@ @TOR_LZMA_LIBS@ @TOR_TRACE_LIBS@
+	@CURVE25519_LIBS@ @TOR_LZMA_LIBS@ @TOR_TRACE_LIBS@ @LIBB2_LIBS@
 src_test_test_ntor_cl_AM_CPPFLAGS =	       \
 	$(AM_CPPFLAGS)
 
@@ -401,7 +401,7 @@ src_test_test_hs_ntor_cl_LDADD = \
 	libtor.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ \
 	$(TOR_LIBS_CRYPTLIB) @TOR_LIB_WS32@ @TOR_LIB_IPHLPAPI@ @TOR_LIB_SHLWAPI@ @TOR_LIB_GDI@ \
-        @CURVE25519_LIBS@ @TOR_TRACE_LIBS@
+        @CURVE25519_LIBS@ @TOR_TRACE_LIBS@ @LIBB2_LIBS@
 src_test_test_hs_ntor_cl_AM_CPPFLAGS =	       \
 	$(AM_CPPFLAGS)
 
@@ -413,7 +413,7 @@ src_test_test_bt_cl_LDADD = \
 	$(TOR_UTIL_TESTING_LIBS) \
 	@TOR_LIB_MATH@ \
 	@TOR_LIB_WS32@ @TOR_LIB_IPHLPAPI@ @TOR_LIB_SHLWAPI@ @TOR_LIB_GDI@ @TOR_LIB_USERENV@ \
-        @TOR_TRACE_LIBS@
+        @TOR_TRACE_LIBS@ @LIBB2_LIBS@
 src_test_test_bt_cl_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS)
 src_test_test_bt_cl_CPPFLAGS= $(src_test_AM_CPPFLAGS) $(TEST_CPPFLAGS)
 endif