New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Vulnerable Regular Expression #167

Closed
cristianstaicu opened this Issue Sep 5, 2017 · 5 comments

Comments

Projects
None yet
3 participants
@cristianstaicu

cristianstaicu commented Sep 5, 2017

The following regular expression used in the mime lookup is vulnerable to ReDoS:

/.*[\.\/\\]/

The slowdown is moderately low: for 50.000 characters around 2 seconds matching time. However, I would still suggest one of the following:

  • remove the regex,
  • anchor the regex,
  • limit the number of characters that can be matched by the repetition,
  • limit the input size.

If needed, I can provide an actual example showing the slowdown.

@dougwilson

This comment has been minimized.

Show comment
Hide comment
@dougwilson

dougwilson Sep 25, 2017

The regular expression listed is used in a .replace() in the 1.x series. Trying to use a similar format to what was shown in other repos, I cannot reproduce the issue:

function genstr(len, chr) {
    var result = "";
    for (i=0; i<=len; i++) {
        result = result + chr;
    }
    return result;
}

var mime = require('mime'); // npm i mime@1
var str =  "x." + genstr(50000, ' ') + "json";
var start = process.hrtime();
var ext = mime.lookup(str);
var end = process.hrtime(start);

console.info("Execution time (hr): %ds %dms", end[0], end[1] / 1000000);
$ node test.js
Execution time (hr): 0s 1.033836ms

This was the worst case I was able to figure out for the stated ~50k, and it was just 1ms. @evilpacket do you know if this is a real issue, and if so, can you contact me / @broofa with the details or can this be closed?

dougwilson commented Sep 25, 2017

The regular expression listed is used in a .replace() in the 1.x series. Trying to use a similar format to what was shown in other repos, I cannot reproduce the issue:

function genstr(len, chr) {
    var result = "";
    for (i=0; i<=len; i++) {
        result = result + chr;
    }
    return result;
}

var mime = require('mime'); // npm i mime@1
var str =  "x." + genstr(50000, ' ') + "json";
var start = process.hrtime();
var ext = mime.lookup(str);
var end = process.hrtime(start);

console.info("Execution time (hr): %ds %dms", end[0], end[1] / 1000000);
$ node test.js
Execution time (hr): 0s 1.033836ms

This was the worst case I was able to figure out for the stated ~50k, and it was just 1ms. @evilpacket do you know if this is a real issue, and if so, can you contact me / @broofa with the details or can this be closed?

@broofa

This comment has been minimized.

Show comment
Hide comment
@broofa

broofa Sep 25, 2017

Owner

I believe I'm able to repro the issue with the code below. Looks like complexity is ~O(N^2).

var RE = /.*[\.\/\\]/;

function test(len) {
  const str = new Array(len).join().replace(/,/g, ' ');

  const start = process.hrtime()
  const res = str.replace(RE, '');
  console.log('N chars:', len, 'Time:', process.hrtime(start));
}

test(1000);
test(2000);
test(5000);
test(10000);
test(20000);
test(50000);
test(100000);
test(200000);
test(500000);

Yields the following output

N chars: 1000 Time: [ 0, 16273206 ]
N chars: 2000 Time: [ 0, 3165858 ]
N chars: 5000 Time: [ 0, 19505864 ]
N chars: 10000 Time: [ 0, 86073894 ]
N chars: 20000 Time: [ 0, 325145464 ]
N chars: 50000 Time: [ 2, 48747126 ]
N chars: 100000 Time: [ 8, 251471106 ]
N chars: 200000 Time: [ 33, 30366008 ]
N chars: 500000 Time: [ 211, 463680672 ]
Owner

broofa commented Sep 25, 2017

I believe I'm able to repro the issue with the code below. Looks like complexity is ~O(N^2).

var RE = /.*[\.\/\\]/;

function test(len) {
  const str = new Array(len).join().replace(/,/g, ' ');

  const start = process.hrtime()
  const res = str.replace(RE, '');
  console.log('N chars:', len, 'Time:', process.hrtime(start));
}

test(1000);
test(2000);
test(5000);
test(10000);
test(20000);
test(50000);
test(100000);
test(200000);
test(500000);

