mandiant / mandiant/capa-rules
[encrypt data using RC4 PRGA] False positive on string validators
- 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
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