前のエントリでStackExchangeがReDoSで攻撃されサイトがダウンした問題を紹介しました。少しだけ掘り下げて見たところ、正規表現だけでメールアドレスをチェックしている場合、壊滅的なReDoS（十分短い文字列で指数関数的に実行時間が増加する）が可能なことが判りました。

結論を書くと、正規表現でのメールアドレスチェックは見直すべき、です。（特にRubyユーザー）

追記：影響範囲はメールアドレスチェックに限らないので、正規表現チェックは全体的に見直さないと、どこが脆弱なのか判りません。見直してチェックしたとしても、それが完全であったと保証することは困難です。ネット検索して直ぐに見つかった検索パターンは非常に脆弱であったこと、メールアドレスのマッチパターンは脆弱になりやすい繰り返しの繰り返しが含まれること、これらがあったのでタイトルが「正規表現でのメールアドレスチェックは見直すべき 」になっています。

ReDoSとは？

ReDoSとは正規表現のアルゴリズムを利用してDoS攻撃を行う攻撃です。ReDoSは新しい脆弱性ではありません。10年以上前から知られており、一部のパターンには対策が行われています。しかし、正規表現の仕組み上、完全に対応することはかなり難しいと思われます。実際、StackExchangeは攻撃されました。

PCRE（PHPだとpreg関数）にはバックトラック制限／スタック制限などの対策が取り入れられていますが、前のエントリで紹介したReDoSのように完全に対応するまでには至っていません。

壊滅的ReDoSが可能な正規表現の例

送信されたメールアドレスが妥当な物であるか、チェックするために正規表現を利用している場合は多いです。以下の正規表現はOniguruma（PHPの場合、mb_ereg関数。Rubyなどでも利用されている）の場合に壊滅的なReDoSが可能なパターンです。

\A([\w+\-].?)+@[a-z\d\-]+(\.[a-z]+)*\.[a-z]+\z

（注意：PHPの場合、^、$で文字列の先頭、末尾にマッチします。処理系によっては\A、\zを利用しなければなりません）

テストスクリプト

Rubyスクリプトですが、PHPでもmb_ereg関数はOnigurumaを使っているので同じです。¹ RubyはFedora 24 x86_64のRuby 2.3.1を利用しました。CPUはCore i7 4770Sなので爆速ではありませんが、遅いCPUでもありません。

n = 5;
while n < 12 do
  s = "username@host"+".abcde"*n+"."
  start = Time.now();
  p /\A([\w+\-].?)+@[a-z\d\-]+(\.[a-z]+)*\.[a-z]+\z/i =~ s
  p s.length.to_s + ': ' + (Time.now() - start).to_s;
  n += 1
end

これを実行するとメールアドレスっぽい文字列の長さ（ペイロード）と正規表現の実行時間を出力します。

ペイロード（攻撃文字列）と実行時間の変化

スクリプトの実行結果は以下の通りです。

[yohgaki@dev ruby]$ time ruby ~/t1.rb
nil
"44: 0.027311876"
nil
"50: 0.132008062"
nil
"56: 0.659123669"
nil
"62: 3.302718201"
nil
"68: 16.69595179"
nil
"74: 84.285386539"
nil
"80: 421.913505251"

real    8m47.431s
user    8m47.041s
sys 0m0.364s

PHPのOnigurumaはこのパターンでは脆弱ではありませんでした。Rubyのバージョンによっては、ReDoSに脆弱だったり、脆弱でなかったりするかも知れません。

まとめ

100文字以内でとんでもない実行時間が必要となり、80文字で421秒（7分）、6文字ペイロードが増えると実行時間が約5倍になっています。実行時間が指数関数的に激増していることがわかりました。RFC2821通りにするなら”64バイト@255バイト”の文字列まで受け入れなければなりません。300文字で攻撃したら1日経ってもこの正規表現マッチは終わらないでしょう。

結論としては、メールアドレスチェックは正規表現ではなく、去年の9月のReDoSの回避に書いた通り、文字列を分解してチェックするなどの対策を行うべき、になります。

ReDoSを回避する正規表現を考えることも可能ですが、回避したと思っていても、また別の攻撃パターンが見つかるかも知れません。正規表現エンジンのバージョンが変ると攻撃パターンが変るかも知れません。あれこれ考えるよりCERTトップ10セキュアコーディング習慣の第4位の「簡易にする」（この場合、文字列を分解して簡単な処理にする）を採用する方が良いでしょう。

PHPの場合、PCREも使えます。PCREの場合、バックトラック制限／スタック制限があり、Onigurumaのmb_ereg関数よりReDoSに対して強いです。しかし、StackExchangeの攻撃に使われた文字列の場合は効果がありませんでした。PCREを利用している場合も、文字列の繰り返しマッチを繰り返す（これに限らない方が良いですが。。）ような場合は、文字列を分割してからバリデーションするといった処理にした方が安全です。正規表現でなくても済むなら使わない、も対策になります。

攻撃はメールアドレスにマッチする正規表現に限りません。複雑な正規表現より、文字列を分割し、単純な正規表現を使うように心掛けないとリスクが残ります。解った上でリスクを取る（増やす）のもセキュリティ対応（セキュリティ対策）の１つなので、絶対にしてはならない、とまでは言いません。

追記:

無精せずにPHPでも実験してみました。

<?php
#$re = '^\\w+([-+.\']\\w+)*@\\w+([-.]\\w+)*\\.\\w+([-.]\\w+)*

実行結果

[yohgaki@dev github-php-src]$ php t3.php 
int(1)
bool(false)
0.011868953704834 PCRE Done
bool(false)
0.00066494941711426 Oniguruma Done

PCREがFALSEを返すのは予測通り²ですが、PHPの古いOnigurumaはこの攻撃に脆弱ではありませんでした！Onigurumaをいつバージョンアップするか分らないですし、PCRE含め³、どのバージョンがどのパターンに脆弱か判らないということになります。転ばぬ先の杖（＝セキュアプログラミング／セキュアコーディング／防御的プログラミング）が役に立ちます。

• CERT Top 10 Secure Coding Practices
• OWASP Secure Coding Practices – Quick Reference Guide

;
$re = ‘\A([\w+\-].?)+@[a-z\d\-]+(\.[a-z]+)*\.[a-z]+\z’;

var_dump(preg_match(‘/’.$re.’/’, ‘yohgaki@ohgaki.net’));

$s = ‘usr@dom’.str_repeat(‘.abcde’, 1000).’.’;

$start = microtime(true);
var_dump(preg_match(‘/’.$re.’/’, $s));
echo microtime(true) – $start .’ PCRE Done’.PHP_EOL;

$start = microtime(true);
var_dump(mb_ereg($re, $s));
echo microtime(true) – $start .’ Oniguruma Done’.PHP_EOL;
実行結果

PCREがFALSEを返すのは予測通り²ですが、PHPの古いOnigurumaはこの攻撃に脆弱ではありませんでした！Onigurumaをいつバージョンアップするか分らないですし、PCRE含め³、どのバージョンがどのパターンに脆弱か判らないということになります。転ばぬ先の杖（＝セキュアプログラミング／セキュアコーディング／防御的プログラミング）が役に立ちます。

• CERT Top 10 Secure Coding Practices
• OWASP Secure Coding Practices – Quick Reference Guide