TROVE-2021-005: hashtable-based DoS in circuit hsahtable

Reported by Jann Horn at Google:

##### cmux circuit muxinfo hashtable uses unsafe hash function #####
(short summary: The circuit muxinfo hashtable doesn't use siphash,
which has two consequences: A timing oracle exists that leaks with
~3ms timing delta (amplified when queries are batched) whether the
number of circuits established by a relay is a specific queried
number; and if an attacker knows that number, they should be able to
make a relay use 100% CPU with ~1.3 Mbit/s of traffic.)

Many of Tor's hash maps use Siphash in their hash functions, which I
think is intended to prevent HashDoS attacks (deliberately placing
tons of elements in a single hash table bucket); but
chanid_circid_entry_hash() doesn't do that:


typedef uint32_t circid_t;
[...]
static inline unsigned int
chanid_circid_entry_hash(chanid_circid_muxinfo_t *a)
{
    return (((unsigned int)(a->circ_id) << 8) ^
            ((unsigned int)((a->chan_id >> 32) & 0xffffffff)) ^
            ((unsigned int)(a->chan_id & 0xffffffff)));
}

Since inward-pointing circuit IDs (p_circ_id) come from the network,
filling a single hash bucket with lots of elements would be trivial if
the hash tables had power-of-2 numbers of buckets. But it's not that
easy because Tor's hash tables use prime numbers of buckets instead.

So to pull off a HashDoS attack against this hash table (beyond piling
128 elements into a bucket, which is trivial because the top 8 bits of
the circ_id are immediately shifted away), an attacker would first
have to guess the number of channels that the Tor instance has
established since it was started (->chan_id is allocated from a
monotonically incrementing counter that starts at zero).

But turning that around, an attacker could theoretically use this as
an oracle that checks whether a given Tor relay has established a
specific number of channels so far. If the rate of channel creation is
sufficiently slow, that might be usable to track the number of
channels that relays have established, which could maybe be useful for
locating a user's entry guard?

Attached is a test program that, given the IP+port of an Onion Router
and the expected ID of the next channel, connects to the OR and tries
to fill up a single hash bucket in a hash table with 49157 buckets:

 - cirid_dos.c: test program
 - cirid_dos.png: graph of response timings while circuits are added -
note that the Y axis is response time *for 128 batched requests*
because I wanted to reduce noise from stuff like TCP Nagle. measured
with Tor's logging disabled.

Given that my box just needs ~3ms per cell at the load limit of the
hash table, and a cell is 514 bytes (plus some overhead from TLS and
so on), and you need two cells to create and then destroy a circuit, I
guess this probably doesn't make a great DoS? You'd have to connect
directly to an Onion Router and constantly send it ~2.8 Mbits/s of
traffic. But the oracle part might be a little useful?

(AFAICS targeting a table with 49157 buckets, corresponding to a load
limit of 29494 entries, is the best an attacker can do here - once the
number of buckets bumps up to 98317, I think it's only possible to
construct roughly 21842 IDs that actually fall into a single bucket.)