GHSA-x4c5-c7rf-jjgv @octokit/endpoint has a Regular Expression in parse that Leads to ReDoS Vulnerability Due to Catastrophic Backtracking
SummaryBy crafting specific `options` parameters, the `endpoint.parse(options)` call can be triggered, leading to a regular expression denial-of-service (ReDoS) attack. This causes the program to hang and results in high CPU utilization.DetailsThe issue occurs in the `parse` function within the `parse.ts` file of the npm package `@octokit/endpoint`. The specific code is located at the following link: https://github.com/octokit/endpoint.js/blob/main/src/parse.ts, at line 62:The regular expression `/[\w-]+(?=-preview)/g` encounters a backtracking issue when it processes `a large number of characters` followed by the `-` symbol.
e.g., the attack string:PoC[The gist](https://gist.github.com/ShiyuBanzhou/a17202ac1ad403a80ca302466d5e56c4)
Here is the reproduction process for the vulnerability:run `npm i @octokit/endpoint`Move `poc.js` to the root directory of the same level as `README.md`run `node poc.js`
result:then the program will be stuck forever with high CPU usage**Import the `endpoint` module**: First, import the `endpoint` module from the npm package `@octokit/endpoint`, which is used for handling GitHub API requests.**Construct the `options` object that triggers a ReDoS attack**: The following member variables are critical in constructing the `options` object:`url`: Set to `"/graphql"`, ensuring the URL ends with `/graphql` to match the format for GitHub's GraphQL API.`headers`:`accept`: A long attack string is crafted with `"A".repeat(100000) + "-"`, which will be passed to the regular expression and cause a backtracking attack (ReDoS).`mediaType`:`previews`: Set to `["test-preview"]`, ensuring `mediaType.previews` exists and has values.`format`: Set to `"raw"`, indicating raw data format.**Call the `endpoint.parse(options)` function and record the time**: Call the `endpoint.parse(options)` function and use `performance.now()` to record the start and end times, measuring the execution duration.**Calculate the time difference and output it**: Compute the difference between the start and end times and output it using `console.log`. When the attack string length reaches 100000, the response time typically exceeds 10000 milliseconds, satisfying the characteristic condition for a ReDoS attack, where response times dramatically increase.
<img width="800" alt="2" src="https://github.com/user-attachments/assets/9fc865a4-e150-42d5-bcd5-93ab6b0c29ef" />ImpactWhat kind of vulnerability is it?This is a **Regular Expression Denial of Service (ReDoS)** vulnerability. It arises from inefficient regular expressions that can cause excessive backtracking when processing certain inputs. Specifically, the regular expression `/[\w-]+(?=-preview)/g` is vulnerable because it attempts to match long strings of characters followed by a hyphen (`-`), which leads to inefficient backtracking when provided with specially crafted attack strings. This backtracking results in high CPU utilization, causing the application to become unresponsive and denying service to legitimate users.Who is impacted?This vulnerability impacts any application that uses the affected regular expression in conjunction with user-controlled inputs, particularly where large or maliciously crafted strings can trigger excessive backtracking.
In addition to directly affecting applications using the `@octokit/endpoint` package, the impact is more widespread because `@octokit/endpoint` is a library used to wrap REST APIs, including GitHub's API. This means that any system or service built on top of this library that interacts with GitHub or other REST APIs could be vulnerable. Given the extensive use of this package in API communication, the potential for exploitation is broad and serious. The vulnerability could affect a wide range of applications, from small integrations to large enterprise-level systems, especially those relying on the package to handle API requests.
Attackers can exploit this vulnerability to cause performance degradation, downtime, and service disruption, making it a critical issue for anyone using the affected version of `@octokit/endpoint`.SolutionTo resolve the ReDoS vulnerability, the regular expression should be updated to avoid excessive backtracking. By modifying the regular expression to `(?<![\w-])[\w-]+(?=-preview)`, we prevent the issue.
Here is how this change solves the problem:**Old Regular Expression**: `/[\w-]+(?=-preview)/g`This regular expression matches any sequence of word characters (`\w`) and hyphens (`-`) followed by `-preview`.The issue arises when the regex engine encounters a long string of characters followed by a `-`, causing excessive backtracking and high CPU usage.**New Regular Expression**: `(?<![\w-])[\w-]+(?=-preview)`This updated regular expression uses a negative lookbehind `(?<![\w-])`, ensuring that the matched string is not preceded by any word characters or hyphens (`\w` or `-`).The new expression still matches sequences of word characters and hyphens, but the negative lookbehind ensures it doesn't cause backtracking issues when processing long attack strings.By adding this lookbehind, we effectively prevent the vulnerability, ensuring the regex operates efficiently without excessive backtracking.Full Solution Example:The specific code is located at the following link: https://github.com/octokit/endpoint.js/blob/main/src/parse.ts, at line 62:**Update the Regular Expression**: In the `parse.ts` file (or wherever the original regex is defined), replace the existing regular expression:With the updated one:**Test the Change**: After updating the regular expression, thoroughly test the application with both regular and malicious inputs to ensure that:The functionality remains correct and the expected matches still occur.The performance improves and the ReDoS vulnerability no longer occurs when handling large attack strings.**Deploy the Fix**: Once the solution is verified, deploy the fix to your production environment to protect against potential attacks.
CVSS v3.1 score: 5.3