ReDoS -正規表現でシステム停止-
この記事は、Cyber-sec+ Advent Calendar 2024の5日目の記事です。
前日の4日目は『セキュリティ若手の会』さんが2024年10月にコミュニティを立ち上げる経緯から、目指すべき方向性を書き綴っています。（スゴイ）
さて、ここからが、本題になります。
Webシステム開発に限らずですが、正規表現を業務で利用したことがある人は一定数居ると思います。 比較的よく利用されるのは指定の形式で値が入力されたかチェックするバリデーション等でしょうか。 一方、その正規表現が脆弱性になりえるという認識をもって利用している人はどの程度いるものでしょうか。 今回はReDoSという正規表現を利用した攻撃手法についてほんの少しだけ掘り下げてみました。
どのような攻撃手法なのか？
サービス運用妨害と分類される攻撃手法で（正規表現 Regular Expression）を解釈するクライアントやサーバへの DoS（Denial of Service）の組み合わせとなります。 一部の正規表現解釈方式で膨大な量のバックトラック（探索処理の一つ）が発生して処理がオーバーフローした状況を指します。
具体的には
以下の正規表現はJavaScriptで広義な意味で脆弱性があるという事になります。（連続した1つ以上の空白文字にマッチする正規表現）
/\s+$/
影響があった例
2016年6月、StackOverflowが34分間ダウン
文字列の末尾の空白を取り除く非常にシンプルな正規表現に起因
2019年7月、CloudflareがReDoSによって27分間ダウン
WAFに設定された正規表現に起因
発生する主な条件
以下の2点が発生に大きく起因するので覚えておいてください。
正規表現の解釈方式（概ね開発言語が呼び出すライブラリに依存）
組み合わせ数と入力値の長さ
正規表現の解釈方式
解釈の方法について詳細を理解するにはオートマトンという状態遷移の概念から理解する必要があるのですが、私は語れる自信が無いので割愛させていただきます。 概略としては主に以下の二つが存在しDFA型ではReDoSは発生しないそうです。
DFA型
正規表現を決定性有限オートマトン（DFA）に変換してマッチング
バックトラックを行わないため後方参照など複雑な正規表現は不可
GNU grep、Google/RE2などで採用パターン
VM型
組み合わせが爆発しないように最適化（バイトコード変換）
JavaやRubyやPerlやJavaScriptなどで採用
組み合わせ数と入力の長さ
組み合わせ数は量指定子（{n,m}）の組み方に依存し、100文字程度でも組み合わせ数によっては数秒かかります。
※『*』『+』『?』などを簡略表記と呼び、それぞれ量指定子『{0,}』『{1,}』『{0,1}』で表現できます。簡略表記を量指定子と同義で呼ぶ場合もあります。
ReDoSの発生を抑制するには
正規表現の必要性を再検討する
入力値を短くする
DFA型のエンジン（Google/RE2など）を利用する
正規表現の解釈に関わるライブラリの最新化して脆弱性を回避する
量指定子同士や量指定子とor条件（| 、 []）の組み合わせを少なくする
リソース枯渇を避けるためマッチ処理をタイムアウト制限を付ける
色々書いてますけど、結局どのような対策が必要？
まずは正規表現が本当に必要なのか要件や仕様を再検討しましょう。 その上で、どうしても必要であれば他に上記のどの抑制対策を取るのかシステムの構成にあわせて検討します。正規表現デバッガツールなどで正規表現をチェックするのも有効だと思います。
まとめ
各言語に当然のように存在する正規表現には実は複数の解釈方式があり、時として脆弱性に繋がるという事を頭の片隅にでも置いておいてください。
参考
さいごに
冒頭でコミュニティの立ち上げを紹介していましたが、私も2024年11月からSecurity.anyというコミュニティを立ち上げています。
色々なバックグラウンドの方々がセキュリティに関係ある話をして交流出来る場を、自分の知り合い含めて提供したいという思いから企画しました。
運営側を一から経験してみたかったという理由もうっすら入っています。
次回2回目が2025年1月23日となりますのでご興味がある方は是非、参加登録をお願いします。