dns: Make TTLs fuzzy at exit relays

This change mitigates DNS-based website oracles by making the time that
a domain name is cached uncertain (+- 4 minutes of what's measurable).

Resolves TROVE-2021-009.

Fixes #40674

2 files changed, 26 insertions, 4 deletions

diff --git a/src/core/or/connection_edge.c b/src/core/or/connection_edge.c
index d071bf8937..7bed089449 100644
--- a/src/core/or/connection_edge.c
+++ b/src/core/or/connection_edge.c
@@ -102,6 +102,7 @@
 #include "feature/stats/predict_ports.h"
 #include "feature/stats/rephist.h"
 #include "lib/buf/buffers.h"
+#include "lib/crypt_ops/crypto_rand.h"
 #include "lib/crypt_ops/crypto_util.h"
 
 #include "core/or/cell_st.h"
@@ -484,6 +485,21 @@ clip_dns_ttl(uint32_t ttl)
     return MAX_DNS_TTL;
 }
 
+/** Given a TTL (in seconds), determine what TTL an exit relay should use by
+ * first clipping as usual and then adding some randomness which is sampled
+ * uniformly at random from [-FUZZY_DNS_TTL, FUZZY_DNS_TTL].  This facilitates
+ * fuzzy TTLs, which makes it harder to infer when a website was visited via
+ * side-channels like DNS (see "Website Fingerprinting with Website Oracles").
+ *
+ * Note that this can't underflow because FUZZY_DNS_TTL < MIN_DNS_TTL.
+ */
+uint32_t
+clip_dns_fuzzy_ttl(uint32_t ttl)
+{
+  return clip_dns_ttl(ttl) +
+    crypto_rand_uint(1 + 2*FUZZY_DNS_TTL) - FUZZY_DNS_TTL;
+}
+
 /** Send a relay end cell from stream <b>conn</b> down conn's circuit, and
  * remember that we've done so.  If this is not a client connection, set the
  * relay end cell's reason for closing as <b>reason</b>.
diff --git a/src/core/or/connection_edge.h b/src/core/or/connection_edge.h
index 966a9391d8..1816f2a463 100644
--- a/src/core/or/connection_edge.h
+++ b/src/core/or/connection_edge.h
@@ -187,11 +187,9 @@ void connection_ap_warn_and_unmark_if_pending_circ(
                                              entry_connection_t *entry_conn,
                                              const char *where);
 
-/** Lowest value for DNS ttl that a server should give or a client should
- * believe. */
+/** Lowest value for DNS ttl clipping excluding the random addition. */
 #define MIN_DNS_TTL (5*60)
-/** Highest value for DNS ttl that a server should give or a client should
- * believe. */
+/** Highest value for DNS ttl clipping excluding the random addition. */
 #define MAX_DNS_TTL (60*60)
 /** How long do we keep DNS cache entries before purging them (regardless of
  * their TTL)? */
@@ -199,8 +197,16 @@ void connection_ap_warn_and_unmark_if_pending_circ(
 /** How long do we cache/tell clients to cache DNS records when no TTL is
  * known? */
 #define DEFAULT_DNS_TTL (30*60)
+/** How much should we +- each TTL to make it fuzzy with uniform sampling at
+ * exits?  The value 4 minutes was chosen so that the lowest possible clip is
+ * 60s.  Such low clips were used in the past for all TTLs due to a bug in Tor,
+ * see "The effect of DNS on Tor's Anonymity" by Greschbach et al.  In other
+ * words, sampling such low clips is unlikely to cause any breakage at exits.
+ */
+#define FUZZY_DNS_TTL (4*60)
 
 uint32_t clip_dns_ttl(uint32_t ttl);
+uint32_t clip_dns_fuzzy_ttl(uint32_t ttl);
 
 int connection_half_edge_is_valid_data(const smartlist_t *half_conns,
                                        streamid_t stream_id);