この記事では、最初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要素を用いて、スクリプトを複数の窓で開き、同時に動作させることにしました。
これを呼び出す親画面は下記の通り。元エントリと同じで、パスワード567890に対するソルトつきハッシュ値hoge$4b364677946ccf79f841114e73ccaf4fを解読しています。<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>
実行結果は以下の通りです。各リクエストが同時に動いていることを示すために、Google ChromeのTimelineを示します。実行時間は250msec程度ですね。<body> <iframe src="crackhash.php?start=0&step=4&salt=hoge&hash=4b364677946ccf79f841114e73ccaf4f" height="50"></iframe> <iframe src="crackhash.php?start=1&step=4&salt=hoge&hash=4b364677946ccf79f841114e73ccaf4f" height="50"></iframe><br> <iframe src="crackhash.php?start=2&step=4&salt=hoge&hash=4b364677946ccf79f841114e73ccaf4f" height="50"></iframe> <iframe src="crackhash.php?start=3&step=4&salt=hoge&hash=4b364677946ccf79f841114e73ccaf4f" height="50"></iframe> </body>
ということで、100万件程度では、ソルトつきMD5ハッシュでは守れないと言うことですが、それならSHA-512等ではあれば守れるかというと、実は守れません。この理由については、稿を改めて説明したいと思います。
100万件ぐらいなら、あらかじめDBに入れておけばいいじゃない。
返信削除匿名さん、こんにちは。
返信削除DBに入れておく方法は、Saltがない場合か、Saltが固定の場合です。この問題の場合は、Saltは可変としていますので、あらゆるSaltを想定してDBを作ることができません。そのため、都度総当たりで求めています。