A hash table usually feels like an array with a little math in front of it.

bucket = hash(key) mod table_size

When the keys are friendly, or when the hash function behaves like a random function for the workload, the table looks constant-time. Each bucket is short. Lookup is a short walk. Insert is a short append.

But “expected constant time” is a bargain with the input distribution. It is not a promise to an adversary who is allowed to choose the keys.

Hash flooding is what happens when that adversary buys one bucket and turns it into the queue.

Average Case Is Not A Security Boundary

Scott Crosby and Dan Wallach’s 2003 USENIX Security paper framed a broader class of algorithmic-complexity attacks: small inputs can force common data structures out of their average case and into their worst case.1 Their examples included hash tables in Perl, Squid, and Bro. The USENIX summary is blunt: hash tables and binary trees can degenerate to linked lists when the input is carefully chosen.2

The mechanism for a chained hash table is painfully simple.

If n distinct keys all land in one bucket, and insertion checks for duplicates by scanning the chain before appending, the comparison count is:

\[0 + 1 + 2 + \cdots + (n-1) = {n(n-1)\over 2}.\]

That is not a micro-optimization failure. It is a different asymptotic regime triggered by input.

random-looking keys:      many short chains
chosen colliding keys:    one long chain

Open addressing has a different floor plan, but the same warning. A flood does not need to break cryptography. It only needs enough control over bucket selection to make the table do a lot of equality checks, probes, or relocations per request.

Salting Is Not Automatically A Wall

A tempting repair is:

bucket = hash(secret, key) mod table_size

The word secret is doing real work only if the keyed function is hard to predict from what the attacker can observe.

If the hash is structurally weak, adding a secret offset may merely move the attacked bucket. In the lab below, the weak hash is an additive checksum:

weak_hash(key, seed) = seed + sum(bytes(key))

The generated attack strings are all different, but every one has the same byte sum. The seed changes the bucket number. It does not split the set.

That is why modern language runtimes moved toward keyed hash functions with a cryptographic security goal. Aumasson and Bernstein introduced SipHash as a fast pseudorandom function for short inputs, explicitly naming hash-table lookups protected against hash-flooding denial-of-service attacks as a target application.3 Their argument is not that collisions become impossible. For a table with m buckets, collisions always exist. The point is that, with an unpredictable keyed function, an attacker cannot cheaply manufacture a large set of new keys for one chosen bucket.

Python’s PEP 456 is a useful production record of that reasoning. It proposed SipHash as the default string and bytes hash algorithm for Python 3.4 and says the earlier FNV-based randomized scheme was not resilient against hash-collision DoS attacks.4 It also states the core problem plainly: FNV has no cryptographic properties, so randomization secrets can be calculated by a remote attacker when the surrounding implementation leaks enough information.5

The security boundary is not:

there is a seed somewhere

It is closer to:

given what the caller can see, can they predict many keys for the same bucket?

Lab: The Same Keys Under Two Hashes

The lab below builds a simple chained hash table. It inserts the same keys twice:

  1. under the weak additive checksum;
  2. under a small secret-mixer toy.

The second hash is not SipHash and is not a cryptographic recommendation. It is only a visible stand-in for the mitigation principle: mix the whole key with a secret in a way the attack strings were not built to defeat.

The attack key generator is real. For each key it creates five character pairs. Each pair has a constant byte sum:

az, by, cx, ...

Changing the pair changes the string, but not the additive checksum. That gives thousands of distinct keys with one weak bucket.

With the default settings, the lab measures:

Run Value
keys 512
buckets 128
weak max bucket 512
secret-mixer max bucket 9
weak insertion comparisons 130,816
secret-mixer insertion comparisons 961
weak lookup p95 512
secret-mixer lookup p95 7
insertion amplification 136.1x
Weak checksum Secret mixer toy Amplification

Deterministic chained-table model. The secret mixer is a toy, not SipHash; it exists so the same attack keys can be run through a non-additive keyed hash in the browser.

What The Graph Should Make Uncomfortable

The bucket chart is the whole story. Under the weak checksum, the attack does not make every bucket slightly worse. It makes one bucket enormous.

That matters because a request parser, JSON decoder, HTTP parameter collector, or router table often builds a hash table while holding a worker thread. If the attacker can make one request spend O(n^2) comparisons, a low-bandwidth input becomes a high-CPU event.

