Regular expression Denial of Service - ReDoS

👉 Overview

👀 What ?

Regular Expression Denial of Service (ReDoS) is a form of Denial of Service (DoS) attack that targets the efficiency of regular expression (regex) processing in a software system. A regex is a sequence of characters that defines a search pattern, typically employed in pattern matching with strings, or string-matching operations such as 'find' or 'replace'.

🧐 Why ?

ReDoS is important to understand because it is a resource exhaustion attack that can cause a targeted system to become unresponsive or unavailable by forcing it to commit nearly all of its resources to processing excessively complex regexes. This can result in a significant impact on the availability and reliability of the system, making it a critical concern for anyone responsible for maintaining the security of software applications.

⛏️ How ?

Implementing ReDoS involves crafting a malicious regular expression that takes a long time to evaluate. This is typically done by creating a regex that has a high degree of ambiguity, forcing the regex engine to spend an excessive amount of time attempting to evaluate all possible matches. This exploit can be mitigated by limiting the complexity of regexes allowed in the system, or by utilizing a regex engine that is designed to handle potentially malicious regexes efficiently.

⏳ When ?

The awareness and practice of ReDoS has increased with the prevalence of web applications and APIs that frequently use regular expressions for input validation and data sanitization. As such, it is more relevant than ever for developers and security practitioners to understand and mitigate against this type of attack.

⚙️ Technical Explanations

At its core, ReDoS is a computational complexity attack that leverages the potential inefficiency of some regular expression engines in software languages like JavaScript, Perl, and others. The vulnerability lies in the use of 'evil' regexes, a term coined by the software community to refer to regexes that can potentially cause catastrophic backtracking. Catastrophic backtracking occurs when the regex engine has to backtrack a large number of times to evaluate the regex, potentially leading to very long processing times. A classic example of an 'evil' regex is (a+)+. When this regex is used against a string of 'a's followed by a single non-matching character, it forces the regex engine to evaluate an exponential number of matches, effectively causing a DoS condition.