validate payment card number using luhn algorithm with no lookup table: doesn't match against notepad.exe

[erhlee-bird]

Summary

Rule Name: "validate payment card number using luhn algorithm with no lookup table"

The aforementioned rule doesn't match against a version of notepad.exe (sha256:d66458a3eb1b68715b552b3af32a9d2e889bbf8ac0c23c1afa8d0982023d1ce2).

I don't think the file is actually exhibiting the represented behavior but the rule seems like it should match from how the rule is written.

Examples

notepad.exe (sha256:d66458a3eb1b68715b552b3af32a9d2e889bbf8ac0c23c1afa8d0982023d1ce2) Function located at 14000a098

1. There's a loop at 14000ac6d satisfying the loop characteristic requirement

2. There is a basic block at 14000a8e2 that satisfies the next inline basic block rule "Digital Root check number*2 < 0x9"

• mnemonic add @ 14000a945
• mnemonic cmp @ 14000a922
• number 9 @ 14000a8ed

3. There is a basic block at 14000aa76 that satisfies the next inline basic block rule "Conversion of chr to int (LEA REG,[REG+ -0x30])"

• mnemonic lea @ 14000aa7e
• offset -0x30 @ 14000aa7e

4. There is a basic block at 14000ad3c that satisfies the last inline basic block rule "Final section returning checkum % 10"

• mnemonic div @ 14000ad41
• number 10 @ 14000ad43

Possible improvements

As a false negative, I think the rule should match according to the specified rule features.

So if this rule did match, I think it would actually be a false positive as a result of the basic block scope being very wide.

If the "Final section returning checkum % 10" rule were at like an instruction scope to look for specifically div 10 or something along those lines, this probably wouldn't match.

Additional context

[mr-tz]

Thanks for the detailed report! I'll have to take a deeper look at this.

And instruction scope or feature (https://github.com/mandiant/capa/issues/767) would help for sure with various FPs.

[re-fox]

Just a contextual comment: One of the issues I encountered when writing this signature is just the sheer amount of variations encountered of this algorithm. Fortunately, most implementations have the same features (Digit summing, lookup tables).

I roughly documented variants of the algorithm that this rule was written against -> https://github.com/re-fox/documentation/blob/master/algorithms/luhns.md. While I don't think all of those are in capa-testfiles, they may help give some samples to regression test against.

With this said, adding the instruction scope would help in reducing FP's, especially when dealing with samples where the basic blocks contain a lot of arithmetic or are overly large.

[mr-tz]

We've since added the instruction scope and improved the rule accordingly.

2., 3. and 4. now do not hit anymore, so the function should not and does not match :)