Suricata

Reported by Communications Security Establishment (CSE):

## 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.