Bug #8820
Updated by Jason Ish 7 days ago
Reported by Communications Security Establishment (CSE): <pre> ## Summary The Aho-Corasick multi-pattern matcher (`SCACSearch`) stores case-sensitive pattern IDs with only bit 31 used as the case flag, leaving bits 0–30 for the PID. The u16 search branch correctly recovers the PID with `AC_PID_MASK` (0x7FFFFFFF), but the u32 branch — taken whenever the automaton has ≥ 32767 states — recovers it with the literal `0x0000FFFF`, silently discarding PID bits 16–30. When a deployment loads more than 65536 distinct case-sensitive fast-patterns into a single AC context, every pattern with internal id ≥ 65536 is looked up in the wrong `pid_pat_list[]` slot at match time. The result is a deterministic detection bypass for those signatures (and possible false-positive firing of the aliased signature). The truncated index stays in-bounds and the offset/length arithmetic is still bounded, so no memory-safety violation occurs. ## Affected Piece of Code - **File:** `src/util-mpm-ac.c` - **Function / Location:** `SCACSearch()` u32 branch, ~L913–960 (specifically L923) - **Subsystem:** util-mpm-spm — Multi-pattern and single-pattern matchers (Aho-Corasick, Hyperscan, Boyer-Moore) ```c /* /home/omuser/claude/suricata/src/util-mpm-ac.c */ 913 } else { 914 register SC_AC_STATE_TYPE_U32 state = 0; 915 const SC_AC_STATE_TYPE_U32(*state_table_u32)[256] = ctx->state_table_u32; 916 for (uint32_t i = 0; i < buflen; i++) { 917 state = state_table_u32[state & 0x00FFFFFF][u8_tolower(buf[i])]; 918 if (state & 0xFF000000) { 919 const uint32_t no_of_entries = ctx->output_table[state & 0x00FFFFFF].no_of_entries; 920 const uint32_t *pids = ctx->output_table[state & 0x00FFFFFF].pids; 921 for (uint32_t k = 0; k < no_of_entries; k++) { 922 if (pids[k] & AC_CASE_MASK) { 923 const uint32_t lower_pid = pids[k] & 0x0000FFFF; /* BUG: should be AC_PID_MASK (0x7FFFFFFF) */ 924 const SCACPatternList *pat = &pid_pat_list[lower_pid]; 925 const int offset = i - pat->patlen + 1; 926 927 if (offset < (int)pat->offset || (pat->depth && i > pat->depth)) 928 continue; 929 if (pat->endswith && (uint32_t)offset + pat->patlen != buflen) 930 continue; 931 932 if (SCMemcmp(pat->cs, buf + offset, 933 pat->patlen) != 0) { ``` For comparison, the construction code that encodes the PID and the sibling u16 branch that decodes it correctly: ```c /* construction — src/util-mpm-ac.c:574-578 */ for (k = 0; k < ctx->output_table[state].no_of_entries; k++) { if (ctx->pid_pat_list[ctx->output_table[state].pids[k]].cs != NULL) { ctx->output_table[state].pids[k] &= AC_PID_MASK; /* 0x7FFFFFFF */ ctx->output_table[state].pids[k] |= ((uint32_t)1 << AC_CASE_BIT); } } /* u16 search branch — src/util-mpm-ac.c:876-878 */ if (pids[k] & AC_CASE_MASK) { const uint32_t lower_pid = pids[k] & AC_PID_MASK; /* correct */ const SCACPatternList *pat = &pid_pat_list[lower_pid]; ``` ## The Bug ### Encoding vs. decoding mismatch During automaton construction (`SCACInsertCaseSensitiveEntriesForPatterns`, L570–580), every case-sensitive pattern ID stored in `output_table[].pids[]` is encoded as: ``` pids[k] = (original_pid & AC_PID_MASK) | (1u << AC_CASE_BIT); = (original_pid & 0x7FFFFFFF) | 0x80000000; ``` Only bit 31 is the flag; bits 0–30 carry the PID. `max_pat_id` is a plain `uint32_t` that is incremented unbounded for every unique pattern added (`util-mpm.c:463`, `p->id = mpm_ctx->max_pat_id++`). Nothing in `SCACPreparePatterns()` or `MpmAddPattern()` caps it at 16 bits. At search time, the u16-state branch (taken when `ctx->state_count < 32767`) correctly inverts this encoding with `pids[k] & AC_PID_MASK` (L877). The u32-state branch — entered at L913 precisely when the ruleset is large enough that PID > 65535 becomes plausible — instead uses the hard-coded literal `0x0000FFFF` (L923). For any case-sensitive pattern whose internally assigned `id ≥ 65536`, bits 16–30 are dropped and `lower_pid` becomes `id mod 65536`. ### Consequences of the wrong index `pid_pat_list[lower_pid]` then resolves to a *different, valid* `SCACPatternList` entry (the array is `calloc`'d with `max_pat_id + 1` elements at L683, so `lower_pid ≤ 65535 < max_pat_id + 1` is always in-bounds). The aliased entry's `patlen`, `cs`, `offset`, `depth`, `endswith`, and `sids` are used in place of the real ones: 1. **Detection bypass.** `SCMemcmp(pat->cs, buf + offset, pat->patlen)` at L932 compares the *wrong* literal against the haystack. In the overwhelmingly common case the bytes differ, the loop `continue`s, and the intended signature's `sids` are never pushed into the `PrefilterRuleStore`. The rule never reaches the candidate list in `DetectRun()` and produces no alert. 2. **False positive / cross-fire.** If the aliased slot's `cs`/`patlen` happen to match the bytes at `buf + offset` (e.g. one pattern is a suffix of the other), the *wrong* `pat->sids` are pushed via `PrefilterAddSids()` (L939), and the de-dup `bitarray` bit is set/tested for the wrong PID (L937–938), which can additionally suppress a later legitimate hit on the aliased pattern. 3. **No OOB read.** Although the title mentions OOB read as the apparent risk, analysis shows the access stays bounded: - `lower_pid` is always a valid index into `pid_pat_list` (see above). - A negative `offset = i - pat->patlen + 1` from a *longer* aliased `patlen` is rejected by `offset < (int)pat->offset` at L927 (`pat->offset` is `uint16_t`, so the cast yields a value ≥ 0 and any negative `offset` fails the check). - The upper bound holds because `offset + pat->patlen == i + 1 ≤ buflen`, so `SCMemcmp` never reads past the haystack end. - If the aliased slot is a nocase pattern (`cs == NULL`), its `patlen` field is 0, so `SCMemcmp(NULL, _, 0)` is a no-op. ### Call chain from the wire to L923 ``` capture-thread slot → FlowWorker() src/flow-worker.c:562 → Detect() src/flow-worker.c:403/457 → src/detect.c:2846/2860 → DetectRun() src/detect.c:106 → DetectRunPrefilterPkt() src/detect.c:622 → Prefilter() src/detect-engine-prefilter.c:219 → engine->cb.Prefilter == PrefilterPktPayload() src/detect-engine-payload.c:116 → mpm_table[MPM_AC].Search == SCACSearch() src/util-mpm-ac.c:854 buf = p->payload buflen = p->payload_len ctx->state_count >= 32767 → u32 branch at L913 pids[k] has bit31 set (set at L576-577) → L922 true lower_pid = pids[k] & 0x0000FFFF → L923 truncates ``` ### Required field values / preconditions - `mpm-algo: ac` (the pure-software Aho-Corasick matcher; non-default when Hyperscan is compiled in). - `detect.sgh-mpm-context: single`, so that all fast-patterns are concentrated into one `MpmCtx`. - ≥ 65537 *unique* case-sensitive fast-pattern strings registered into that `MpmCtx`, so that at least one receives internal `id ≥ 65536`. This many distinct strings also guarantees `state_count ≥ 32767`, forcing the u32 table and the buggy branch. - Attacker sends a packet whose payload contains the literal bytes of one of those high-PID patterns. **Vulnerability class:** network-reachable logic bypass (mis-indexed lookup); originally suspected OOB read ruled out on closer analysis. ## Reproduction Results **Precondition (operator-side, not attacker-controllable):** 1. `suricata.yaml`: ```yaml mpm-algo: ac detect: sgh-mpm-context: single ``` 2. Generate a rule file with > 65536 rules, each carrying a unique case-sensitive `content` that is selected as the fast-pattern and lands in the same payload MPM context: ```sh for i in $(seq 1 70000); do printf 'alert udp any any -> any 9999 (msg:"r%d"; content:"UNIQPATTERN%07d"; fast_pattern; sid:%d; rev:1;)\n' $i $i $i done > big.rules ``` All 70000 contents are 18-byte unique case-sensitive strings. With `sgh-mpm-context: single` they are all added to one `MpmCtx` via `MpmAddPattern()`, where each new unique pattern gets `p->id = mpm_ctx->max_pat_id++` (`util-mpm.c:463`). The 65537th distinct pattern therefore receives internal pid 65536. The 70000 distinct strings also push `state_count` well past 32767, so `SCACPrepareStateTable()` builds the u32 table. 3. Start Suricata with this rules file. The build is memory-heavy but loads; `SCACPreparePatterns()` imposes no 16-bit cap on `max_pat_id`. **Attacker step (network):** 4. Send one UDP datagram to `<sensor-monitored-host>:9999` whose payload is exactly the 18 ASCII bytes of the pattern that received internal pid 65536. Assuming `MpmAddPattern()` is invoked in rule-load order, that is the literal for sid 65537: ``` payload = 55 4e 49 51 50 41 54 54 45 52 4e 30 30 36 35 35 33 37 = "UNIQPATTERN0065537" ``` Full frame: any L2/L3 that Suricata decodes — e.g. Ethernet / IPv4 / UDP dport 9999, UDP payload = the 18 bytes above. **Expected vs. actual:** 5. *Expected:* alert for sid 65537. *Actual:* `SCACSearch()` walks the automaton to the accepting state; `pids[k] = 0x80010000`; L923 computes `lower_pid = 0x80010000 & 0x0000FFFF = 0`; `pid_pat_list[0].cs = "UNIQPATTERN0000001"`; `SCMemcmp("UNIQPATTERN0000001", "UNIQPATTERN0065537", 18) != 0` → `continue`. sid 65537's `sids` never enter `det_ctx->pmq`, `DetectRun()` never evaluates the rule, and no alert is emitted. (Conversely, if the aliased slot's `cs`/`patlen` happened to match the bytes at `buf + offset`, the *wrong* `sids` would be pushed — a false positive.) **Reproduction status:** *Analytical only.* The trigger was not exercised live because the precondition requires building and loading a > 64k-pattern AC context whose u32 state table is multi-GB, which is outside the scope of this static-analysis audit. However, every step in the chain is deterministic source-level arithmetic, and an exhaustive search of the AC code path found no guard that caps `max_pat_id` at 16 bits or otherwise prevents `pid ≥ 65536` from reaching L923. ## Severity **LOW.** The defect causes a deterministic detection bypass — and in edge cases a false-positive cross-fire — for every case-sensitive fast-pattern whose internally assigned pattern-id is ≥ 65536 while the AC matcher is in its u32-state mode. There is no crash and no out-of-bounds read or write: the truncated index is always inside the `calloc`'d `pid_pat_list` (sized `max_pat_id + 1`, L683), negative offsets are filtered at L927, and the upper bound `offset + patlen == i + 1 ≤ buflen` holds for the `SCMemcmp`. Exploitability is gated entirely by operator configuration: the deployment must (a) explicitly select `mpm-algo: ac` (non-default when Hyperscan is available) **and** (b) concentrate > 65536 unique fast-patterns into a single MPM context (e.g. `sgh-mpm-context: single` with an extremely large ruleset). This combination is very uncommon in production. The attacker contributes only a single packet containing a known signature literal. ## Suggested Fix Use the same mask that the construction code (L576–577) and the u16 search branch (L877) already use. One-line patch: ```diff --- a/src/util-mpm-ac.c +++ b/src/util-mpm-ac.c @@ -920,7 +920,7 @@ uint32_t SCACSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx, const uint32_t *pids = ctx->output_table[state & 0x00FFFFFF].pids; for (uint32_t k = 0; k < no_of_entries; k++) { if (pids[k] & AC_CASE_MASK) { - const uint32_t lower_pid = pids[k] & 0x0000FFFF; + const uint32_t lower_pid = pids[k] & AC_PID_MASK; const SCACPatternList *pat = &pid_pat_list[lower_pid]; const int offset = i - pat->patlen + 1; ``` Optionally, add a defensive assertion in `SCACPreparePatterns()` that `mpm_ctx->max_pat_id < AC_CASE_MASK` to document the invariant that the PID never collides with the case-flag bit. </pre>