As I'm preparing to give a talk on automated regular expression denial of service methods and defenses at DefCon 23 this week, I beefed up part of 8ball (a tool demonstrated at DefCon 22 last year) to be able to incorporate RE:DoS.
8ball is a script that parses a txt file list of snort/suricata rules and makes a corresponding packet for each rule (of which it sends at a target host). The piece of this script that just got updated was the pcre parser. This part of the script analyzes the pcre string of the IDS rule and crafts a string that it knows would match it (automated). with the -l option (aka the speedball option) the string is crafted in such a way as to take the longest time for a (NFA) regular expression engine to evaluate.
Another side effect of this technique is that the string will actually fail to match the expression. Think back to when you learned 'short-circuiting' in a programming language:
if (a or b or c) {
print "all of them\n";
}
If 'a' is true, why even evaluate b and c? compilers create code that don't; it's faster this way. As a bastardized analogy, the speedball option makes a and b true, but not c. They all have to be evaluated. 'c' is false..because backtracking, yeah, that's where the analogy falls apart, it's a regex thing.
Let's now look at an example, an IDS rule:
alert tcp $EXTERNAL_NET any -> $HTTP_SERVERS $HTTP_PORTS (msg:"ET WEB_SERVER Coldfusion cfcexplorer Directory Traversal"; flow:established,to_server; content:"/cfcexplorer.cfc"; nocase; http_uri; fast_pattern:only; content:"path="; nocase; pcre:"/^[^&]*?(?:%(?:25)?2e(?:%(?:(?:25)?2e(?:%(?:25)?5c|\/|\\)|2e(?:25)?%(?:25)?2f)|\.(?:%(?:25)?(?:2f|5c)|\/|\\))|\.(?:%(?:25)?2e(?:%(?:25)?(?:2f|5c)|\/|\\)|\.(?:%(?:25)?(?:2f|5c)|\/|\\)))/Ri"; reference:url,blog.spiderlabs.com/2013/12/the-curious-case-of-the-malicious-iis-module-prologue-method-of-entry-analysis.html; classtype:attempted-user; sid:2017875; rev:1;)
There is one pcre up there: ^[^&]*?(?:%(?:25)?2e(?:%(?:(?:25)?2e(?:%(?:25)?5c|\/|\\)|2e(?:25)?%(?:25)?2f)|\.(?:%(?:25)?(?:2f|5c)|\/|\\))|\.(?:%(?:25)?2e(?:%(?:25)?(?:2f|5c)|\/|\\)|\.(?:%(?:25)?(?:2f|5c)|\/|\\)))
the default engine will create this string:
^%252e%252e%255c|/|\)|2e25%252f|.%252f|5c|/|\)|.%252e%252f|5c|/|\)|.%252f|5c|/|\)
The speedball option creates:
^]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]2e.5c|/|\)|.5c|/|\)|.%25@
The first string matches. The 2nd string, does not match, and even though it is smaller, it takes twice as long to evaluate. That's childs-play compared to how bad this can get. If you happen to be at DefCon this week and want gratuitous RE:DoS details, come check out my talk "REvisiting RE:DoS" at 3pm on Friday: Link to Abstract
While you're at it, some other talks to check out:
David Huertas Crypto talk: Link to Talk Abstract
Trammel's talk on MAC firmware attacks (Another NYC Resistor regular): Link to Talk Abstract
And ALTF4's Safe Robbing talk (of PHX2600 and HeatSyncLabs): Link to Talk Abstract