You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Every key hash is FNV-1a with the fixed offset basis, and flow_table::bucket
keeps only the low log2(Slots) bits. The table uses linear probing and fills
to 7/8 before refusing inserts.
The hashed bytes are attacker-chosen:
by_peer / by_flow: the source port (16 bits), and on IPv6 the low 64 bits
of the source address.
by_payload_id: a QUIC client picks its own Initial destination connection id.
Finding N keys that share a bucket needs about N * Slots hash evaluations. Once
the accept path inserts them, they form one probe cluster. Every lookup that
lands in the cluster walks it, and that includes lookups for junk datagrams that
match no flow. At max_size a single lookup can cost 7/8 * Slots probes.
Separately, 7/8 load is high for linear probing even with a good hash. The
expected probe count for a miss is about (1 + 1/(1-a)^2) / 2, about 32 at
full load.
Proposed fix
Key the hash per table. Pick a seed at carve (for example from getrandom).
The minimal version keeps hash_value and runs its output through a seeded
finalizer in bucket. That forces the attacker to find full 64-bit FNV
collisions instead of low-bit ones. It raises the bar but is not a real keyed
hash.
The proper version makes the demux_key hash take a seed and uses a keyed
hash over the identity bytes (SipHash-1-3, or a seeded wyhash/rapidhash).
Consider lowering max_size to 3/4 or less, or document the probe cost at the
current limit.
Acceptance
Keys that collide in the low bits for one table do not collide in another
table's buckets.
A test inserts keys crafted to collide under the unseeded hash and checks the
longest probe run stays bounded.
Activity