[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-commits] [tor] 05/77: hs: Add solve and verify PoW functions
This is an automated email from the git hooks/post-receive script.
dgoulet pushed a commit to branch main
in repository tor.
commit 51ce0bb6ef60781cfe20fcaa16b36d438f264db7
Author: David Goulet <dgoulet@xxxxxxxxxxxxxx>
AuthorDate: Mon Jun 27 16:03:54 2022 -0400
hs: Add solve and verify PoW functions
Signed-off-by: David Goulet <dgoulet@xxxxxxxxxxxxxx>
---
configure.ac | 3 +
src/app/include.am | 6 +-
src/feature/hs/hs_pow.c | 280 ++++++++++++++++++++++++++++++++++++++++++++++
src/feature/hs/hs_pow.h | 9 ++
src/feature/hs/include.am | 1 +
src/test/fuzz/include.am | 3 +-
src/test/include.am | 16 +--
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
--
To stop receiving notification emails like this one, please contact
the administrator of this repository.
_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits