Understanding ReDoS Attack

ReDoS stands for Regular Expression Denial of Service. The ReDoS is an algorithmic complexity attack that produces a denial of service by providing a regular expression that takes a very long time to evaluate. The attack exploits the fact that most regular expression implementations have exponential time worst case complexity,  so for larger input strings(the ‘evil regex’) the time taken by a regex engine to find a match increases exponentially.

The aim of the attacker is to provide such regex(s) so that it takes indefinite amount of computation time which in turn will either slow down the application or completely bring it down.
So this attack basically takes advantage of the fact that the regex engine will try out every possible permutation and combination of characters to find a match.

Regular expressions can be found all over the web and a ReDoS attack can be used to target various components of the web.

Sample Expression of ReDOS attacks

Regex: ^((ab)*)+$ (this regex searches for ab and its repetition)
Input: ababab
In this case the regex engine will find a match in the first try since ababab matches the regex pattern. Now we can complicate things very easily by throwing in abababa as the input. This exta a in the end will cause all kinds of trouble since it does not match the pattern and it will make the regex engine run all kinds of permutation looking for a possible match.

(ababab) - NOT A MATCH

(abab)(ab) - NOT A MATCH

(ab)(abab) - NOT A MATCH

(ab)(ab)(ab) - NOT A MATCH

()(ababab) - NOT A MATCH

()(abab)(ab) - NOT A MATCH

()(ab)(abab) - NOT A MATCH

()(ab)(ab)(ab) - NOT A MATCH

You can try it out yourself in this online regex editor. Now imagine if that input was longer something like

abababababababababababababababababababababababababab......

what kind of havoc it will create.

Evil Regex

They are the regular expressions that make an application vulnerable to ReDoS attacks, they occur whenever these factors occur:

• the regular expression applies repetition (“+”, “*”) to a complex subexpression
• for the repeated subexpression, there exists a match which is also a suffix of another valid match.

Examples of malicious regexes include the following:

• (a+)+
• ([a-zA-Z]+)*
• (a|aa)+
• (a|a?)+
• (.*a){x} for x > 10

Web application attack via Evil Regex:

• Open a JavaScript and find the Evil Regex
• Craft a malicious input for the found Regex and submit a valid value via intercepting proxy
• Change the request to contain a malicious input and you are ready with a ReDos attack

ReDoS via Regex Injection

The following example checks if the username is part of the password entered by the user.

String userName = textBox1.Text;

String password = textBox2.Text;

Regex testPassword = new Regex(userName);

Match match = testPassword.Match(password);

if (match.Success)

{

MessageBox.Show("Do not include name in password.");

}

else

{

MessageBox.Show("Good password.");

}

If an attacker enters ^(([a-z])+.)+[A-Z]([a-z])+$ as a username and  aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! as a password, the program will hang.

Prevention:

1. Use atomic grouping in your regex. An atomic group is a group that, when the regex engine exits from it, automatically throws away all backtracking positions remembered by any tokens inside the group
2. If a regular expression takes too long, kill it at once, and inform the user that the regular expression was taking too long.
3. Preformat/validate your regular expressions or let people search for text directly, rather than input a regular expression directly.