The insertion curve shows the triangular number directly. With 512 keys in one chain:

\[{512\cdot511\over2}=130{,}816.\]

The secret-mixer toy spends 961 comparisons on the same strings because the strings no longer share a bucket. The improvement is not because chaining became clever. The input no longer controls the bucket map.

Audit Grid

The lab exports a Node audit that checks bucket accounting, finite outputs, the triangular comparison count for the flood case, and the spread of the keyed toy: five measured rows and 39 named checks.

Scenario Keys Buckets Weak comparisons Keyed comparisons Weak max bucket Keyed max bucket Amplification
same weak checksum 512 128 130,816 961 512 9 136.1x
same weak checksum 1024 256 523,776 2,003 1024 12 261.5x
flood plus ordinary keys 768 128 61,118 2,246 348 12 27.2x
ordinary keys 768 128 2,412 2,334 15 13 1.0x
same weak checksum 256 64 32,640 497 256 9 65.7x

The ordinary-key row is important. It is the trap. The weak checksum can look fine under a benign corpus. The security question is not whether the table performs on your sample. It is whether the caller can cheaply move your sample into the worst case.

To reproduce the deterministic audit grid from the repository root:

node - <<'NODE'
const lab = require("./assets/js/hash-flood-lab.js");
const EXPECTED_CASE_SHAPE = [
  "1:flood:512/128:17/35:130816/961:512/9:512.000/7.000:9",
  "2:flood:1024/256:91/50:523776/2003:1024/12:1024.000/6.000:9",
  "3:mixed:768/128:23/20:61118/2246:348/12:288.100/8.000:6",
  "4:random:768/128:23/20:2412/2334:15/13:9.000/10.000:6",
  "5:flood:256/64:404/80:32640/497:256/9:256.000/6.050:9"
];
const EXPECTED_CASE_ROWS = [
  "1:flood:keys=512:buckets=128:weak=130816:keyed=961:max=512/9:p95=512.000/7.000:amp=136.1:checks=9/9:passed=true",
  "2:flood:keys=1024:buckets=256:weak=523776:keyed=2003:max=1024/12:p95=1024.000/6.000:amp=261.5:checks=9/9:passed=true",
  "3:mixed:keys=768:buckets=128:weak=61118:keyed=2246:max=348/12:p95=288.100/8.000:amp=27.2:checks=6/6:passed=true",
  "4:random:keys=768:buckets=128:weak=2412:keyed=2334:max=15/13:p95=9.000/10.000:amp=1.0:checks=6/6:passed=true",
  "5:flood:keys=256:buckets=64:weak=32640:keyed=497:max=256/9:p95=256.000/6.050:amp=65.7:checks=9/9:passed=true"
];
const COMMON_CHECK_NAMES = [
  "weak rows match key count",
  "keyed rows match key count",
  "comparison counts finite",
  "bucket accounting weak",
  "bucket accounting keyed",
  "lookup p95 finite"
];
const FLOOD_CHECK_NAMES = [
  ...COMMON_CHECK_NAMES.slice(0, 5),
  "flood keys share one weak bucket",
  "flood comparisons are triangular",
  "keyed mixer spreads flood set",
  COMMON_CHECK_NAMES[5]
];
const EXPECTED_CHECKS_BY_CASE = [
  FLOOD_CHECK_NAMES,
  FLOOD_CHECK_NAMES,
  COMMON_CHECK_NAMES,
  COMMON_CHECK_NAMES,
  FLOOD_CHECK_NAMES
];
const EXPECTED_CHECK_ROWS = [
  "1:weak rows match key count=true|keyed rows match key count=true|comparison counts finite=true|bucket accounting weak=true|bucket accounting keyed=true|flood keys share one weak bucket=true|flood comparisons are triangular=true|keyed mixer spreads flood set=true|lookup p95 finite=true",
  "2:weak rows match key count=true|keyed rows match key count=true|comparison counts finite=true|bucket accounting weak=true|bucket accounting keyed=true|flood keys share one weak bucket=true|flood comparisons are triangular=true|keyed mixer spreads flood set=true|lookup p95 finite=true",
  "3:weak rows match key count=true|keyed rows match key count=true|comparison counts finite=true|bucket accounting weak=true|bucket accounting keyed=true|lookup p95 finite=true",
  "4:weak rows match key count=true|keyed rows match key count=true|comparison counts finite=true|bucket accounting weak=true|bucket accounting keyed=true|lookup p95 finite=true",
  "5:weak rows match key count=true|keyed rows match key count=true|comparison counts finite=true|bucket accounting weak=true|bucket accounting keyed=true|flood keys share one weak bucket=true|flood comparisons are triangular=true|keyed mixer spreads flood set=true|lookup p95 finite=true"
];
const EXPECTED_CASES = EXPECTED_CASE_SHAPE.length;
const EXPECTED_CHECKS = EXPECTED_CHECKS_BY_CASE.reduce(
  (sum, checks) => sum + checks.length,
  0
);
const EXPECTED_TOTALS = {
  rows: EXPECTED_CASES,
  passed: EXPECTED_CASES,
  total: EXPECTED_CASES,
  passedChecks: EXPECTED_CHECKS,
  totalChecks: EXPECTED_CHECKS
};

