Tor onion service INTRODUCE2 invalid-MAC cells permanently grow service replay cache

How it was found

Summary

A remote client can send well-formed v3 INTRODUCE1 cells whose encrypted section has an invalid MAC but a unique byte pattern. The introduction point parses and forwards these cells to the onion service as INTRODUCE2. On the service side, hs_cell_parse_introduce2() inserts the attacker-controlled encrypted section into the intro-point replay cache before verifying the INTRODUCE2 MAC.

The intro-point replay cache is created with replaycache_new(0, 0), meaning entries never expire. Since MAC-invalid INTRODUCE2 cells fail before ip->introduce2_count++, they also do not advance the normal introduction-count rotation threshold. A malicious client can therefore grow an onion service's per-introduction-point replay cache with unauthenticated data until memory pressure or OOM.

Root Cause

src/feature/hs/hs_cell.c:1015-1034 adds the encrypted section to the replay cache before key/MAC validation:

if (replaycache_add_test_and_elapsed(data->replay_cache, encrypted_section,
                                     encrypted_section_len, &elapsed)) {
  ...
  goto done;
}

...
intro_keys = get_introduce2_keys_and_verify_mac(data, encrypted_section,
                                                encrypted_section_len);
if (!intro_keys) {
  ...
  goto done;
}

src/feature/hs/hs_service.c:539 creates the per-introduction-point replay cache with no expiration:

ip->replay_cache = replaycache_new(0, 0);

src/feature/hs_common/replaycache.c:122-127 allocates a new time_t and inserts a digest for every new input. With horizon == 0, replaycache_scrub_if_needed_internal() returns without scrubbing.

src/feature/hs/hs_circuit.c:1342-1369 increments ip->introduce2_count only after hs_cell_parse_introduce2() succeeds. Invalid-MAC cells return before this point, so the count-based intro-point rotation threshold is not reached.

Reachability

1. A client obtains a public onion-service descriptor and sends INTRODUCE1 cells to the advertised introduction point.
2. The intro point parses the non-encrypted portion, finds the service intro circuit by auth key, and forwards the same payload as RELAY_COMMAND_INTRODUCE2 (src/feature/hs/hs_intropoint.c:653-710).
3. One INTRODUCE1 is allowed per client circuit, but an attacker can create many introduction circuits. The default onion-service intro DoS defense is disabled (HS_CONFIG_V3_DOS_DEFENSE_DEFAULT 0 in src/feature/hs/hs_config.h:20), and the relay-side INTRODUCE2 token-bucket default is also disabled (HS_DOS_INTRODUCE_ENABLED_DEFAULT 0 in src/feature/hs/hs_dos.c:47).
4. The onion service stores each unique encrypted section in ip->replay_cache before MAC validation. Mutating only the final MAC byte preserves trunnel framing but guarantees MAC failure.

Proof of Concept

I added an in-tree regression test:

• File: src/test/test_hs_service.c
• Test: hs_service/intro2_invalid_mac_replay_cache_growth

{F5843398}:

1. Builds a legitimate INTRODUCE1 payload with Tor's existing hs_circ_send_introduce1() helper.
2. Mutates only the final byte of the MAC, preserving valid INTRODUCE1/INTRODUCE2 framing.
3. Delivers eight unique invalid-MAC payloads through hs_circ_handle_introduce2().
4. Asserts each payload is rejected.
5. Asserts ip->introduce2_count remains zero.
6. Asserts digest256map_size(ip->replay_cache->digests_seen) grows from 0 to 8.

Reproduction:

git apply h1-submissions/tor-hs-introduce2-invalid-mac-replaycache-dos-poc.patch
make -j2 src/test/test
./src/test/test hs_service/intro2_invalid_mac_replay_cache_growth

Observed output:

hs_service/intro2_invalid_mac_replay_cache_growth: [forking] OK
1 tests ok.  (0 skipped)

I also reran the existing normal-path test:

hs_service/intro2_handling: [forking] OK
1 tests ok.  (0 skipped)

Suggested Fix

Do not insert the INTRODUCE2 encrypted section into the non-expiring intro-point replay cache until after the MAC has been verified. If Tor wants early replay suppression for invalid cells to avoid repeated crypto work, use a separate bounded and short-lived negative cache with explicit size limits and expiration.

At minimum, the fix should ensure attacker-controlled MAC-invalid encrypted sections cannot create permanent entries and cannot bypass the normal intro-point rotation/resource accounting.

Impact

The attacker controls the number of permanent replay-cache entries added to the onion service for an intro point. These entries are not removed by replay-cache time expiration, and invalid cells do not count toward the 16,384 to 32,768 valid-INTRODUCE2 introduction-count rotation threshold. The time-based intro-point lifetime is 18 to 24 hours, giving a large window for sustained memory growth.

Each unique invalid encrypted section creates one digest256map entry and one separately allocated time_t. The map entry stores a 32-byte digest key, a value pointer, hash-table linkage, allocator metadata, and the time_t value allocation. A reasonable 64-bit estimate is about 64 to 96 bytes per unique invalid INTRODUCE2, before hash-table resizing overhead. At 100, 500, and 1000 fresh introduction circuits per minute, that is roughly 0.4 to 0.6 MB/hour, 1.9 to 2.9 MB/hour, and 3.8 to 5.8 MB/hour per targeted intro point. Across the 18 to 24 hour intro-point lifetime window, a sustained attacker can accumulate tens to low hundreds of MB of service RSS, and more with parallel clients or higher circuit creation rates.

This is an availability issue. I am not claiming code execution, information disclosure, or integrity impact.

CVSS:3.0/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L Justification:

• AV:N: the attack is delivered over normal Tor onion-service introduction circuits.
• AC:L: no race or heap shaping is required; each malformed INTRODUCE1 only needs valid public framing and a unique invalid MAC byte pattern.
• PR:N: public onion services expose introduction points to unauthenticated clients.
• UI:N: no user interaction is needed.
• S:U: the affected component is the onion service process that receives INTRODUCE2.
• C:N/I:N: no confidentiality or integrity impact is claimed.
• A:L: the demonstrated impact is unbounded memory growth, but the PoC does not show immediate service loss or a one-shot crash.

Escalation note: CVSS:3.0/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H is defensible if you classify sustained, unauthenticated memory growth until OOM as high availability impact, especially for onion services running near a memory ceiling.