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@torproject.org AuthorDate: Mon Jun 27 16:03:54 2022 -0400
hs: Add solve and verify PoW functions
Signed-off-by: David Goulet dgoulet@torproject.org --- 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