commit fd3da15d2a0e8806f407c24060c660122da83da7
parent c217699db1c5be02a59d7367decdb92b32827210
Author: David Goulet <dgoulet@torproject.org>
Date: Wed, 22 Jan 2025 09:06:14 -0500
Merge branch 'maint-0.4.8'
Diffstat:
10 files changed, 229 insertions(+), 36 deletions(-)
diff --git a/changes/ticket40996 b/changes/ticket40996
@@ -0,0 +1,5 @@
+ o Major bugfixes (onion service directory cache):
+ - When the OOM killer kicks in, cleanup the descriptor cache of an HSDir by
+ looking at the lowest downloaded count instead of time in cache. Fixes bug
+ 40996; bugfix on 0.3.5.1-alpha.
+
diff --git a/src/core/or/relay.c b/src/core/or/relay.c
@@ -2940,7 +2940,7 @@ cell_queues_check_size(void)
if (hs_cache_total > get_options()->MaxMemInQueues / 5) {
const size_t bytes_to_remove =
hs_cache_total - (size_t)(get_options()->MaxMemInQueues / 10);
- removed = hs_cache_handle_oom(now, bytes_to_remove);
+ removed = hs_cache_handle_oom(bytes_to_remove);
oom_stats_n_bytes_removed_hsdir += removed;
alloc -= removed;
}
diff --git a/src/feature/dircache/dircache.c b/src/feature/dircache/dircache.c
@@ -26,6 +26,7 @@
#include "feature/dircommon/directory.h"
#include "feature/dircommon/fp_pair.h"
#include "feature/hs/hs_cache.h"
+#include "feature/hs/hs_ident.h"
#include "feature/nodelist/authcert.h"
#include "feature/nodelist/networkstatus.h"
#include "feature/nodelist/routerlist.h"
@@ -34,6 +35,7 @@
#include "feature/stats/geoip_stats.h"
#include "feature/stats/rephist.h"
#include "lib/compress/compress.h"
+#include "lib/crypt_ops/crypto_format.h"
#include "feature/dircache/cached_dir_st.h"
#include "feature/dircommon/dir_connection_st.h"
@@ -1381,6 +1383,17 @@ handle_get_hs_descriptor_v3(dir_connection_t *conn,
write_http_response_header(conn, strlen(desc_str), NO_METHOD, 0);
connection_buf_add(desc_str, strlen(desc_str), TO_CONN(conn));
+ /* We have successfully written the descriptor on the connection outbuf so
+ * save this query identifier into the dir_connection_t in order
+ * to associate it to the descriptor when closing. */
+ {
+ /* Decode blinded key. This is certain to work else
+ * hs_cache_lookup_as_dir() would have failed. */
+ ed25519_public_key_t blinded_key;
+ ed25519_public_from_base64(&blinded_key, pubkey_str);
+ conn->hs_ident = hs_ident_server_dir_conn_new(&blinded_key);
+ }
+
done:
return 0;
}
diff --git a/src/feature/dircommon/dir_connection_st.h b/src/feature/dircommon/dir_connection_st.h
@@ -44,7 +44,9 @@ struct dir_connection_t {
/* Hidden service connection identifier for dir connections: Used by HS
client-side code to fetch HS descriptors, and by the service-side code to
- upload descriptors. */
+ upload descriptors. Also used by the HSDir, setting only the blinded key,
+ in order to locate back the descriptor in the cache once the dir stream is
+ closed. */
struct hs_ident_dir_conn_t *hs_ident;
/** If this is a one-hop connection, tracks the state of the directory guard
diff --git a/src/feature/dircommon/directory.c b/src/feature/dircommon/directory.c
@@ -16,6 +16,7 @@
#include "feature/dirclient/dirclient.h"
#include "feature/dircommon/directory.h"
#include "feature/dircommon/fp_pair.h"
+#include "feature/hs/hs_cache.h"
#include "feature/stats/geoip_stats.h"
#include "lib/compress/compress.h"
@@ -492,6 +493,17 @@ connection_dir_about_to_close(dir_connection_t *dir_conn)
connection_dir_client_request_failed(dir_conn);
}
+ /* If we are an HSDir, mark the corresponding descriptor as downloaded. This
+ * is needed for the OOM cache cleanup.
+ *
+ * This is done when the direction connection is closed in order to raise the
+ * attack cost of filling the cache with bogus descriptors. That attacker
+ * would need to increase that downloaded counter for the attack to be
+ * successful which is expensive. */
+ if (conn->purpose == DIR_PURPOSE_SERVER && dir_conn->hs_ident) {
+ hs_cache_mark_dowloaded_as_dir(dir_conn->hs_ident);
+ }
+
connection_dir_client_refetch_hsdesc_if_needed(dir_conn);
}
diff --git a/src/feature/hs/hs_cache.c b/src/feature/hs/hs_cache.c
@@ -68,7 +68,7 @@ store_v3_desc_as_dir(hs_cache_dir_descriptor_t *desc)
}
/** Query our cache and return the entry or NULL if not found. */
-static hs_cache_dir_descriptor_t *
+STATIC hs_cache_dir_descriptor_t *
lookup_v3_desc_as_dir(const uint8_t *key)
{
tor_assert(key);
@@ -224,6 +224,71 @@ cache_lookup_v3_as_dir(const char *query, const char **desc_out)
return -1;
}
+/** Clean the v3 cache by removing entries that are below or equal the
+ * downloaded target.
+ *
+ * Stop when the max_remove_bytes is reached. It is possible that more bytes
+ * are removed if max_remove_bytes is not aligned on cache entry size.
+ *
+ * Return the amount of bytes freed. The next_lowest param is set to the
+ * lowest n_downloaded value in the cache that is above target.
+ *
+ * If both next_lowest and returned value are 0, the cache is empty. */
+STATIC size_t
+cache_clean_v3_by_downloaded_as_dir(const uint64_t target,
+ const size_t max_remove_bytes,
+ uint64_t *next_lowest)
+{
+ size_t bytes_removed = 0;
+ uint64_t lowest = 0;
+
+ if (!hs_cache_v3_dir) { /* No cache to clean. Just return. */
+ goto end;
+ }
+
+ log_info(LD_REND, "Cleaning HS cache for downloaded target of %" PRIu64
+ ". Maximum bytes to removed: %zu",
+ target, max_remove_bytes);
+
+ DIGEST256MAP_FOREACH_MODIFY(hs_cache_v3_dir, key,
+ hs_cache_dir_descriptor_t *, entry) {
+ /* Downloaded counter is above target, ignore. Record next lowest. */
+ if (entry->n_downloaded > target) {
+ if (lowest == 0 || lowest > entry->n_downloaded) {
+ lowest = entry->n_downloaded;
+ }
+ continue;
+ }
+ /* We have removed enough, avoid cleaning this entry. Reason we continue
+ * the loop is so we can find the next lowest value. Yes, with many
+ * entries, this could be expensive but this is only called during OOM
+ * cleanup which should be fairly rare. */
+ if (bytes_removed >= max_remove_bytes) {
+ continue;
+ }
+ size_t entry_size = cache_get_dir_entry_size(entry);
+ /* Logging. */
+ {
+ char key_b64[BASE64_DIGEST256_LEN + 1];
+ digest256_to_base64(key_b64, (const char *) key);
+ log_info(LD_REND, "Removing v3 descriptor '%s' from HSDir cache. "
+ "Downloaded %" PRIu64 " times and size of %zu bytes",
+ safe_str_client(key_b64), entry->n_downloaded, entry_size);
+ }
+ /* Remove it from our cache. */
+ MAP_DEL_CURRENT(key);
+ bytes_removed += entry_size;
+ /* Entry is not in the cache anymore, destroy it. */
+ cache_dir_desc_free(entry);
+ /* Update our cache entry allocation size for the OOM. */
+ hs_cache_decrement_allocation(entry_size);
+ } DIGEST256MAP_FOREACH_END;
+
+ end:
+ *next_lowest = lowest;
+ return bytes_removed;
+}
+
/** Clean the v3 cache by removing any entry that has expired using the
* <b>global_cutoff</b> value. If <b>global_cutoff</b> is 0, the cleaning
* process will use the lifetime found in the plaintext data section. Return
@@ -334,6 +399,22 @@ hs_cache_lookup_as_dir(uint32_t version, const char *query,
return found;
}
+/** Using the given directory identifier, lookup the descriptor in our cache
+ * and if present, increment the downloaded counter. This is done when the
+ * directory connection fetching this descriptor is closed. */
+void
+hs_cache_mark_dowloaded_as_dir(const hs_ident_dir_conn_t *ident)
+{
+ hs_cache_dir_descriptor_t *entry;
+
+ tor_assert(ident);
+
+ entry = lookup_v3_desc_as_dir(ident->blinded_pk.pubkey);
+ if (entry) {
+ entry->n_downloaded++;
+ }
+}
+
/** Clean all directory caches using the current time now. */
void
hs_cache_clean_as_dir(time_t now)
@@ -1071,45 +1152,28 @@ hs_cache_client_new_auth_parse(const ed25519_public_key_t *service_pk)
* min_remove_bytes if the caches get emptied out so the caller should be
* aware of this. */
size_t
-hs_cache_handle_oom(time_t now, size_t min_remove_bytes)
+hs_cache_handle_oom(size_t min_remove_bytes)
{
- time_t k;
size_t bytes_removed = 0;
+ /* The downloaded counter value to remove. Start at 0 and increment to the
+ * next lowest value in the cache. */
+ uint64_t target = 0;
/* Our OOM handler called with 0 bytes to remove is a code flow error. */
tor_assert(min_remove_bytes != 0);
- /* The algorithm is as follow. K is the oldest expected descriptor age.
- *
- * 1) Deallocate all entries from v3 cache that are older than K hours
- * 2.1) If the amount of remove bytes has been reached, stop.
- * 2) Set K = K - 1 hour and repeat process until K is < 0.
- *
- * This ends up being O(Kn).
- */
-
- /* Set K to the oldest expected age in seconds which is the maximum
- * lifetime of a cache entry. */
- k = hs_cache_max_entry_lifetime();
-
+ /* Loop until we have an empty cache or we have removed enough bytes. */
do {
- time_t cutoff;
-
- /* If K becomes negative, it means we've empty the caches so stop and
- * return what we were able to cleanup. */
- if (k < 0) {
+ /* This is valid due to the loop condition. At the start, min_remove_bytes
+ * can't be 0. */
+ size_t bytes_to_free = (min_remove_bytes - bytes_removed);
+ size_t bytes_freed =
+ cache_clean_v3_by_downloaded_as_dir(target, bytes_to_free, &target);
+ if (bytes_freed == 0 && target == 0) {
+ /* Indicate that the cache is empty. */
break;
}
- /* Compute a cutoff value with K and the current time. */
- cutoff = now - k;
-
- if (bytes_removed < min_remove_bytes) {
- /* We haven't remove enough bytes so clean v3 cache. */
- bytes_removed += cache_clean_v3_as_dir(now, cutoff);
- /* Decrement K by a post period to shorten the cutoff, Two minutes
- * if we are a testing network, or one hour otherwise. */
- k -= get_options()->TestingTorNetwork ? 120 : 3600;
- }
+ bytes_removed += bytes_freed;
} while (bytes_removed < min_remove_bytes);
return bytes_removed;
@@ -1194,3 +1258,17 @@ hs_cache_increment_allocation(size_t n)
}
}
}
+
+#ifdef TOR_UNIT_TESTS
+
+/** Test only: Set the downloaded counter value of a HSDir cache entry. */
+void
+dir_set_downloaded(const ed25519_public_key_t *pk, uint64_t value)
+{
+ hs_cache_dir_descriptor_t *entry = lookup_v3_desc_as_dir(pk->pubkey);
+ if (entry) {
+ entry->n_downloaded = value;
+ }
+}
+
+#endif /* TOR_UNIT_TESTS */
diff --git a/src/feature/hs/hs_cache.h b/src/feature/hs/hs_cache.h
@@ -13,6 +13,7 @@
#include "feature/hs/hs_common.h"
#include "feature/hs/hs_descriptor.h"
+#include "feature/hs/hs_ident.h"
#include "feature/rend/rendcommon.h"
#include "feature/nodelist/torcert.h"
@@ -68,6 +69,10 @@ typedef struct hs_cache_dir_descriptor_t {
/** Encoded descriptor which is basically in text form. It's a NUL terminated
* string thus safe to strlen(). */
char *encoded_desc;
+ /** How many times this descriptor has been downloaded. We use this as an
+ * heuristic for the OOM cache cleaning. It is very large so we avoid an kind
+ * of possible wrapping. */
+ uint64_t n_downloaded;
} hs_cache_dir_descriptor_t;
/* Public API */
@@ -82,7 +87,7 @@ hs_cache_max_entry_lifetime(void)
void hs_cache_init(void);
void hs_cache_free_all(void);
void hs_cache_clean_as_dir(time_t now);
-size_t hs_cache_handle_oom(time_t now, size_t min_remove_bytes);
+size_t hs_cache_handle_oom(size_t min_remove_bytes);
unsigned int hs_cache_get_max_descriptor_size(void);
@@ -92,6 +97,7 @@ unsigned int hs_cache_get_max_descriptor_size(void);
int hs_cache_store_as_dir(const char *desc);
int hs_cache_lookup_as_dir(uint32_t version, const char *query,
const char **desc_out);
+void hs_cache_mark_dowloaded_as_dir(const hs_ident_dir_conn_t *ident);
const hs_descriptor_t *
hs_cache_lookup_as_client(const struct ed25519_public_key_t *key);
@@ -144,10 +150,18 @@ typedef struct hs_cache_client_descriptor_t {
} hs_cache_client_descriptor_t;
STATIC size_t cache_clean_v3_as_dir(time_t now, time_t global_cutoff);
+STATIC size_t cache_clean_v3_by_downloaded_as_dir(const uint64_t target,
+ const size_t min_remove_bytes,
+ uint64_t *next_lowest);
+STATIC hs_cache_dir_descriptor_t *lookup_v3_desc_as_dir(const uint8_t *key);
STATIC hs_cache_client_descriptor_t *
lookup_v3_desc_as_client(const uint8_t *key);
+#ifdef TOR_UNIT_TESTS
+void dir_set_downloaded(const ed25519_public_key_t *pk, uint64_t value);
+#endif /* TOR_UNIT_TESTS */
+
#endif /* defined(HS_CACHE_PRIVATE) */
#endif /* !defined(TOR_HS_CACHE_H) */
diff --git a/src/feature/hs/hs_ident.c b/src/feature/hs/hs_ident.c
@@ -62,6 +62,16 @@ hs_ident_dir_conn_free_(hs_ident_dir_conn_t *ident)
tor_free(ident);
}
+/** Return a newly allocated HS directory connection identifier that is meant
+ * for the server side (HSDir). Only the blinded key is known by the HSDir. */
+hs_ident_dir_conn_t *
+hs_ident_server_dir_conn_new(const ed25519_public_key_t *blinded_pk)
+{
+ hs_ident_dir_conn_t *ident = tor_malloc_zero(sizeof(*ident));
+ ed25519_pubkey_copy(&ident->blinded_pk, blinded_pk);
+ return ident;
+}
+
/** Initialized the allocated ident object with identity_pk and blinded_pk.
* None of them can be NULL since a valid directory connection identifier must
* have all fields set. */
diff --git a/src/feature/hs/hs_ident.h b/src/feature/hs/hs_ident.h
@@ -128,6 +128,8 @@ void hs_ident_dir_conn_free_(hs_ident_dir_conn_t *ident);
void hs_ident_dir_conn_init(const ed25519_public_key_t *identity_pk,
const ed25519_public_key_t *blinded_pk,
hs_ident_dir_conn_t *ident);
+hs_ident_dir_conn_t *hs_ident_server_dir_conn_new(
+ const ed25519_public_key_t *blinded_pk);
/* Edge connection identifier API. */
hs_ident_edge_conn_t *hs_ident_edge_conn_new(
diff --git a/src/test/test_hs_cache.c b/src/test/test_hs_cache.c
@@ -90,7 +90,7 @@ test_directory(void *arg)
tt_str_op(desc_out, OP_EQ, desc1_str);
/* Tell our OOM to run and to at least remove a byte which will result in
* removing the descriptor from our cache. */
- oom_size = hs_cache_handle_oom(time(NULL), 1);
+ oom_size = hs_cache_handle_oom(1);
tt_int_op(oom_size, OP_GE, 1);
ret = hs_cache_lookup_as_dir(3, helper_get_hsdir_query(desc1), NULL);
tt_int_op(ret, OP_EQ, 0);
@@ -127,7 +127,7 @@ test_directory(void *arg)
NULL);
tt_int_op(ret, OP_EQ, 0);
/* Cleanup our entire cache. */
- oom_size = hs_cache_handle_oom(time(NULL), 1);
+ oom_size = hs_cache_handle_oom(1);
tt_int_op(oom_size, OP_GE, 1);
hs_descriptor_free(desc_zero_lifetime);
tor_free(desc_zero_lifetime_str);
@@ -224,6 +224,61 @@ test_clean_as_dir(void *arg)
tor_free(desc1_str);
}
+static void
+test_clean_oom_as_dir(void *arg)
+{
+ size_t ret;
+ char *desc1_str = NULL, *desc2_str = NULL;
+ hs_descriptor_t *desc1 = NULL, *desc2 = NULL;
+ ed25519_keypair_t signing_kp1, signing_kp2;
+
+ (void) arg;
+
+ init_test();
+
+ /* Generate two valid descriptors. */
+ ret = ed25519_keypair_generate(&signing_kp1, 0);
+ tt_int_op(ret, OP_EQ, 0);
+ ret = ed25519_keypair_generate(&signing_kp2, 0);
+ tt_int_op(ret, OP_EQ, 0);
+ desc1 = hs_helper_build_hs_desc_with_ip(&signing_kp1);
+ tt_assert(desc1);
+ desc2 = hs_helper_build_hs_desc_with_ip(&signing_kp2);
+ tt_assert(desc2);
+ ret = hs_desc_encode_descriptor(desc1, &signing_kp1, NULL, &desc1_str);
+ tt_int_op(ret, OP_EQ, 0);
+ ret = hs_cache_store_as_dir(desc1_str);
+ tt_int_op(ret, OP_EQ, 0);
+ ret = hs_desc_encode_descriptor(desc2, &signing_kp2, NULL, &desc2_str);
+ tt_int_op(ret, OP_EQ, 0);
+ ret = hs_cache_store_as_dir(desc2_str);
+ tt_int_op(ret, OP_EQ, 0);
+
+ /* Set the downloaded count to 42 for the second one. */
+ dir_set_downloaded(&desc2->plaintext_data.blinded_pubkey, 42);
+ const hs_cache_dir_descriptor_t *entry =
+ lookup_v3_desc_as_dir(desc2->plaintext_data.blinded_pubkey.pubkey);
+ tt_u64_op(entry->n_downloaded, OP_EQ, 42);
+
+ /* Spin the OOM cleanup for only 1 descriptor (very low amount of bytes). We
+ * expect desc1 to be cleaned up because its downloaded counter is 0. */
+ size_t removed = hs_cache_handle_oom(1);
+ tt_size_op(removed, OP_GT, 0);
+
+ /* Desc1 is gone. */
+ entry = lookup_v3_desc_as_dir(desc1->plaintext_data.blinded_pubkey.pubkey);
+ tt_assert(!entry);
+ /* Desc2 is still there. */
+ entry = lookup_v3_desc_as_dir(desc2->plaintext_data.blinded_pubkey.pubkey);
+ tt_assert(entry);
+
+ done:
+ hs_descriptor_free(desc1);
+ hs_descriptor_free(desc2);
+ tor_free(desc1_str);
+ tor_free(desc2_str);
+}
+
/* Test helper: Fetch an HS descriptor from an HSDir (for the hidden service
with <b>blinded_key</b>. Return the received descriptor string. */
static char *
@@ -705,6 +760,8 @@ struct testcase_t hs_cache[] = {
NULL, NULL },
{ "clean_as_dir", test_clean_as_dir, TT_FORK,
NULL, NULL },
+ { "clean_oom_as_dir", test_clean_oom_as_dir, TT_FORK,
+ NULL, NULL },
{ "hsdir_revision_counter_check", test_hsdir_revision_counter_check, TT_FORK,
NULL, NULL },
{ "upload_and_download_hs_desc", test_upload_and_download_hs_desc, TT_FORK,
