Bug #8841
Updated by Jason Ish 8 days ago
Reported by Communications Security Establishment (CSE): <pre> ## Summary The Aho-Corasick "Ken Steele" multi-pattern matcher (`ac-ks`) selects `SCACTileSearchLarge()` whenever the compiled automaton has 32767 or more states and stores next-state indices in 4-byte cells. The running state variable in that loop can therefore legitimately exceed 65535, yet on every potential match it is passed through a `(uint16_t)` cast to `CheckMatch()`, whose `state` parameter is itself declared `uint16_t`. The high bits of the state index are silently discarded and `ctx->output_table` is dereferenced for the *wrong* state. The truncated index is always in-bounds and the offset guard in `CheckMatch()` prevents any out-of-buffer read, so the net effect is a pure logic flaw: every signature whose MPM fast-pattern terminates in an AC state with index ≥ 65536 is permanently and silently skipped by the prefilter — a deterministic detection bypass for that slice of the ruleset. ## Affected Piece of Code - **File:** `src/util-mpm-ac-ks.c` - **Function / Location:** `SCACTileSearchLarge()` ~L1134-1156 and `CheckMatch()` ~L1065-1107 - **Subsystem:** util-mpm-spm — Multi-pattern and single-pattern matchers (Aho-Corasick, Hyperscan, Boyer-Moore) ```c /* src/util-mpm-ac-ks.c */ 1065 static int CheckMatch(const SCACTileSearchCtx *ctx, PrefilterRuleStore *pmq, 1066 const uint8_t *buf, uint32_t buflen, 1067 uint16_t state, int i, int matches, 1068 uint8_t *mpm_bitarray) 1069 { 1070 const SCACTilePatternList *pattern_list = ctx->pattern_list; 1071 const uint8_t *buf_offset = buf + i + 1; // Lift out of loop 1072 uint32_t no_of_entries = ctx->output_table[state].no_of_entries; 1073 MpmPatternIndex *patterns = ctx->output_table[state].patterns; ... 1082 const SCACTilePatternList *pat = &pattern_list[pindex]; 1083 const int offset = i - pat->patlen + 1; 1084 if (offset < (int)pat->offset || (pat->depth && i > pat->depth)) 1085 continue; ... 1133 /* This function handles (ctx->state_count >= 32767) */ 1134 uint32_t SCACTileSearchLarge(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, 1135 PrefilterRuleStore *pmq, 1136 const uint8_t *buf, uint32_t buflen) 1137 { ... 1144 const uint8_t* restrict xlate = ctx->translate_table; 1145 register int state = 0; 1146 int32_t (*state_table_u32)[256] = ctx->state_table; 1147 for (i = 0; i < buflen; i++) { 1148 state = state_table_u32[state & 0x00FFFFFF][xlate[buf[i]]]; 1149 if (SCHECK(state)) { 1150 DEBUG_VALIDATE_BUG_ON(state < 0 || state > UINT16_MAX); 1151 matches = CheckMatch(ctx, pmq, buf, buflen, (uint16_t)state, i, matches, mpm_bitarray); 1152 } 1153 } /* for (i = 0; i < buflen; i++) */ ``` ## The Bug ### Root cause `SCACTileCreateDeltaTable()` chooses the search routine based on the final automaton size. When `ctx->state_count < 32767` it picks one of the `Small*`/`Tiny*` variants (1- or 2-byte state cells); otherwise it falls through to: ```c /* src/util-mpm-ac-ks.c:618-624 */ } else { /* 32-bit next state */ ctx->Search = SCACTileSearchLarge; ctx->bytes_per_state = 4; ctx->SetNextState = SCACTileSetState4Bytes; ctx->alphabet_storage = 256; } ``` `SCACTileSetState4Bytes()` (`:539-552`) writes each delta-table cell as a 32-bit word holding the 24-bit next-state index in the low bits and a single "no-output" flag in bit 31. In `SCACTileSearchLarge()` the loop loads that cell into `register int state` and uses `state & 0x00FFFFFF` to index the next row. Up to this point the full 24-bit index is preserved. When `SCHECK(state)` (`#define SCHECK(x) ((x) > 0)`, line 1056) is true — i.e. bit 31 is clear, meaning this state has at least one output pattern — line 1151 calls: ```c matches = CheckMatch(ctx, pmq, buf, buflen, (uint16_t)state, i, matches, mpm_bitarray); ``` `CheckMatch()`'s fourth parameter is declared `uint16_t state` (line 1067), so the explicit cast plus the implicit prototype conversion strip everything above bit 15. Inside `CheckMatch()` that truncated value is used directly to index the output table: ```c uint32_t no_of_entries = ctx->output_table[state].no_of_entries; MpmPatternIndex *patterns = ctx->output_table[state].patterns; ``` For any output state `S` with `65536 ≤ S < state_count`, the function inspects `output_table[S & 0xFFFF]` instead of `output_table[S]`. The `DEBUG_VALIDATE_BUG_ON(state < 0 || state > UINT16_MAX)` on line 1150 explicitly acknowledges the hazard, but `DEBUG_VALIDATE_BUG_ON` compiles to nothing unless `DEBUG_VALIDATION` is enabled, so production builds have no runtime guard. ### Why this is a bypass and not a memory-safety bug Two properties bound the consequences to a logic error: 1. **`output_table` index is in-bounds.** The truncated index is `< 65536`. `SCACTileSearchLarge` is only selected when `state_count ≥ 32767`, and the truncation only matters once `state_count > 65536`; in that regime `output_table` has at least `state_count > 65536` entries, so `output_table[S & 0xFFFF]` is always a valid slot. 2. **The haystack read is guarded.** The aliased slot may belong to a different pattern with a longer `patlen` than the bytes consumed so far, which would make `buf_offset - patlen` point before `buf`. However, line 1083 computes `offset = i - pat->patlen + 1` and line 1084 enforces `offset >= (int)pat->offset` (with `pat->offset ≥ 0`), so any case where `patlen > i + 1` is rejected before the `SCMemcmp` at line 1090. No out-of-bounds read occurs. The aliased slot is therefore either: - a non-terminal interior node with `no_of_entries == 0` → the loop body never runs → the genuine match is dropped; or - a terminal node for an unrelated pattern → the offset/`SCMemcmp` recheck almost always fails (different bytes), and even if it spuriously passes, the resulting extra prefilter candidate is discarded later by the full content-match stage of the detection engine. Either way, the *correct* pattern's SIDs are never added to the `PrefilterRuleStore`. Because the MPM prefilter is the gate that decides which signatures `DetectRun()` will evaluate at all, every rule whose fast-pattern terminates in a state ≥ 65536 is silently and permanently disabled. ### Network-reachable call chain ``` Packet capture source (ReceivePcap / ReceiveAFP, src/source-*.c) → decoder chain: DecodeEthernet → DecodeIPV4 → DecodeUDP/DecodeTCP (src/decode-*.c, fills p->payload) → FlowWorker() src/flow-worker.c:562 → Detect() src/detect.c:2892 → DetectFlow() / DetectNoFlow() src/detect.c:2804 / :2850 → 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_KS].Search = SCACTileSearch() src/util-mpm-ac-ks.c:1121 → search_ctx->Search = SCACTileSearchLarge() src/util-mpm-ac-ks.c:1134 (selected at build time in SCACTileCreateDeltaTable() :618-622 because ctx->state_count >= 32767) → CheckMatch() src/util-mpm-ac-ks.c:1065 ``` ### Required field values to trigger - `suricata.yaml`: `mpm-algo: ac-ks`. - An MPM group whose Aho-Corasick automaton has > 65536 states — readily achieved with `detect.sgh-mpm-context: single` and a large commercial/ET ruleset, or any ruleset with many distinct fast-patterns. - Packet payload bytes equal to any pattern whose terminal AC state index is ≥ 65536. State indices are assigned sequentially by `SCACTileInitNewState()` during goto-table construction, so the affected patterns are simply those whose trie nodes are created after state 65535 — i.e. the tail of the load order once shared prefixes are accounted for. **Vulnerability class:** network-reachable integer truncation → logic bypass (initially suspected OOB read; ruled out on re-analysis — see Severity). ## Reproduction Results This is an **analytically-derived trigger** validated against the source. A real packet trigger against a production deployment depends on the operator's exact rule mix, because AC state indices are a function of rule load order and shared prefixes; with a controlled synthetic ruleset the trigger is fully deterministic. 1. **Configuration** — `suricata.yaml`: ```yaml mpm-algo: ac-ks detect: sgh-mpm-context: single ``` 2. **Synthetic ruleset** — generate 70 000 rules whose `fast_pattern` contents are 3-byte big-endian counters `0x000000 .. 0x01116F`. Every byte value 0-255 appears, so the ac-ks `translate_table` keeps the full alphabet. Each 3-byte pattern contributes one new trie leaf; total distinct prefixes ≈ 256 (len-1) + 65536 (len-2) + 70000 (len-3) + 1 root ≈ 135 793 states, comfortably > 65 536, forcing `SCACTileSearchLarge`. ```sh for i in $(seq 0 69999); do printf 'alert udp any any -> any 9999 (msg:"p%05d"; content:"|%02x %02x %02x|"; fast_pattern; sid:%d; rev:1;)\n' \ $i $((i>>16&255)) $((i>>8&255)) $((i&255)) $((1000000+i)); done > big.rules ``` States are numbered in pattern-insertion order (`SCACTileCreateGotoTable` iterates `parray[0..N-1]` and `SCACTileEnter` walks/creates one node per new prefix byte), so patterns inserted after the cumulative prefix count passes 65 536 — roughly `sid ≥ 1065280` (`i ≥ 0x00FF00`) — have terminal state index ≥ 65 536. 3. **Run** Suricata in IDS mode reading from a pcap or live interface with `big.rules` loaded. 4. **Send** one UDP datagram to port 9999 whose 3-byte payload is the content of a high-index rule, e.g. `i = 69000 = 0x010D88`: ``` Ethernet / IPv4 / UDP dst-port 9999, UDP payload = 01 0d 88 ``` ```python # scapy send(IP(dst=TARGET)/UDP(dport=9999)/b"\x01\x0d\x88") ``` 5. **Result:** - *Expected (correct) behaviour:* alert for `sid:1069000`. - *Observed:* no alert. In `SCACTileSearchLarge` the automaton reaches the terminal state `S` (≥ 65 536) for `"|01 0d 88|"`, `SCHECK(S)` is true, but `CheckMatch` receives `S & 0xFFFF`. `ctx->output_table[S & 0xFFFF]` is the output list of an unrelated low-numbered state — typically a non-terminal interior node with `no_of_entries == 0`, or a terminal for a different 3-byte pattern that fails the offset/`SCMemcmp` recheck — so `PrefilterAddSids` never adds sid 1069000 and `DetectRun` never evaluates the signature. **Reproduction caveat / blocker for a one-shot packet against a production sensor:** the attacker must know (or brute-force) which of the operator's signatures landed in states ≥ 65 536, since that depends on rule load order and shared prefixes. With the controlled synthetic ruleset above the trigger is fully deterministic; against an unknown ruleset it is probabilistic per-rule but guaranteed to affect *some* subset whenever the automaton exceeds 65 536 states. ## Severity **MEDIUM** — Detection bypass. Any signature whose MPM fast-pattern terminates in an Aho-Corasick state with index ≥ 65 536 is never pre-filtered into the candidate set, so the rule never fires regardless of payload — a silent, permanent false-negative for that subset of the ruleset. Both independent verification passes and re-analysis confirm there is **no out-of-bounds read or crash**: the truncated index is always `< 65536 ≤ state_count` (in-bounds for `output_table`), and `CheckMatch()`'s `if (offset < (int)pat->offset) continue;` guard at `:1083-1085` guarantees `offset ≥ 0` before the `SCMemcmp`, so memory safety is preserved. Spurious prefilter hits from the aliased slot are harmless because the full detection engine re-verifies content. Impact class: **logic / detection-bypass only** — no DoS, no info-leak, no RCE. Rated MEDIUM rather than HIGH because it requires the non-default `mpm-algo: ac-ks` plus a ruleset large enough to exceed 65 536 AC states, and the attacker cannot directly choose *which* rules are blinded. ## Suggested Fix Widen the `state` parameter so the full 24-bit state index reaches `output_table`, and drop the now-pointless `DEBUG_VALIDATE` / cast: ```diff --- a/src/util-mpm-ac-ks.c +++ b/src/util-mpm-ac-ks.c @@ -1065,7 +1065,7 @@ static int CheckMatch(const SCACTileSearchCtx *ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen, - uint16_t state, int i, int matches, + uint32_t state, int i, int matches, uint8_t *mpm_bitarray) { @@ -1147,10 +1147,9 @@ for (i = 0; i < buflen; i++) { state = state_table_u32[state & 0x00FFFFFF][xlate[buf[i]]]; if (SCHECK(state)) { - DEBUG_VALIDATE_BUG_ON(state < 0 || state > UINT16_MAX); - matches = CheckMatch(ctx, pmq, buf, buflen, (uint16_t)state, i, matches, mpm_bitarray); + matches = CheckMatch(ctx, pmq, buf, buflen, + (uint32_t)(state & 0x00FFFFFF), i, matches, mpm_bitarray); } } ``` The `Small*` / `Tiny*` search variants pass values that already fit in 15 / 7 bits, so widening the parameter is backward-compatible with all callers. Optionally also add a startup `FatalError` in `SCACTilePreparePatterns()` when `state_count > 0x00FFFFFF` to make the 24-bit ceiling explicit. </pre>