regexploit: Find regular expressions which are vulnerable to ReDoS

Regexploit

Find regexes which are vulnerable to Regular Expression Denial of Service (ReDoS).

Many default regular expression parsers have unbounded worst-case complexity. Regex matching may be quick when presented with a matching input string. However, certain non-matching input strings can make the regular expression matcher go into crazy backtracking loops and take ages to process. This can cause a denial of service, as the CPU will be stuck trying to match the regex.

This tool is designed to:

• find regular expressions which are vulnerable to ReDoS
• give an example malicious string which will cause catastrophic backtracking

Worst-case complexity

This reflects the complexity of the regular expression matcher’s backtracking procedure with respect to the length of the entered string.

Cubic complexity here means that if the vulnerable part of the string is doubled in length, the execution time should be about 8 times longer (2^3). For exponential ReDoS with starred stars e.g. (a*)*$ a fudge factor is used and the complexity will be greater than 10.

For exploitability, cubic complexity or higher is typically required unless truly giant strings are allowed as input.

Example

Run regexploit and enter the regular expression v\w*_\w*_\w*$ at the command line.

$ regexploit

v\w*_\w*_\w*$

Pattern: v\w*_\w*_\w*$

---

Worst-case complexity: 3 ⭐⭐⭐ (cubic)

Repeated character: [5f:_]

Final character to cause backtracking: [^WORD]

Example: 'v' + '_' * 3456 + '!'

The part \w*_\w*_\w* contains three overlapping repeating groups (\w matches letters, digits, and underscores). As shown in the line Repeated character: [5f:_], a long string of _ (0x5f) will match this section in many different ways. The worst-case complexity is 3 as there are 3 infinitely repeating groups. An example to cause ReDoS is given: it consists of the required prefix v, a long string of _, and then a ! (non-word character) to cause backtracking. Not all ReDoSes require a particular character at the end, but in this case, a long string of _ will match the regex successfully and won’t backtrack. The line Final character to cause backtracking: [^WORD] shows that a non-matching character (not a word character) is required at the end to prevent matching and cause ReDoS.

As another example, install a module version vulnerable to ReDoS such as pip install ua-parser==0.9.0. To scan the installed python modules run regexploit-python-env.

Importing ua_parser.user_agent_parser

Vulnerable regex in /somewhere/.env/lib/python3.9/site-packages/ua_parser/user_agent_parser.py #183

Pattern: \bSmartWatch *\( *([^;]+) *; *([^;]+) *;

Context: self.user_agent_re = re.compile(self.pattern)

---

Worst-case complexity: 3 ⭐⭐⭐

Repeated character: [20]

Example: 'SmartWatch(' + ' ' * 3456



Worst-case complexity: 3 ⭐⭐⭐

Repeated character: [20]

Example: 'SmartWatch(0;' + ' ' * 3456



Vulnerable regex in /somewhere/.env/lib/python3.9/site-packages/ua_parser/user_agent_parser.py #183

Pattern: ; *([^;/]+) Build[/ ]Huawei(MT1-U06|[A-Z]+\d+[^\);]+)[^\);]*\)

Context: self.user_agent_re = re.compile(self.pattern)

---

Worst-case complexity: 3 ⭐⭐⭐

Repeated character: [[0-9]]

Example: ';0 Build/HuaweiA' + '0' * 3456

...

For each vulnerable regular expression, it prints one or more malicious strings to trigger ReDoS. Setting your user agent to ;0 Build/HuaweiA000000000000000… and browsing a website using an old version of ua-parser may cause the server to take a long time to process your request, probably ending in status 502.

Install & Use

Copyright 2020 Doyensec LLC.