Redos Pentest

ReDoS Pentesting Skill

A skill for identifying, testing, and exploiting Regular Expression Denial of Service (ReDoS) vulnerabilities in applications and codebases.

What is ReDoS?

Regular Expression Denial of Service (ReDoS) occurs when crafted input causes a regex engine to perform catastrophic backtracking, consuming excessive CPU time and potentially freezing or crashing the application. This happens when:

• The regex contains nested or overlapping quantifiers (e.g., (a+)+, (.*a){100})
• The input creates many ambiguous matching paths
• The engine must backtrack through exponential possibilities before failing

When to Use This Skill

Use this skill when:

• You need to audit regex patterns for security vulnerabilities
• You're testing a web application for ReDoS susceptibility
• You're working on a CTF challenge involving regex injection
• You need to generate ReDoS payloads for penetration testing
• You want to measure the severity of a suspected ReDoS vulnerability
• You're reviewing code that processes user input with regex

Identifying Vulnerable Patterns

Classic Evil Regex Patterns

These patterns are commonly vulnerable to ReDoS:

Red Flags to Look For

1. Nested quantifiers: (a+)+, ((.*)*)*
2. Quantified groups with quantifiers inside: ([a-z]+)*
3. Alternation with overlap: (a|aa)+, (a|a?)+
4. Large repetition counts: (.*a){100}
5. Multiple quantifiers in sequence: \w*_*\w*$

Testing for ReDoS

Step 1: Generate Test Payloads

Use the timing harness script to test if a pattern is vulnerable:

python scripts/redos_timing_test.py "(a+)+$" "aaaaaaaaaaaaaaaaaaaaaaaa!"

Or test with increasing input lengths to observe exponential growth:

python scripts/redos_timing_test.py "(\w*_)*\w*$" --lengths 8 10 12 14 16 18 20

Step 2: Analyze Results

• Safe: Linear or constant time growth
• Vulnerable: Exponential or high-polynomial growth (time doubles or more with small input increases)
• Critical: Pattern freezes or times out with moderate input (50+ characters)

Step 3: Verify with Tools

Use automated tools to scan codebases:

# Install regexploit
pip install regexploit

# Scan Python code
regexploit-py /path/to/code/

# Scan JavaScript code
regexploit-js /path/to/code/

# Interactive analysis
regexploit

ReDoS Payload Generation

When You Control Both Input and Regex

Use these generic payloads to test vulnerable patterns:

// Test payloads
const payloads = [
  "(a|a?)+$",
  "(\\w*)+$",
  "(a*)+$",
  "(.*a){100}$",
  "([a-zA-Z]+)*$",
  "(a+)*$"
];

// Test input
const testInput = "aaaaaaaaaaaaaaaaaaaaaaaaaa!";

String Exfiltration via ReDoS (Blind Regex Injection)

When you control the regex but not the input (e.g., flag validation), use timing-based exfiltration:

Pattern 1 (PortSwigger technique):

^(?=<flag>)((.*)*)*salt$

Pattern 2 (CTF technique):

<flag>(((((((.*)*)*)*)*)*)*)!

Pattern 3 (Simple brute force):

^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

How it works:

1. The regex matches the flag prefix
2. If the guess is correct, the nested quantifiers cause catastrophic backtracking
3. The page freezes or times out
4. If the guess is wrong, the regex fails quickly
5. Use timing differences to exfiltrate characters one by one

Engine-Specific Notes

JavaScript (Browser/Node.js)

• Built-in RegExp is backtracking and commonly exploitable
• Works when both regex and input are attacker-influenced
• Browser tabs can freeze, Node.js processes can hang

Python

• re module is backtracking
• Long ambiguous runs + failing tail = catastrophic backtracking
• Use regex module or re2 for safer alternatives

Java

• java.util.regex is backtracking
• If you control input: look for complex validators
• If you control patterns: ReDoS is usually trivial
• Use RE2J for linear-time alternatives

Safe Engines (ReDoS-Resilient)

• RE2 (C++, Java, Go, JavaScript ports)
• Rust regex crate
• Hyperscan
• These use finite automata and guarantee linear time

Fixing Vulnerable Patterns

Strategy 1: Use Atomic Groups

# Vulnerable
(a+)+

# Fixed (if engine supports atomic groups)
(a++)+

Strategy 2: Use Possessive Quantifiers

# Vulnerable
(a+)+

# Fixed
(a++)+

Strategy 3: Simplify the Pattern

# Vulnerable
([a-zA-Z]+)*

# Fixed
[a-zA-Z]+

Strategy 4: Use Non-Backtracking Engines

• Replace re with regex module in Python
• Use RE2 in Java/Go/JavaScript
• Use Rust's regex crate

Strategy 5: Add Length Limits

# Before processing
if len(user_input) > 1000:
    raise ValueError("Input too long")

Quick Reference

Common Vulnerable Patterns

Testing Commands

# Test single pattern
python scripts/redos_timing_test.py "(a+)+$" "aaaaaaaaaaaaaaaaaaaaaaaa!"

# Test with length progression
python scripts/redos_timing_test.py "(\w*_)*\w*$" --lengths 8 10 12 14 16 18 20

# Scan codebase
regexploit-py /path/to/code/
regexploit-js /path/to/code/

References

• OWASP ReDoS
• PortSwigger: Blind Regex Injection
• regexploit
• vuln-regex-detector
• RE2: Why Linear-Time Regex
• SoK 2024: ReDoS Review