正規表現を使ったDoS – ReDoS

(Last Updated On: 2018年8月8日)

いつかは忘れるくらい前に正規表現のアルゴリズム自体を利用してDoS攻撃を行うReDoSが発表されていました。今まであまり気にしていなかったのですが、検索しても日本語のページが出てこないようでした。詳しく知るためのリンクなどを紹介します。

少し検索して出て来た日本語ページはHPのページでしたが、たまたまインデックスされていたページがヒットしたようでした。また記載されている情報は不十分でした。(ページ下のコピーライトからFortifyの情報のようです)

日本語のページで良いものは無いようなので、ReDoSの英語ページ/PDFを紹介します。

3つ目のCHECKMARXのPDFは解りやすいと思います。OWASPのページはCHECKMARXの資料が元になっているようです。攻撃可能な正規表現のパターンと攻撃文字列が載っています。

Evil Regex pattern examples

  1.  (a+)+
  2.  ([a-zA-Z]+)*
  3.  (a|aa)+
  4.  (a|a?)+
  5.  (.*a){x} | for x > 10

Payload: “aaaaaaaaaaaaaaaaaaX”

危険性がある正規表現は

  • オーバーラップがある正規表現
  • 繰り返しのネストがある正規表現

とされています。上の”Evil Regex Pattern Example”の正規表現はこの条件を満たしています。

対策も書かれており

  • ReDoS脆弱性は非常に大きな問題であり、我われは検出/防止しなければならない
  • 動的に生成した正規表現は使わない、もしくは適切なサニタイズを行って利用する
  • どのような正規表現もReDoSに脆弱でないか使用する前に確認する
  • 動的な正規表現テストツール、静的な正規表現検査ツールの開発が必要

としています。CHECKMARXは静的なコード検査ツールを販売しているメーカーなので、自社ツールにも入れるのかも知れません。CHECKMARXは今年評価したのですが、評価に利用したコードについてはReDoS脆弱性は検出していませんでした。

どのくらいの性能劣化なのか?はDZoneのRegular Expressions Denial of the Service (ReDOS) Attacks: From the Exploitation to the Preventionに記載されています。

RANDOM STRING CHARACTER LENGTH ELAPSED TIME (MS)
360817709111694! 16 16ms
2639383945572745! 17 23ms
57994905459869261! 18 50ms
327218096525942566! 19 106ms
4700367489525396856! 20 207ms
24889747040739379138! 21 394ms
156014309536784168029! 22 795ms
8797112169446577775348! 23 1595ms
41494510101927739218368! 24 3200ms
112649159593822679584363! 25 6323ms

といった感じで簡単にCPU時間を使い切ってしまいます。

日本語の紹介/解説ページが無かったようなので簡単に紹介しました。

 

投稿者: yohgaki