function sameList(left, right) {
  return left.length === right.length &&
    left.every((value, index) => value === right[index]);
}

function sameJson(left, right) {
  return JSON.stringify(left) === JSON.stringify(right);
}

function rowDrifts(actual, expected) {
  const count = Math.max(actual.length, expected.length);
  const drift = [];
  for (let index = 0; index < count; index += 1) {
    if (actual[index] !== expected[index]) {
      drift.push({ index, actual: actual[index], expected: expected[index] });
    }
  }
  return drift;
}

function auditShape(audit) {
  return {
    totals: {
      rows: audit.cases.length,
      passed: audit.passed,
      total: audit.total,
      passedChecks: audit.passedChecks,
      totalChecks: audit.totalChecks
    },
    cases: audit.cases.map(
      (row) => `${row.caseId}:${row.scenario}:${row.keys}/${row.buckets}:` +
        `${row.seed}/${row.lookupMix}:` +
        `${row.weakComparisons}/${row.keyedComparisons}:` +
        `${row.weakMaxBucket}/${row.keyedMaxBucket}:` +
        `${row.weakLookupP95.toFixed(3)}/${row.keyedLookupP95.toFixed(3)}:` +
        `${row.totalChecks}`
    ),
    caseRows: audit.cases.map(
      (row) => `${row.caseId}:${row.scenario}:keys=${row.keys}:` +
        `buckets=${row.buckets}:weak=${row.weakComparisons}:` +
        `keyed=${row.keyedComparisons}:` +
        `max=${row.weakMaxBucket}/${row.keyedMaxBucket}:` +
        `p95=${row.weakLookupP95.toFixed(3)}/${row.keyedLookupP95.toFixed(3)}:` +
        `amp=${row.amplification.toFixed(1)}:` +
        `checks=${row.passedChecks}/${row.totalChecks}:passed=${row.passed}`
    ),
    checkRows: audit.cases.map(
      (row) => `${row.caseId}:` +
        row.checks.map((check) => `${check.name}=${check.passed}`).join("|")
    ),
    checksByCase: audit.cases.map((row) => row.checks.map((check) => check.name))
  };
}

const audit = lab.auditGrid();
const shape = auditShape(audit);
const failed = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const caseRowDrifts = rowDrifts(shape.caseRows, EXPECTED_CASE_ROWS);
const checkRowDrifts = rowDrifts(shape.checkRows, EXPECTED_CHECK_ROWS);
const shapeErrors = [
  sameJson(shape.totals, EXPECTED_TOTALS) ? null : "totals",
  sameList(shape.cases, EXPECTED_CASE_SHAPE) ? null : "cases",
  caseRowDrifts.length ? "caseRows" : null,
  checkRowDrifts.length ? "checkRows" : null,
  shape.checksByCase.every((checks, index) =>
    sameList(checks, EXPECTED_CHECKS_BY_CASE[index] || [])
  ) ? null : "checksByCase"
].filter(Boolean);
console.table(audit.cases.map((row) => ({
  scenario: row.scenario,
  keys: row.keys,
  buckets: row.buckets,
  weakComparisons: row.weakComparisons,
  keyedComparisons: row.keyedComparisons,
  weakMaxBucket: row.weakMaxBucket,
  keyedMaxBucket: row.keyedMaxBucket,
  amplification: row.amplification.toFixed(1) + "x",
  checks: `${row.passedChecks}/${row.totalChecks}`
})));
const summary =
  `${audit.passed}/${audit.total} cases and ${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (
  shapeErrors.length ||
  failed.length ||
  !audit.ok ||
  audit.passed !== audit.total ||
  audit.passedChecks !== audit.totalChecks
) {
  throw new Error(JSON.stringify({
    summary,
    shapeErrors,
    shape,
    drifts: {
      caseRows: caseRowDrifts,
      checkRows: checkRowDrifts
    },
    failed,
    failures: audit.failures,
    passed: audit.passed,
    total: audit.total,
    passedChecks: audit.passedChecks,
    totalChecks: audit.totalChecks
  }, null, 2));
}
console.log(summary);
NODE

Defenses Are Layered

A keyed hash is a major defense because it makes bucket selection unpredictable to the caller. It is not the whole system.

Practical defenses usually combine several limits:

  • keyed, per-process hashing for attacker-controlled strings;
  • request-size and parameter-count caps;
  • parser budgets that fail closed before one request monopolizes a worker;
  • collision telemetry, especially max chain length or probe length;
  • fallback structures, such as tree bins, when one bucket grows too large;
  • not exposing raw hash values or timing channels that help recover the secret.

The last point is why PEP 456’s discussion is more subtle than “salt FNV.” A non-cryptographic hash can be fast and well distributed for ordinary inputs, yet still leak enough algebraic structure for an adaptive attacker. SipHash’s selling point for hash tables is that it gives the hash function a PRF-style unpredictability goal while staying fast on short strings.6

The Boundary Of The Toy

This post does not claim the toy keyed mixer is secure. It is not.

It also does not model every production table. CPython dictionaries are open addressed, Java 8 can treeify long bins in HashMap, many runtimes resize and probe in implementation-specific ways, and web frameworks often cap parameter counts before the language hash table sees the full attack. Those details matter.

The toy isolates one invariant:

if a caller can choose many keys for one bucket, the table is no longer in its average case

Once that invariant is visible, the engineering review gets sharper. A hash function is not only a spreader of keys. On a public input boundary, it is part of the denial-of-service surface.

Review Questions

Before trusting a hash table on attacker-controlled keys, I want the review to answer:

  • Is the hash function keyed per process or per table?
  • Does it have a security goal, or only a distribution benchmark?
  • Can users observe hash values, bucket indices, error timing, or collision behavior?
  • What is the maximum accepted key count per request?
  • What happens when a chain, probe run, or bucket crosses a threshold?
  • Is the collision metric visible in production telemetry?

The constant-time story is still useful. It just needs its condition attached:

expected O(1), assuming the caller cannot steer the distribution

When the caller can steer it, the bucket becomes the queue.

Sources

  1. Scott A. Crosby and Dan S. Wallach, “Denial of Service via Algorithmic Complexity Attacks”, USENIX Security 2003. ↩

  2. The USENIX paper page summarizes the result: low-bandwidth attacks can exploit average-case data structures, and the authors demonstrated attacks against Perl, Squid, and Bro hash-table implementations. ↩

  3. Jean-Philippe Aumasson and Daniel J. Bernstein, “SipHash: a fast short-input PRF”, 2012. The abstract names hash-table lookups protected against hash-flooding denial-of-service attacks as a target application. ↩

  4. Christian Heimes, “PEP 456: Secure and interchangeable hash algorithm”, Python Enhancement Proposals, final for Python 3.4. The PEP proposes SipHash as Python’s default string and bytes hash algorithm. ↩

  5. PEP 456, sections “Rationale” and “Current implementation with modified FNV.” The PEP describes CPython’s earlier FNV-style hash, the added prefix/suffix randomization, and why non-cryptographic hashing was not considered sufficient against hash-collision DoS attacks. ↩

  6. Aumasson and Bernstein, “SipHash: a fast short-input PRF”, Section 7. They argue that a strong PRF makes bucket indices unpredictable even after selected observations, and that short-input performance is critical for hash-table applications. ↩