XlogicX Blog

8ball_can_now_speedball

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