Regex-enabled search could become a vulnerability for systems, as a Japanese security researcher revealed a new theoretical exploit that allows the forced extraction of data from web applications. The researcher, Takashi Yoneuchi of the University of Tokyo’s Department of Information Science, refers to this threat as “blind regular expression attacks.”

Yonueuchi presented his findings during the OWASP Night 2020/02 event in Tokyo. This was not the result of a targeted study, but the outcome of his occasional research on blind regex injection. His study explored the idea of “algorithmic complexity attack” in possibly forcing apps to reveal delicate information by building on established security research on regex injection.

From DoS to Injection

Web applications employ a search engine function that uses regular expressions (regex) that enable users or app developers themselves to set search pattern definitions. This reliance on a regex engine makes web apps prone to a denial-of-service attack capable of overwhelming the said engine. The attack is called ReDoS or regular expression denial-of-service.

According to Yoneuchi, cybercriminals may take the ReDoS attack to another level by using regular expression injection. This novel attack vector exploits the system limitations in relation to regex implementations by subjecting them to extreme situations. Cybercriminals can induce such extreme conditions by introducing specially crafted codes.

This attack has an aspect that is comparable to SQL injection, blind or inferential SQLI in particular. It obtains information using true or false questions. The answer is determined depending on the response of the attacked database. A popular way to find out if the attack succeeded is to employ an SQL sleep command, which causes a delay within the application.

Yoneuchi’s blind regex injection outlines a method that allows cybercriminals to force a web application to give away sensitive information by combining the approaches involved in ReDoS and SQL injection. Attackers don’t necessarily launch a succession of ReDoS and regex injection attacks. What happens is that they attempt to reveal supposedly private or restricted information based on a time delay observed when executing a regular expression after discovering vulnerabilities arising from protections used against denial-of-service attacks.

This attack may not yield the kind of information and control using other techniques like cross-site request forgery, which allows the attacker to make purchases or fund transfers, but it manages to extract criminally useful details out of servers.

It’s worth noting that regex injection is possible because of the “backtracking” feature in databases that allow regular expression searches. This same feature is what attackers exploit when launching ReDoS attacks. The difference in the former is that evaluating the response is based on a timeout.

How It Works

Yoneuchi wrote a technical blog post to explain this new attack in great detail. Here’s a summary of the example the security researcher used to elaborate on how the scheme works.

• A sample application that has a timeout for evaluation of regular expressions was selected.
• The researcher used a payload with a definite response time (two seconds) if SECRET (the information that will be obtained) matches R (the regular expression). The response will be less if they don’t match.
• Regex injection is used to determine whether or not an arbitrary regular expression matches SECRET. For example, it is possible to reveal the length of SECRET by testing the response time for ^(?=.{1})((.*)*)*salt$, ^(?=.{2})((.*)*)*salt$ etc.
• The value of SECRET is determined by examining the nth character of SECRET, checking if it is c or not for all instances of n in [1, len(SECRET)] and c in possible characters in SECRET. 

Based on the example above, blind regex injection is similar to Cross-Origin State Inference (COSI) attacks. Also known as XS Leaks, these are a group of side-channel attack methods that also use network timing to infer and collect information about users.

Yoneuchi reckons that the new technique he discovered imperils search features that make use of regular expressions. A web application similar to Weibo, for example, that enables searching of tweets through regular expressions can be forced to reveal posts made by accounts that are supposed to be private or protected. This can happen if the web app’s database features backtracking engines and comes with the ability to stop ReDoS attacks through timeouts for regular expression evaluation.

Theoretical for Now

There have been no documented cases yet of this novel method used in actual attacks. The mechanisms are still theoretical, and there have been no working exploits identified for now. The researcher is reportedly working on exploits for real-world applications to test if the method can indeed create the kind of outcomes described.

Other security researchers are encouraged to work on the information presented in the research as Yoneuchi believes that blind regex injection can become a powerful cyberattack approach. The crafting of a ReDoS payload with an attacker-controllable ceiling for the number of backtracking, in particular, can result in a viable new attack vector. Timeouts appear to be the stumbling block for the full development of this threat. In the absence of timeouts, attackers need to control the time it takes to evaluate regular expressions meticulously for them to make sense of the responses they get from the targeted databases.

The Takeaway

The common solution for preventing ReDoS, ironically, is what creates a vulnerability that allows blind regex injection attacks to happen. Fortunately, this novel cyberattack method is still a concept. There’s ample time for security researchers to find ways to counter it or develop solutions that would prevent future incidents based on this technique. The recommended solution is to develop non-backtracking engines to mitigate ReDoS threats. While it’s important to address denial-of-service threats, it’s also necessary to make sure that the solution implemented does not open another potential problem.