ReDoS Vulnerability Analysis and Fix

[guiyi-he]

Vulnerability Description

A Regular Expression Denial of Service (ReDoS) vulnerability was identified in the turndown library's whitespace trimming functionality.

As shown in the figure, the matching between the regular term and the attack string is nonlinear, and the time growth curve approaches exponential, indicating a ReDos vulnerability. For details, please refer to the website: https://mmmsssttt404.github.io/ReDos-Line-Chart-Drawing/

Vulnerable Pattern

/^(([ \t\r\n]*)(\s*))(?:(?=\S)[\s\S]*\S)?((\s*?)([ \t\r\n]*))$/

Attack String

"\u0000 " + "\t".repeat(100000) + "\u000b"

Root Cause

The regex contains nested quantifiers (\s*) and (\s*?) that create exponential backtracking when processing malicious input with repeated whitespace characters.

Security Fix

Original Vulnerable Code

var m = string.match(/^(([ \t\r\n]*)(\s*))(?:(?=\S)[\s\S]*\S)?((\s*?)([ \t\r\n]*))$/)

Fixed Code with Negative Lookahead

var m = string.match(/^(?!.*(\s)\1{10000,})(([ \t\r\n]*)(\s*))(?:(?=\S)[\s\S]*\S)?((\s*?)([ \t\r\n]*))$/)

Fix Explanation

• Added negative lookahead (?!.*(\s)\1{10000,}) at the beginning
• Prevents matching strings with more than 10,000 consecutive identical whitespace characters
• Blocks the attack vector while preserving normal functionality
• Uses backreference \1 to match the same whitespace character type

Impact Assessment

• Severity: Medium to High
• Attack Vector: Crafted input strings with excessive whitespace
• Effect: CPU exhaustion, application freeze, potential DoS
• Affected Component: String trimming functionality in turndown library

Mitigation Strategy

1. Apply the negative lookahead fix to prevent catastrophic backtracking
2. Consider input validation for string length limits
3. Implement timeout mechanisms for regex operations in production

Testing

Test the fix with both the attack string and normal use cases to ensure functionality is preserved while preventing the ReDoS condition.

[martincizek]

Thank you for reporting this.

It should be O(n^2), not exponential. Even the attached charts show a quadratic function.

I consider this a performance issue. Turndown does not promise O(n), although that's the optimum. And SECURITY.md warns against using unsanitized inputs.

We'll look into it.

[pavelhoral]

@ShiyuBanzhou can you please provide a link to the code with the problematic regexp?

[domchristie]

The Rails Core team recently discussed these kinds of issues. They have raised an exception after a timeout. See: https://youtu.be/QaQ9rF9sYHQ?si=rQEUGtmwWzG3Nam1 at about 20mins