2014年2月10日月曜日

数字6桁パスワードのハッシュ値の総当たり、PHPなら約0.25秒で終わるよ

JALの6桁数字パスワード問題から派生して、JALのサイトがパスワードリマインダとして「現在のパスワード」を教えてくれることから、JALサイトではパスワードを平文保存しているのではないかという疑惑が持ち上がっています。それに対して、「いやいや、従来の主流と思われるソルト付きMD5ハッシュでの保存しても、実用的な速度でハッシュ値から元パスワードを『解読』できるよ」と、JALを擁護(?)するエントリが現れました。
この記事では、最初Clojureによる単純な総当たりで36秒、Clojureのreducersによる並列化で11秒でハッシュ値から元パスワードが求められるよ、と説明されています。まことに痛快な記事ですので、未読の方には一読をお勧めします。

とはいうものの、100万件のMD5の総当たりが、逐次実行で36秒、並列化して11秒という数字は、ちと遅すぎるように感じました。拙著「体系的に学ぶ 安全なWebアプリケーションの作り方」では以下のように書いているからです。
(md5bruteによる英小文字8桁パスワードのMD5ハッシュ値の総当たりが)Pentium Dual-Core 2GHzの1コアのみ使った実験で、約40時間で探索に成功しています。1秒あたり138万個のハッシュ値を計算していることになります。
ということで、PHPで試してみると、100万件の総当たりでは 0.8 秒程度でした。マシンスペックは、偶然ながら @kawasima さんの検証と同じ「Corei7-4770 Windows 7 」です。

PHPはマルチスレッドのプログラミングをサポートしていないので上記はシングルスレッドでの実行ですが、PHPでも並列実行できる方法はないかと考えてみたところ、PHPなのだからWebでやろうと思い立ちました。iframe要素を用いて、スクリプトを複数の窓で開き、同時に動作させることにしました。
<body>
<?php
$hash = $_GET['hash'];
$salt = $_GET['salt'];
$start = (int)$_GET['start'];
$step = (int)$_GET['step'];

$t0 = microtime(true);
for ($i = $start; $i < 1000000; $i += $step) {
  $pass = sprintf('%06d', $i);
  if (md5($salt . '$' . $pass) === $hash) {
    $time = microtime(true) - $t0;
    echo "Solved: $pass $time<br>\n";
  }
}
$time = microtime(true) - $t0;
echo "done: $time<br>\n";
?></body>
これを呼び出す親画面は下記の通り。元エントリと同じで、パスワード567890に対するソルトつきハッシュ値hoge$4b364677946ccf79f841114e73ccaf4fを解読しています。
<body>
<iframe src="crackhash.php?start=0&amp;step=4&amp;salt=hoge&amp;hash=4b364677946ccf79f841114e73ccaf4f" height="50"></iframe>
<iframe src="crackhash.php?start=1&amp;step=4&amp;salt=hoge&amp;hash=4b364677946ccf79f841114e73ccaf4f" height="50"></iframe><br>
<iframe src="crackhash.php?start=2&amp;step=4&amp;salt=hoge&amp;hash=4b364677946ccf79f841114e73ccaf4f" height="50"></iframe>
<iframe src="crackhash.php?start=3&amp;step=4&amp;salt=hoge&amp;hash=4b364677946ccf79f841114e73ccaf4f" height="50"></iframe>
</body>
実行結果は以下の通りです。各リクエストが同時に動いていることを示すために、Google ChromeのTimelineを示します。実行時間は250msec程度ですね。


ということで、100万件程度では、ソルトつきMD5ハッシュでは守れないと言うことですが、それならSHA-512等ではあれば守れるかというと、実は守れません。この理由については、稿を改めて説明したいと思います。