Coordinated Disclosure Timeline
- 2021-01-21: Emailed report to email@example.com
- 2021-02-25: No response so far, so replied to the original email asking for an update.
- 2021-02-25: Received a reply from Claudia Meadows (firstname.lastname@example.org).
- 2021-02-25: Pierre-Yves Gérardy has implemented a fix and created a draft security advisory.
- 2021-04-13: I ask if the draft security advisory is ready to publish. Claudia Meadows responds that they will publish it in a few days time.
- 2021-08-21: I ask again for the draft security advisory to be published.
- 2021-08-31: Published as per our policy.
The project contains one or more regular expressions that are vulnerable to ReDoS (Regular Expression Denial of Service)
Latest commit at the time of reporting (January 21, 2021).
ReDoS, or Regular Expression Denial of Service, is a vulnerability affecting poorly constructed and potentially inefficient regular expressions which can make them perform extremely badly given a creatively constructed input string.
For the specific regular expression reported, it is possible to force it to work with an
O(2^n) runtime performance when there is exponential backtracking.
ReDoS can be caused by ambiguity or overlapping between some regex clauses. These badly performing regular expressions can become a security issue if a user can control the input. For example if the project is an input validation library, then the project could be used by a server to validate untrusted user input. There is no one size fits all when it comes to fixing ReDoS. But in general it is about removing ambiguity/overlap inside the regular expression.
Before showing the vulnerable regex, it may be helpful to show some examples of regular expressions vulnerable to ReDoS and how to fix them. If you are familiar with this vulnerability and how to fix it, please skip this section.
var reg = /<!--(.|\s)*?-->/g;
The above regular expression matches the start of an HTML comment, followed by any characters, followed by the end of a HTML comment.
The dot in the regular expression (
.) matches any char except newlines, and
\s matches any whitespace.
\s matches whitespace such as the space character.
There are therefore many possible ways for this regular expression to match a sequence of spaces.
This becomes a problem if the input is a string that starts with
<!-- followed by a long sequence of spaces, because the regular expression evaluator will try every possible way of matching the spaces
(see this debugging session for an example: https://regex101.com/r/XvYgkN/1/debugger).
The fix is to remove the ambiguity, which can be done by changing the regular expression to the below, where there is no overlap between the different elements of the regular expression.
var reg = /<!--(.|\r|\n)*?-->/g;
var reg = /(\w+_?)+_(\d+)/;
The above matches a snake_case identifier that ends with some digits.
However, for a string starting with lots of letters, there many ways for the regular expression to match those letters, due to the regex having a repetition matching letters (
w+) inside another repetition that can match letters (
The regular expression evaluator will try every possible grouping of letters into smaller groups of letters (see this debugging session for an example: https://regex101.com/r/fmci1j/1/debugger).
The fix is again to remove ambiguity, by changing the inner repetition to match groups of letters that must end with an underscore.
var reg = /(\w+_)+(\d+)/;
Often the regular expressions are not as simple as the examples above. Like the below regular expression that used to be part of VS Code. (the top regular expression is the vulnerable, the bottom is the fixed)
var linkPattern = /(\[((!\[[^\]]*?\]\(\s*)([^\s\(\)]+?)\s*\)\]|(?:\\\]|[^\]])*\])\(\s*)(([^\s\(\)]|\(\S*?\))+)\s*(".*?")?\)/g; var linkPattern = /(\[((!\[[^\]]*?\]\(\s*)([^\s\(\)]+?)\s*\)\]|(?:\\\]|[^\]])*\])\(\s*)(([^\s\(\)]|\([^\s\(\)]*?\))+)\s*(".*?")?\)/g;
But this example is actually very similar to the first example.
A section of the regular expression that was too general (
\S) was changed to something a bit more specific (
[^\s\(\)]) to remove overlap with another part of the regular expression.
mithril.js is a general purpose DOM manipulation libray. It includes a CSS selector parser, that is vulnerable to ReDoS. The attack requires that an attacker can inject a string into a CSS selector at runtime. It is quite common to be able to inject into jQuery CSS selectors, so the attack seems realistic. (Old versions of jQuery had a similar vulnerability, which is fixed now).
This vulnerability was found using a CodeQL query which identifies inefficient regular expressions.
mithril.js is a browser library. The PoC therefore invokes the CSS parser directly.
npm install mithril
- Run the below with
var str = ‘[a=”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”\”’; hyperscript(str); ```
This issue may lead to a denial of service.
This issue was discovered and reported by GitHub team member @erik-krogh (Erik Krogh Kristensen).
You can contact the GHSL team at
email@example.com, please include a reference to
GHSL-2021-028 in any communication regarding this issue.