Overview Link to heading

Regex are powerful tools for pattern matching and text manipulation. They allow developers to define search patterns using a combination of characters, metacharacters, and quantifiers. However, certain patterns can be susceptible to exponential-time matching behavior.

In the context of ReDoS, an attacker can exploit this behavior by providing input that triggers worst-case scenarios for the regex engine. This often involves crafting a pattern that requires a significant amount of backtracking to evaluate.

Backtracking occurs when the regex engine attempts to match a pattern but encounters a contradiction or failure along the way. It then goes back and explores alternative paths in an attempt to find a match. If the pattern is designed in such a way that there are multiple ambiguous possibilities, the engine may need to explore an exponential number of paths, leading to a significant increase in evaluation time.

As a result, an attacker can construct input strings that cause the regex engine to take an excessive amount of time to complete matching. This can consume a disproportionate amount of CPU resources, memory, or even crash the system in extreme cases.

Demo Link to heading

The following server.js code uses regex to check if password contains username. It’s potential ReDoS vulnerability

const http = require('http');

const server = http.createServer((req, res) => {
  if (req.method === 'POST') {
    let body = '';

    req.on('data', chunk => {
      body += chunk.toString();
    });

    req.on('end', () => {
      const { username, password } = JSON.parse(body);

      // Potential ReDoS vulnerability: checking if password contains username
      const regex = new RegExp(username, 'i');
      const isPasswordInvalid = regex.test(password);

      if (isPasswordInvalid) {
        res.writeHead(400, { 'Content-Type': 'text/plain' });
        res.end('Password is containing username');
      } else {
        res.writeHead(200, { 'Content-Type': 'text/plain' });
        res.end('Password is OK');
      }
    });
  } else {
    res.writeHead(404, { 'Content-Type': 'text/plain' });
    res.end('Not Found');
  }
});

const port = 3000;
server.listen(port, () => {
  console.log(`Server listening on port ${port}`);
});

Run the server in the terminal

$ node server.js
Server listening on port 3000

Open another terminal, send a legit POST request to confirm the server is working properly

$ curl http://localhost:3000 -d '{"username": "admin", "password": "ok"}'
Password is OK

$ curl http://localhost:3000 -d '{"username": "admin", "password": "admin"}'
Password is containing username

Send another POST request containing an evil regex. The server will be hang and will not response to any other legit requests

$ curl http://localhost:3000 -d '{"username": "^(\\w+)+$", "password": "f582707b490428aa26c91cd61ec049f0f2f82bfc68a080c776ba21e12c71feb4!"}'

Prevent ReDoS Link to heading

Developers can mitigate ReDoS vulnerabilities by following best practices such as:

1. Avoiding complex and ambiguous regex patterns that may lead to excessive backtracking.
2. Limiting the input length and complexity that the regex needs to process.
3. Employing techniques like setting a timeout for regex evaluation.
4. Using alternative algorithms or libraries specifically designed to handle regex-es efficiently and securely.

Reference: Attacking Evil Regex: Understanding Regular Expression Denial of Service Attacks (ReDoS)