Skip to content

demux-hash-flooding.md #1

Closed
Closed

Description

@aotodev

Flow table hash is unseeded and floodable

Problem

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

  1. self-assigned this
    on Sep 30, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

No labels
No labels

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions