Key Points

• Recently, malicious Python packages – uploaded to PyPI by user “dsfsdfds” – were found to be exfiltrating sensitive user data without consent, to a Telegram chat bot.
• The Telegram bot is linked to multiple cybercriminal operations based in Iraq. The bot has activity dating back to 2022 and contains over 90,000 messages, mostly in Arabic.
• The bot functions also as an underground marketplace offering social media manipulation services. It has been linked to financial theft and exploits victims by exfiltrating their data.
• Initially, the malicious packages incident, appeared isolated. However, it is part of a larger, sophisticated cybercriminal ecosystem, emphasizing the importance of thorough investigation and collaboration within the cybersecurity community.

Attack Flow

The malicious script follows a systematic approach to compromise the victim’s system and exfiltrate sensitive data. It begins by scanning the user’s file system and focusing on two specific locations: the root folder and the DCIM folder. The script searches for files during the scanning process, with extensions such as .py, .php, and .zip files, as well as photos with .png, .jpg, and .jpeg extensions.

Once identified, the script sends their file paths, along with the actual files and photos, to the attackers Telegram bot. This all occurs without the end-user’s knowledge or consent.

The following code snippet demonstrates the core functionality of the malicious script:

The inclusion of hardcoded sensitive information, such as the bot token and chat ID, allowed us to gain further valuable insights into the attacker’s infrastructure and operations.

Additional Insights

Further analysis of the Telegram bot to which the exfiltrated data was being sent uncovered additional findings.

The hardcoded “chat_id” and “bot_token” present in the malicious packages allowed us to gain direct access to the attacker’s Telegram bot and monitor its activities. This technique (outlined here) proved to be a valuable tool in understanding the scope and nature of the attack.

This Telegram bot exhibited a significant history of activity. It had records dating back to at least 2022 –  long before the malicious packages were released on PyPI, and contained over 90,000 messages.

The messages were primarily in Arabic.  Further investigation with GitHub’s “TeleTracker” revealed that the bot operator maintained numerous other bots and was likely based in Iraq.

Initially, the bot appeared to function as a typical underground marketplace, offering various illicit services such as: purchasing Telegram and Instagram views, followers, spam services, and discounted Netflix memberships.

However, upon further examination of the bot’s message history, we found evidence of more sinister activities that appeared to be involved in financial theft. Additional messages suggested they were sent from systems compromised by the harmful Python packages.

The discovery of this elaborate Telegram-based cybercriminal operation underscores the importance of thorough and persistent investigation when researching the true extent of such attacks. Especially since the initial malicious packages served as a mere entry point to a much larger criminal ecosystem.

Conclusion

The discovery of the malicious Python packages on PyPI and the subsequent investigation into the Telegram bot have shed light on a sophisticated and widespread cybercriminal operation. What initially appeared to be an isolated incident of malicious packages turned out to be just the tip of the iceberg, revealing a well-established criminal ecosystem based in Iraq.

This use case describes simple data exfiltration, but think about what could happen if an attacker targeted an enterprise. While the initial compromise might occur on an individual developer’s machine, the implications for enterprises can be significant.

As the fight against malicious actors in the open source ecosystem persists, collaboration and information sharing among the security community will be critical in identifying and stopping these attacks. Through collective effort and proactive measures, we can work towards a safer and more secure open source ecosystem for all. Our research team is continuously investigating this attack to gain additional insights into the attacker’s modus operandi and will share further findings with the community as they emerge.

As part of the Checkmarx Supply Chain Security solution, our research team continuously monitors suspicious activities in the open-source software ecosystem. We track and flag “signals” that may indicate foul play and promptly alert our customers to help protect them.

PACKAGES

• testbrojct2
• proxyfullscraper
• proxyalhttp
• proxyfullscrapers

The research team of Checkmarx simultaneously investigated a campaign of multiple malicious packages appear to be related to the same threat actors.

The threat actors target victims with Typosquatting attack technique using their CLI to install Python packages. 

This is a multi-stage attack and the malicious payload aimed to steal crypto wallets, sensitive data from browsers (cookies, extensions data, etc..) and various credentials.

In addition, the malicious payload employed a persistence mechanism to survive reboots.

PyPi Suspended User and Project Creation

A few hours ago, on Mar 28, 2024 – 02:16 UTC, The Python Package Index (PyPi) added a new website banner and released an official update: “We have temporarily suspended new project creation and new user registration to mitigate an ongoing malware upload campaign”

Evidence of Multiple Malicious Typosquatting Packages

Between March 27 and March 28, 2024, multiple malicious Python packages were uploaded on the Python Package Index (PyPI). These packages most likely created using automation 

The Malicious Payload

The malicious code is located within each package’s setup.py file, enabling automatic execution upon installation.

employed a technique where the setup.py file contained obfuscated code that was encrypted using the Fernet encryption module. When the package was installed, the obfuscated code was automatically executed, triggering the malicious payload.

Upon execution, the malicious code within the setup.py file attempted to retrieve an additional payload from a remote server. The URL for the payload was dynamically constructed by appending the package name as a query parameter. 

The retrieved payload was also encrypted using the Fernet module, Once decrypted, the payload revealed an extensive info-stealer designed to harvest sensitive information from the victim’s machine.

The malicious payload also employed a persistence mechanism to ensure it remained active on the compromised system even after the initial execution.

A small piece of the larger script

Summary

The discovery of these malicious Python packages on PyPI highlights the ongoing nature of cybersecurity threats within the software development ecosystem.

This incident is not an isolated case, and similar attacks targeting package repositories and software supply chains are likely to continue.

As this situation unfolds, we will provide updates on any new developments.

Working together to keep the open source ecosystem safe.

Package List

IOCs

• hxxps://funcaptcha[.]ru/paste2
• hxxps://funcaptcha].[ru/delivery
• hxxps://funcaptcha.ru/atomic/app.asar
• ABE19B0964DAF24CD82C6DB59212FD7A61C4C8335DD4A32B8E55C7C05C17220D      

0C1DDD33E630F4AC684880F0E673DFA84919272494C11DA0F1EC05FB4F919CE8

The threat actors behind these packages deviated from conventional tactics, introducing a nuanced twist in their approach. The first notable tactic was the exploitation of GitHub, a platform synonymous with trust and reliability within the developer community, to disseminate their malicious code. The packages themselves were mere vessels; the actual malicious content was not embedded within them but distributed through them.

This tactic capitalizes on the confidence developers inherently place in GitHub as a staple source for software tools, adding a layer of deceit to the attackers’ scheme and complicating the task for developers in distinguishing between legitimate and suspicious packages.

But that is not the only thing that stands out in this attack attempt. In this blog, we will explain the various combined tactics the attacker used to make these packages stand out.

Key Takeaways

• A number of Python packages surfaced in December on PyPI, utilizing GitHub as a distribution channel for their malicious code.
• One of the packages combined obfuscation with encryption/decryption techniques to mask the harmful intent within the code.
• One of the packages deployed fileless malware, ensuring stealthy execution without leaving traces on disk and better circumventing modern EDR solutions.
• One of the packages exploited the reputation of the widely-used PySocks project to gain trust and increase the likelihood of their malicious packages being downloaded.
• All packages specifically targeted Windows machines.

The “httprequesthub” Package: A Multiple-Stage Malicious Process

The httprequesthub Python package stands out for its sophisticated multi-stage process, executing malicious code hidden within layers of encryption and obfuscation.

httprequesthub attack flow

Stage One

The package starts by decoding a Base64 encoded string within its setup.py file, unveiling a URL that points to a GitHub gist created by the threat actor. This gist acts as the first external payload source.

First stage payload in setup.py file

At the time of publication, the user and gist are still active.

Stage Two

Upon accessing the URL, the package retrieves a second-stage payload characterized by complex obfuscated code combined with arbitrary and non-descriptive variables and function names.

The attacker adds a unique twist by mixing the use of obfuscation and encryption to enhance the complexity of the code, making it even more challenging to understand its intent.

After manually simplifying this code, we get this:

Second stage payload after simplifying it.

Another base64 encoded URL within the executed code leads to yet another GitHub gist, deepening the layers of the attack. This GitHub gist and user profile are no longer active.

This phase also includes a specific condition to fetch and execute the code from the second URL only on Windows systems, tailoring the attack based on the victim’s OS.

Stage Three

The third stage involves executing Python code from the second URL, which is also obfuscated. Simplifying this code reveals a blend of encryption and obfuscation, with a base64 encoded string undergoing a custom XOR decryption process. This produces a complex, encrypted code block, showcasing the attacker’s dedication to concealing their payload’s nature.

After again, manually simplifying this code we get this:

Third stage payload after simplifying it.

The sophistication of the attack escalates further with its reliance on fileless execution Instead of the traditional file-based execution, allowing it to bypass modern EDR solutions.

It dynamically allocates memory within the current process and transfers the decoded payload into this space. Utilizing the Windows API via the ctypes module, it manipulates system memory to create an executable thread directly within the memory, circumventing traditional disk-based detection mechanisms. This fileless execution approach is particularly concerning as it leaves no trace on the hard drive, posing a significant challenge for conventional security tools to detect and mitigate.

Given the multi-staged nature of this attack, it is extremely challenging to identify the malicious intent of the package through static analysis alone, even with the aid of machine learning. For such cases, advanced dynamic solutions are necessary alongside static methods to effectively detect such sophisticated threats.

We have yet to fully determine the end goal of this package.

The “easyhttprequest” Mysterious Package, Exploiting the Shadow of a Popular Project

easyhttprequest attack flow

The easyhttprequest Python package employs a deceptive technique by overriding the standard installation process with a custom PostInstall class embedded within its setup.py script. This class is meticulously mapped to the “install” command in the cmdclass dictionary and is designed to execute additional code when the package is installed using the setup.py install command.

Upon installation, the package’s first move is to clone a GitHub repository (isaaknikolaev/PySocks) into a temporary directory on the user’s system, creating a folder named “PySocks.”

This repository is in fact a fork of the vastly popular “Anorov/PySocks” repository, whose corresponding Python package “pysocks” boasts millions of weekly downloads. This tactic of riding off the reputation of a renowned project is a calculated move to cloak the package’s true intent under the guise of a trustworthy source, enhancing its chances of evading detection.

This cloning occurs regardless of the operating system. However, the script includes a condition specifically for Windows systems, where it installs an additional Python package, dulwich (a package used for interacting with Git repositories)

Upon cloning the repository, the package checks the latest commit message for a particular trigger string (uJq93k8bmm7KqjL). If this string is present, the script removes the trigger string, decodes the remaining message, and proceeds to execute the remaining part of the commit message, which is encoded in Base64. This execution step is where the potential for running malicious code lies.

At the time of discovery, no malicious content was found in the commit message of the cloned repository. This could indicate that either the package was intercepted and sanitized before the attacker could deploy their intended malicious code, or the harmful content was never committed. Nevertheless, the structure of the package indicates a clear intent for malicious use, showcasing a sophisticated method of hiding and executing potentially harmful code through a seemingly innocent package installation.

• For nearly half a year, a threat actor has been planting malicious Python packages into the open-source repository. 
• Many of the malicious packages were camouflaged with names closely resembling popular legitimate Python packages. Consequently, they received thousands of downloads. 
• The setup.py file within these packages was used to carry the harmful payload, which allowed the malicious code to be executed upon installation. 
• A defining characteristic of this attack was the utilization of steganography to hide a malicious payload within an innocent-looking image file, which increased the stealthiness of the attack. 
• The attack pattern pointed to a systematic approach, with the code in these packages exhibiting similar obfuscation techniques and harmful payloads. 
• The ultimate goal of these packages appears to be gaining persistence on the compromised systems, stealing sensitive information, and achieving financial gains. 

It has become commonplace for attackers to invest a significant amount of time and effort within the open-source ecosystem.  

Attackers, driven by malicious intent, demonstrate an extraordinary level of persistence in their pursuit of exploiting vulnerabilities in the open-source ecosystem. While they may not always achieve their objectives in every single attack, their unwavering determination allows them to eventually identify and target vulnerable individuals or organizations. This persistence, coupled with the increasing number of attackers engaging in these activities, suggests that there is a certain degree of success within this realm. 

For close to six months, a malicious actor has been stealthily uploading dozens of malicious Python packages, most of them mimicking the names of legitimate ones, to bait unsuspecting developers. 

All packages containing malicious code had it embedded within the setup.py file, allowing the code to execute upon package installation. For packages that didn’t directly contain malicious code, they included references to other malicious packages, likely to trick developers into downloading them. These malicious packages contained different variations of malicious code, but the most common method of operation was as follows: 

• User Identification: The scripts began by verifying the username of the logged-in user. 
• Directory Verification and Creation: They checked for a particular directory named “System64” within the user’s Start Menu Programs path. If nonexistent, the script created it. 
• File Placement and Execution: The scripts then deployed VBScript and batch files that downloaded and executed a file named “Runtime.exe”, ensuring its persistence on the system by placing it in the system’s Startup folder. 
• Stealth and Cleanup: Post-execution, the scripts cleared their tracks by deleting the evidence of their presence. 

A Common Blueprint 

The initial obfuscated code within the setup.py file followed a similar structure across most packages: 

Upon deobfuscation, the script’s true nature was revealed, with minor variations distinguishing one malicious package from the other: 

The “Runtime.exe” turned out to be a Python program harboring a compiled file “s.pyc”. From this, we extracted disassembly code that was designed to steal extensive sensitive information from the compromised system, various browsers, and applications. 

Financial Data Theft 

Like many attacks we’ve increasingly seen during these past couple of years on the open-source ecosystem, the attacker in this case seemed to also aim to profit from cryptocurrency. The script demonstrates its capability for stealing financial data, with a specific focus on targeting cryptocurrency assets. It would scan for the ‘Local State’ file of the Exodus cryptocurrency wallet, which usually includes sensitive configuration data that could be exploited to gain unauthorized access to a user’s cryptocurrency funds. 

Exfiltration 

The stolen information is ultimately stored in separate files named: 

• alls.armageddon 
• ckk.armageddon 
• imp.armageddon 
• pskk.armageddon 
• toks.armageddon 

These files were later exfiltrated by being uploaded to the following endpoints: “hxxp[:]//51.178.25.148:8081/uploader “ and “hxxp[:]//51.178.25.148:8081/upload”. 

Once this process was complete, all of these files were deleted from the host. 

Behind the Pixels: Steganography at Play 

Some outliers in this attack campaign used more sophisticated methods. They employed steganography to hide executable code within a PNG image that was downloaded from an external link and saved as “uwu.png” inside the user’s “%APPDATA%/local” directory. 

Once this was done, the image file previously downloaded was deleted, clearing its tracks. and the fetched code was decoded and executed using the built-in exec() function 

The payload was designed to collect the public IP address of the affected host and its UUID (machine ID) and exfiltrate this information to an external server.  

Encoded payload within the image: 

which translates to this: 

They all lead to two packages: 

A common thread in the descriptions of all malicious packages was the mention of “Pystob” or “Pywool”. These packages masqueraded as useful tools for API management, but upon closer inspection, were found to be obfuscated twice over, hiding their true, harmful nature. 

So, it appears as though the packages were also attempting to get their victims to deliberately download these packages. Upon investigating these two packages, it was found that their code was also placed within the setup.py file and the code was obfuscated under two layers. 

This malicious payload essentially downloads and runs executable files aimed at performing various malicious activities which also include: 

• Collecting user data and exfiltrating it to a Discord webhook. 
• Attempting to maintain persistence by placing a VBS file in the Windows startup folder. 

In a clever move, the attacker also utilized the domain name ‘api-hw.com’ to download the second-stage payload. This choice of domain was likely a strategic decision to make the packages appear more legitimate and relevant to their presumed functionality. However, at this time the attacker no longer has control over this domain and it appears to be available for purchase, indicating either a retreat or a shift in their strategy. 

Targets of the Attack 

One critical aspect of this attack was the selection of targets. The attackers chose popular legitimate Python packages and created malicious counterparts with similar names. This strategy aimed to increase the chances of developers accidentally downloading the malicious packages. To demonstrate the extent of this deception, refer to the table below, which compares some examples of the names of the malicious packages with their legitimate counterparts and includes the download count of the legitimate packages. Overall, the malicious packages received over four thousand downloads. 

Percentage Distribution of Total Downloads of the Malicious Package by Country 

Conclusion 

This campaign serves as another stark reminder of the ever-present threats that exist in today’s digital landscape, particularly in areas where collaboration and open exchange of code are foundational. It is crucial to recognize the importance of cybersecurity measures and remain vigilant in protecting sensitive information. 

To enhance security, consumers of open-source packages should vet packages before installing them and at the very least, utilize public advisories and security assessment platforms like the community-driven overlay browser extension. This extension provides insights into the security score and other relevant information about the package based on various platforms including socket.io, deps.dev, and snyk. By using these resources, developers can make informed decisions and reduce risks in their DevOps pipelines. 

As part of the Checkmarx Supply Chain Security solution, our research team continuously monitors suspicious activities in the open-source software ecosystem. We track and flag “signals” that may indicate foul play and promptly alert our customers to help protect them. 

Packages 

IOC 

• hxxp[:]//51.178.25.148[:]8081/upload 
• hxxp[:]//51.178.25.148[:]8081/dl/runtime 
• hxxp[:]//51.178.25.148[:]8081/uploader 
• hxxp[:]//51.178.25.148[:]8081/gethw 
• hxxp[:]//51.178.25.148[:]8081/dl/system 
• hxxp[:]//51.178.25.148[:]8081/getip 
• hxxp[:]//51.178.25.148[:]8081/dl/uwu 
• hxxp[:]//51.178.25.148[:]8081/rooter 
• hxxps[:]//pastebin.com/raw/TwHdexDC 
• hxxps[:]//canary.discord.com/api/webhooks/1153431050517762059/MAkfrB4n1Gz6qe7W8ffWTZF92yfN3D_FWPFFaK_FBgDQWB1ZYfbKHa61X_8L6GK175r0 
• hxxps[:]//canary.discord.com/api/webhooks/1155235432406196334/3eFtMXnG2laJjInzO_kAzLbW6ebMgbrrwmAcRtZyOfqnyCh-twTT9pSumcKr5QJvbGEZ 
• hxxps[:]//canary.discord.com/api/webhooks/1152716297474424913/z6-hvrQNeyL0m1Mm34JLYj1VVB67sVEXogqJzGCkxYgMFCgCWhQaR07ruMBck1dJAi9g 
• hxxp[:]//51.178.25.148[:]8081/dl/sys86 
• hxxp[:]//51.178.25.148[:]8081/dl/gamesdk 
• hxxps[:]//canary.discord.com/api/webhooks/1152648911371120681/JlL5FnwmY6nP6RaZxmQ7NI9MGR6HARmAekaPqPDdVTq9K3RJ68Lcd7cz16l9u6eZH9c3 
• hxxps[:]//discord.com/api/webhooks/1103033150558457876/22oUF1rkDTdxz-iq-2EOR4aVXwDr5vFIeE9zWlitIbYSG2E3XhF8KQIzuo1uXy_bOcos 

ReDoS

Regular Expression Denial of Service (ReDoS) is an algorithmic complexity attack that provokes a Denial of Service (DoS). ReDos attacks are caused by a regular expression that takes a very long time to be evaluated, exponentially related with the input size. This exceptionally long time in the evaluation process is due to the implementation of the regular expression in use, for example, recursive backtracking ones.
A regular expression, better known as a ‘regex’, is a sequence of characters that defines a search pattern, used to search for one or more characters within a string. One of the handy usages of a regex is information validation, i.e., ensuring that only properly formed data is being submitted.
For example, let’s pretend that we want to apply a regular expression over the username input of listing 1. Thus, a simple regex could be:
/^[a-zA-Z0-9_-]{3,10}$/
Listing 2: Regex example 1
The regular expression is contained between the slash characters and in the pattern 2 regex. We start by telling the parser to find the beginning of the string (ˆ), followed by any lowercase letter (a-z), uppercase letter (A-Z), number (0-9), an underscore, or a hyphen. The {3,10} section makes sure that the entered string has a length between three and ten characters. Finally, the $ represents the end of the string. For this regex, if we used the input ”checkmarx”  it would match the pattern:

Figure 1: Example – Regex 1

On the other hand, if we used a string like ”checkmarx’ OR SLEEP(10)–” it would not match the pattern.

Figure 2: Example – Regex 1 Fail

Evil Regular Expressions

Even though the benefits of using regexs for input validations are great, depending on the way they are written and the engine used, a malicious user can leverage it and make the application or service unavailable. Thus, evil regexs are the root cause of the ReDoS issue. They are considered evil or malicious if they can stuck on crafted input. To understand this better, let’s consider the following regular expression:
/A(B|C+)+D/
Listing 3: Evil Regex example 1
In this scenario, this regex pattern starts by searching for the character ’A.’ Then, the following string must either be the character ’B’ or one or more ’C’s, (B|C+). The next + indicates that it can search for one or more occurrences of the previous string. Finally, the ’D’ ensures that the string is terminated by the character ’D’. To match this regular expression, any input of the following type would be accepted:
ABCD
ABCBD
ACD
ACBD
Listing 4: Valid input for Evil regex 1
To show the differences between the implementations used by different languages, we created simple programs in four different languages: Python, JavaScript, PHP and Go. All created programs use the regex from example 3. This benchmark was done incrementing passed inputs, allowing us to visually understand the different behaviors of the program depending on the variations of the inputs.
In the example code from listing 5, we show a simple Python implementation to evaluate the evil regex. We start by testing the valid inputs from listing 4. Then we send malicious inputs to try to get the program stuck.
regex = r”A(B|C+)+D”
test_str = raw_input(“Enter the string: “)
matches = re.finditer(regex, test_str) (…)
print (“It took: %s seconds” % elapsedTime)
Listing 5: Python Regex compiler
To craft malicious inputs, we started by incrementing valid and invalid inputs, and tweaking it according to the time differences between them. At some point, we found some relevant discrepancies. In figure 4, we show the attempted malicious payloads and the matching elapsed time for evaluation. We see that when a malicious input payload of type AC+E, where + represents one or more occurrences of the character C, is sent with more than 20 Cs, the elapsed time starts to double for each new C.

The same principle was applied to the other languages and we maintained the input cases in order to compare the results. The next example is for JavaScript. Listing 6 shows the JS code snippet:
const regex = /A(B|C+)+D/g; (…)
let m;
while ((m = regex.exec(str)) !== null) { (…)
} (…)
console.log(“It took: ” + seconds + ” seconds”);
Listing 6: JS Regex compiler
The obtained results for the JavaScript implementation are as follows:

The next example is PHP:
$re = ‘/A(B|C+)+D/’;
preg_match_all($re, $str, $matches, PREG_SET_ORDER, 0); (…)
echo $timediff.” seconds”;
Listing 7: PHP Regex compiler
Where the results from figures 7 and 8 produced these results:

Finally, an example for Go. We created the following program:
func main() {
re := regexp.MustCompile(`A(B|C+)+D`) (…)
for i, match := range re.FindAllString(str, -1) { fmt.Println(match, “found at index”, i)
} (…)
fmt.Println(“It took:”, elapsed.Seconds(), “seconds”)
}
Listing 8: Go Regex compiler
And produced the following results:

We can see that the results from PHP (8) and Go (10) implementations are much different from the Python (4) and JavaScript (6) results. The malicious inputs used in Python and JavaScript generated exponential time increments, versus the linear time responses for PHP and Go.
In the PHP regex implementation, we used the Perl Compatible Regular Expressions (PCRE) library 1, which uses backreferences. The official regex package [2] implemented in Go uses the RE2 engine 2, which does not support backreferences, and guarantees a linear time execution while avoiding regex denial of service.
In table 1, we summarize the obtained results for each programming language, where it is displayed the elapsed time in seconds for each input that was tested. For the purpose of this post, we only tested ten inputs, starting with  20 ’C’ characters and incrementing one unit. This clarifies that for the Python and JavaScript implementations the time doubles when a new C is added.
Finally, in the chart seen in figure 11, it becomes visually clear what the discrepancies are between the results and places of the performances of PHP and Go side by side.

Behind the Curtains

The most commonly used algorithms to implement regular expression matching are:

• Perl-based
• NFA-based

So far, we have seen how the PHP implementation uses the PCRE, Perl-based, and Go uses the RE2. In any case, to accomplish the regular expression matching, the engine builds a Nondeterministic Finite Automaton (NFA), which is a finite state machine where for each pair of state and input symbol, there may be several possible next states. Hence, for each input symbol, the NFA will transit to a new state until all the input symbols have been consumed. This will try all paths of the NFA until it reaches an accepting state, that is, where a match occurred or all the paths were attempted but with no match.
Considering the regex ˆ(a+)+$ and its correspondent NFA:

We can use the same methodology of inputting different sizes in order to understand the NFA behavior. To this, if we choose the input aaaaX, 16 possible paths will exist in the graph from figure 12.
If we modify the input to aaaaaaaaaaX, it will have 1024 steps. And if we change it to aaaaaaaaaaaaaaaaX, 65536 possible paths will be generated. Each additional ”a” doubles this number. This behavior is an extreme case and happens because the algorithm will go through all the possible paths until failing.
What happens behind the curtains is that any time a symbol is being tested by the engine and it fails to match the next one, it will backtrack and look for another way to compile the previous symbol. If this path gets too long, the number of backtracking steps will eventually become very large, resulting in catastrophic backtracking, leading to a possible denial of service.
If we take the example of the regular expression from listing 3, and with the help from the regex101 website, we can resume this behavior in a table, where displayed is the number of steps taken for a target input string.

Table 2: PCRE (PHP) – Benchmark

From table 2, it is clear that each time we incremented the number of C’s by one unit, the engine took twice the number of steps. Using this engine from the regex101 website, if more than 998 C’s are used, it will respond with a catastrophic backtracking message:

This is the turning point between the PHP and Go implementations. In subsection 2.2, we saw that for the input used, the results in terms of elapsed time were very similar, but we did not test for extremely large inputs, as seen in figure 13, crashes the PHP implementation. This is avoided in Go.
As a matter of fact, all programming language engines (from this website) will have disastrous behaviors with this input – except for Go. JavaScript will respond with a timeout and the Python with a catastrophic backtracking. As for Go, it will resolve the string input in approximately 218ms. These results can be consulted here.
2.3.1 Easter Egg
It is also important that websites testing regular expressions can properly detect catastrophic cases:

Figure 14: Catastrophic Backtracking on Pythex
A malicious user could take advantage of the lack of validation in this website to provoke a denial of service. Another example happens in the https://www.debuggex.com/ website. When a vulnerable regular expression is used with a malicious input, it will hang the page.

Conclusion

In this blog post, we recapped what a regular expression is and how can it be leveraged to provoke a denial of service. We go through a set of examples where behaviors of different engines are shown. Specifically, we emphasize the Go behavior.
Despite possible recommendations and workarounds to avoid ReDoS, which revolve around the usual input sanitization, the best measure is to target the root cause, and so, focus on the implemented algorithm.
The implementation provided by the Go package (regexp) is guaranteed to run in time linear in the size of the input. A property that is not guaranteed by most open source implementations of regular expressions [3].

Using open source, but not sure what versions and components are in use?
Get a single holistic view of your application portfolio

References

• ReDoS, available at https://www.owasp.org/index.php/Regular expression Denial of Service – ReDoS.
• Package regexp, available at https://golang.org/pkg/regexp/.
• Regular Expression Matching Can Be Simple And Fast, available at https://swtch.com/~rsc/regexp/regexp1.html