Yields the following output

N chars: 1000 Time: [ 0, 16273206 ]
N chars: 2000 Time: [ 0, 3165858 ]
N chars: 5000 Time: [ 0, 19505864 ]
N chars: 10000 Time: [ 0, 86073894 ]
N chars: 20000 Time: [ 0, 325145464 ]
N chars: 50000 Time: [ 2, 48747126 ]
N chars: 100000 Time: [ 8, 251471106 ]
N chars: 200000 Time: [ 33, 30366008 ]
N chars: 500000 Time: [ 211, 463680672 ]
@broofa

This comment has been minimized.

Show comment
Hide comment
@broofa

broofa Sep 25, 2017

Owner

Looks like anchoring the RE (as suggested by @cristianstaicu) fixes the problem. If I change the RE to /^.*[\.\/\\]/, I get the following results:

N chars: 1000 Time: [ 0, 16485058 ]
N chars: 2000 Time: [ 0, 22999 ]
N chars: 5000 Time: [ 0, 29946 ]
N chars: 10000 Time: [ 0, 24706 ]
N chars: 20000 Time: [ 0, 34055 ]
N chars: 50000 Time: [ 0, 80097 ]
N chars: 100000 Time: [ 0, 159342 ]
N chars: 200000 Time: [ 0, 379852 ]
N chars: 500000 Time: [ 0, 780705 ]

I'll patch this in both the 1.x and 2.x branches.

Owner

broofa commented Sep 25, 2017

Looks like anchoring the RE (as suggested by @cristianstaicu) fixes the problem. If I change the RE to /^.*[\.\/\\]/, I get the following results:

N chars: 1000 Time: [ 0, 16485058 ]
N chars: 2000 Time: [ 0, 22999 ]
N chars: 5000 Time: [ 0, 29946 ]
N chars: 10000 Time: [ 0, 24706 ]
N chars: 20000 Time: [ 0, 34055 ]
N chars: 50000 Time: [ 0, 80097 ]
N chars: 100000 Time: [ 0, 159342 ]
N chars: 200000 Time: [ 0, 379852 ]
N chars: 500000 Time: [ 0, 780705 ]

I'll patch this in both the 1.x and 2.x branches.

broofa added a commit that referenced this issue Sep 25, 2017

@broofa broofa closed this in 1df903f Sep 25, 2017

@broofa

This comment has been minimized.

Show comment
Hide comment
@broofa

broofa Sep 25, 2017

Owner

npm published in v1.4.1 and 2.0.3

Owner

broofa commented Sep 25, 2017

npm published in v1.4.1 and 2.0.3

@dougwilson

This comment has been minimized.

Show comment
Hide comment
@dougwilson

dougwilson commented Sep 26, 2017

Thanks @broofa !

bsclifton added a commit to bsclifton/webtorrent that referenced this issue Sep 28, 2017

bsclifton referenced this issue in brave/browser-laptop Sep 28, 2017

Add exception, supressing two new reported vulnerabilities
If this change looks OK, I'll make sure to submit patch to 0.20.x and master

Auditors: @evq, @darkdh, @diracdeltas

@nikeee nikeee referenced this issue Oct 22, 2017

Merged

Mime update #3122

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

@robocop robocop bot referenced this issue Nov 14, 2017

Closed

Update README.md #62

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

@robocop robocop bot referenced this issue Nov 14, 2017

Closed

Update README.md #63

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

@robocop robocop bot referenced this issue Nov 14, 2017

Closed

Update README.md #64

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

@robocop robocop bot referenced this issue Nov 14, 2017

Closed

Update README.md #67

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

@robocop robocop bot referenced this issue Nov 14, 2017

Closed

Update README.md #68

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

@robocop robocop bot referenced this issue Nov 14, 2017

Closed

Update README.md #69

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

robocop bot referenced this issue in goeltanmay/PatientsApp Nov 14, 2017

@robocop robocop bot referenced this issue Nov 15, 2017

Open

new dependency #83

@devongovett devongovett referenced this issue Jan 5, 2018

Closed

Update mime #151

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment