正規表現でのメールアドレスチェックは見直すべき – ReDoS

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

前のエントリで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を使っているので同じです1 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を利用している場合も、文字列の繰り返しマッチを繰り返す(これに限らない方が良いですが。。)ような場合は、文字列を分割してからバリデーションするといった処理にした方が安全です。正規表現でなくても済むなら使わない、も対策になります。

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

 

追記:

無精せずに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を返すのは予測通り2ですが、PHPの古いOnigurumaはこの攻撃に脆弱ではありませんでした!Onigurumaをいつバージョンアップするか分らないですし、PCRE含め3、どのバージョンがどのパターンに脆弱か判らないということになります。転ばぬ先の杖(=セキュアプログラミング/セキュアコーディング/防御的プログラミング)が役に立ちます。


  1. 同じかと思っていましたが古いOnigurumaの方が脆弱でなかったです。どのパターン、どの正規表現エンジンで攻撃できるか、判別するのは結構難しいようです。たまたま連続して攻撃可能なパターンと環境を見つけていたようです。 
  2.  preg_matchはマッチした数を返すので、マッチしない場合は0を返す。 
  3. 末尾直前の複数文字にマッチするパターンの場合、PHP 5.6のPCREはクラッシュしてしまいました。PHP 7.1-devのPCREはクラッシュせず実行時間が長くなりました。PCREもバージョンによって動作が異ることが結構あります。 

;
$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を返すのは予測通り2ですが、PHPの古いOnigurumaはこの攻撃に脆弱ではありませんでした!Onigurumaをいつバージョンアップするか分らないですし、PCRE含め3、どのバージョンがどのパターンに脆弱か判らないということになります。転ばぬ先の杖(=セキュアプログラミング/セキュアコーディング/防御的プログラミング)が役に立ちます。


  1. 同じかと思っていましたが古いOnigurumaの方が脆弱でなかったです。どのパターン、どの正規表現エンジンで攻撃できるか、判別するのは結構難しいようです。たまたま連続して攻撃可能なパターンと環境を見つけていたようです。 
  2.  preg_matchはマッチした数を返すので、マッチしない場合は0を返す。 
  3. 末尾直前の複数文字にマッチするパターンの場合、PHP 5.6のPCREはクラッシュしてしまいました。PHP 7.1-devのPCREはクラッシュせず実行時間が長くなりました。PCREもバージョンによって動作が異ることが結構あります。 

投稿者: yohgaki