mandiant / mandiant/capa-rules

[encrypt data using RC4 PRGA] False positive on string validators

Open
#1,193 0 comments 0 reactions 0 assignees View on GitHub
false positive
Dominant language
No language data
Stars
736
Forks
245
Avg merge
4d 53m
Merged PRs (30d)
2

Description

## Summary

`encrypt data using RC4 PRGA` matches on code that has the same coarse shape as RC4 PRGA (loop, one incidental xor, a loose mod-256 arithmetic signal, few calls) without being RC4. No S-box, no permutation, no swap. Found on a wide-char string validator, then confirmed more broadly on hash/PRNG mixers, fixed-table substitution ciphers, and a couple of misidentified jump tables in optimized binaries.

## Examples

**Sample:** `x64\vulkan-1.dll` from the official [VulkanRT-X64-1.4.350.0-Components.zip](https://sdk.lunarg.com/sdk/download/1.4.350.0/windows/VulkanRT-X64-1.4.350.0-Components.zip) (LunarG Vulkan SDK).

- SHA256: `0419974f00e82a3d619077ba414da265a774f8db9d45ad93bc1843f44b2c2c1f`
- MD5: `8317b31612b11fcb4ca7e04f6e93efa5`

capa matches function `0x1800CB61C` as RC4 PRGA. It's a case-insensitive string validator: reads one wide char at a time from a stream, compares against strings, returns an error code on mismatch. No crypto: the single nzxor is `(errcode & 0xff) ^ 1` in the error path.

Minimal reproducer (`rc4_fp.c`) and repro steps below.

## Possible improvements

```diff
--- a/data-manipulation/encryption/rc4/encrypt-data-using-rc4-prga.yml
+++ b/data-manipulation/encryption/rc4/encrypt-data-using-rc4-prga.yml
@@ -22,10 +22,14 @@ rule:
# TODO: maybe add characteristic for nzxor reg size
- count(characteristic(nzxor)): 1
- or:
- - match: calculate modulo 256 via x86 assembly
- # compiler may do this via zero-extended mov from 8-bit register
- - count(mnemonic(movzx)): 4 or more
+ # PRGA masks BOTH the i-index and the j-accumulator mod 256 each
+ # iteration (i=(i+1)&0xff; j=(j+S[i])&0xff), so a genuine PRGA body
+ # hits this idiom at least twice per loop.
+ - count(match(calculate modulo 256 via x86 assembly)): 2 or more
+ # compiler may do this via zero-extended mov from 8-bit register.
+ # Raised from 4 to 6 to stop ordinary narrow-char parsers from
+ # satisfying this fallback alone.
+ - count(mnemonic(movzx)): 6 or more
# should not call (many) functions
- count(characteristic(calls from)): (0, 4)
# should not be too simple or too complex (50 is picked by intuition)
```

Root cause: the mod-256 (`and reg,0xff`) only had to appear once, and the `movzx` fallback triggered at 4, low enough that a plain narrow-char parsing loop satisfies it. Genuine PRGA masks both the `i` index and `j` accumulator mod 256 per iteration, so require that idiom twice, and raise the `movzx` fallback to 6.

Commit made on fork: [BinTriage/capa-rules@4ba9d4d](https://github.com/BinTriage/capa-rules/commit/4ba9d4dd3d59db6243e5e3dea82fed0ee4999395) (branch `fix/rc4-prga-fp`)

### Testing

Ran `scripts/lint.py --thorough` against the 4 samples in the rule's `meta.examples` (from [capa-testfiles](https://github.com/mandiant/capa-testfiles)). All 4 still match:

```
capa-src/.lintvenv/bin/python capa-src/scripts/lint.py --thorough \
-t "encrypt data using RC4 PRGA" -v --samples capa-testfiles capa-rules-new
# -> "no lints failed, nice!"
```

### Extended benchmark

Went further and manually classified every `encrypt data using RC4 PRGA` match the original unmodified rule produces across capa-testfiles: 56 matches across 298 files that scanned cleanly (63 timed out, excluded).

By my count, the original rule lands around 52% false positives on this corpus (29/56 matches are not RC4: no S-box, no swap, nothing cryptographic). Two files account for 10 of those 29: a custom multiply-based hash/PRNG mixer and an obfuscated junk-constant chaff routine, both hitting every clause by coincidence.

Original vs. fixed rule:

- 0 new false positives (expected, the fix only tightens).
- 14 of the 56 original matches dropped. Disassembled all 14: 11 correct exclusions, 3 real regressions (genuine RC4 no longer matching): `021f49678cd633dc8cf99c61b3af3dda.exe_@0x40ff6a`, `2d3edc218a90f03089cc01715a9f047f.exe_@0x401079`, `44d40faf3f1fe4ed969befab7afcd2f0.exe_@0x1002c390`. True recall cost: 3/45 real matches ≈ 6.7%, not the raw 25% the drop count suggests.
- Net: 42 matches remain, 18 of those look like false positives to me, barely moved from before. The two repeat-offender files are unaffected; they still generate enough movzx/and instructions to pass either way.

**Caveats:**

- "Masks mod-256 twice" doesn't universally hold: 5 of the 26 confirmed-genuine matches have an `and reg,0xff` count of 0 or 1 (compiler does the wrap via 8-bit sub-register truncation instead). Those only survive via the `movzx >= 6` fallback.
- The rule's own `# TODO: maybe add characteristic for nzxor reg size` is the real gap.

## Additional context

Reproducer source (`rc4_fp.c`):

```c
#include
#include

typedef uint16_t WCHAR;

static const WCHAR GOOD1[] = { 'U','N','I','T','Y' };
static const WCHAR GOOD2[] = { 'i','n','i','t','y' };

int validate(FILE *stream, WCHAR *out) {
int i;
int c;
WCHAR wc;

for (i = 0; i < 5; i++) {
c = fgetc(stream);
wc = (WCHAR)c;
if (wc != GOOD1[i] && wc != GOOD2[i]) {
return ((unsigned)c & 0xff ^ 1) * 4 + 3; /* single nzxor, matches original error path */
}
out[i] = wc;
}
return 3;
}

int main(void) {
FILE *f = fopen("input.txt", "r");
if (!f) return 1;
WCHAR buf[5];
int r = validate(f, buf);
fclose(f);
printf("%d\n", r);
return 0;
}
```

Build: `gcc -O0 -o rc4_fp rc4_fp.c`

Reproduce the FP against unmodified capa-rules, confirm the fix:

```
capa -r capa-rules -j rc4_fp | python3 -c "import json,sys; d=json.load(sys.stdin); print('encrypt data using RC4 PRGA' in d['rules'])"
# -> True (false positive, unmodified rule)

capa -r capa-rules-new -j rc4_fp | python3 -c "import json,sys; d=json.load(sys.stdin); print('encrypt data using RC4 PRGA' in d['rules'])"
# -> False (fixed)
```

Contributor guide

Open the contributing guide

Research direction

Start with data-manipulation/encryption/rc4/encrypt-data-using-rc4-prga.yml and reproduce the reported match with rc4_fp.c using the two capa commands. Run scripts/lint.py --thorough against the rule's meta.examples, then compare the benchmark results; done means the validator no longer matches while the listed RC4 samples remain covered and any recall regressions are understood.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, python, yaml
Domain
reverse-engineering, security, testing-qa
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.