Regex Denial of Service (ReDoS)

TL;DR

Yes, a regex without special characters like [(+*{}? can still be dangerous and cause a Denial of Service (ReDoS) attack. This happens when the regex takes an extremely long time to complete due to backtracking with certain inputs.

What is ReDoS?

ReDoS occurs when a carefully crafted input string causes a regular expression engine to take an exponentially long time to process, potentially freezing your application or server. It’s a type of resource exhaustion attack.

How can simple regexes be vulnerable?

The problem isn’t the presence of special characters; it’s how the regex is structured and interacts with the input. Even seemingly harmless patterns can become problematic if they lead to excessive backtracking.

Example Vulnerable Regex

Consider this simple regex:

.*a.*

This looks innocent, matching any character (.) zero or more times (*), followed by ‘a’, then any character zero or more times again.

How it can cause ReDoS

1. Backtracking: When the regex engine tries to match this against a long string without an ‘a’, it will try every possible combination of characters before failing.
2. Exponential Time: The more characters in the input string without an ‘a’, the longer it takes because the engine has to backtrack and explore many possibilities.

For example, matching against a 100-character string of ‘b’s will take much longer than matching against ‘ba’.

Steps to Prevent ReDoS

1. Limit Input Length: The simplest and most effective defense. Restrict the maximum length of strings that your regex processes.
2. Timeouts: Most regex engines allow you to set a timeout for matching operations. If the regex takes too long, it will be aborted.
   • Python: Use the timeout parameter in re.search() or re.match() (requires Python 3.7+).

   import re
   
   try:
     match = re.search(".*a.*", input_string, timeout=0.1) # Timeout after 0.1 seconds
   except TimeoutError:
     print("Regex timed out!")

   • JavaScript: JavaScript doesn’t have built-in regex timeouts directly. You can use a workaround with setTimeout() and asynchronous execution, but it’s complex.
3. Simplify Regexes: Avoid overly complex patterns that could lead to excessive backtracking. Break down complex expressions into simpler ones if possible.
4. Use Atomic Grouping (if supported): Some regex engines support atomic grouping, which prevents backtracking within the group.

   (?:.*a.*)

5. Test with Vulnerable Inputs: Use tools and techniques to test your regexes against strings designed to trigger ReDoS. There are online ReDoS testing services available.
6. Consider Alternatives: If possible, avoid using regular expressions altogether for tasks where they aren’t essential. String manipulation functions might be faster and more predictable.

Tools for Testing

• Regex101: https://regex101.com (can help visualize backtracking)
• ReDoS Attack website: https://redos-attack.net/ (specifically for testing ReDoS vulnerabilities)