Jul 01, 2020 09:20:00

What is a 'ReDoS attack' that targets regular expressions used from apps to firewalls?

Among

DoS attacks that intentionally load servers and networks and cause service failures, an attack that uses a vulnerability in regular expression pattern processing is called a ReDoS attack, and StackOverflow and Cloudflare have also been targeted. .. James Davis , a professor of electrical and computer engineering at Purdue University , talks about the typical regular expressions that cause ReDoS attacks and what to do about them.

The Regular Expression Denial of Service (ReDoS) cheat-sheet
https://levelup.gitconnected.com/the-regular-expression-denial-of-service-redos-cheat-sheet-a78d0ed7d865

Regular expression is a method of expressing several character strings as a pattern with one character string. Implemented in most programming languages, the programming language uses a regular expression engine to evaluate whether a string matches a regular expression pattern, Davis explains.

The attack that uses the processing of such regular expressions is the ReDoS attack, which is an attack that takes the computational resources of the server by inputting a character string that requires time for the regular expression pattern evaluation. Regular expressions are used everywhere, from client-side applications to firewalls and databases, so ReDoS attacks can be said to have a wide scope.

Davis uses the regular expression '(a|a)(b|b)c' as an example to explain the mechanism by which the regular expression engine takes a long time to process. '(A|a)(b|b)c' is a regular expression in which multiple ORs are used and the evaluation path is divided into multiple parts.

When evaluating a character string that does not match the above regular expression, the following processing is performed by the regular expression engine.

1: The regular expression engine starts from the left point and reaches the branch. The regex engine thinks it will match an 'a' in either the upper or lower route and will evaluate one route for the moment and move on.
2: This time you reach the 'b' branch. Think of it as matching 'b' on either the top or bottom route, evaluate one route and move on.
3: Reached 'c' but did not match the pattern. The regular expression engine goes back to branch 'b' again.
4: First evaluated the route that was not evaluated in the branch of 'b', and reached 'c' again. It does not match the pattern, so it returns to branch 'a'.
5: First evaluate the route that was not evaluated at the 'a' branch, and reach the 'b' branch. The canonical rating engine again evaluates the two paths of'b'. In other words, repeat steps 2 to 4 again.
6: Finally, the canonical evaluation engine goes through four different routes, evaluates the same 'c' four times, and finishes the process.

Davis points out that the basic rule of thumb for avoiding regular expressions that cause ReDoS attacks is 'eliminate ambiguity' because there are redundant parts in the evaluation of regular expression engines. The ambiguity of regular expressions is generally attributed to the logical sum expressed by '|' and the quantifiers such as '*' and '+'.

How to use quantifiers is also important. For example, when comparing '(a|a)' and '(a|a)*', the number of branches processed by the regular expression engine is '(a|a)*'.

In order to avoid ambiguity by avoiding regular expressions used in ReDoS attacks, Davis said that there are points to be suppressed as follows.

・Avoid putting a quantifier inside a quantifier such as '(a*)*'
・Avoid putting patterns of disjunctions in quantifiers such as '(a|a)*'
・Avoid concatenating quantifiers such as 'abc.*def.*'

Also, if you use a regular expression that causes a ReDoS attack, you can handle it on the software side so that it will not lead to a failure. One of the methods is 'validate the string in advance'. For example, you can test the length of a string before it is evaluated by the regular expression engine to eliminate strings that take a long time to evaluate. However, it may also remove valid input, and Davis says he doesn't trust the method of pre-validating strings.

You can also avoid ReDoS attacks by using a fast regular expression engine such as RE2 . However, it is said that such a high-speed regular evaluation engine does not support advanced functions such as back reference, or its behavior may be slightly different.

If you are developing with C#/.NET, you can deal with ReDoS attacks by setting a timeout for the evaluation time of the regular expression engine, Davis said.