グラボ(GPU)の力でMD5を解読 - うさぎ文学日記

CPUではなく、グラフィックボードに搭載されているGPUの力を使って、MD5やSHA-1などのハッシュ値を解読するというのを試してみました。
きっかけはPCの刷新。ゲームなどはしないので、DUAL DVI-Iが付いていれば何でもいいやと思って「VAPOR-X HD 5770 1G GDDR5 PCI-E DUAL DVI-I/HDMI/DP OC Version」というカードを13,980円で購入。
このATI HD5770が、GPUを使ってハッシュ値をブルートフォースで解読する「IGHASHGPU」に対応していたので、以前から試してみたかったので使ってみました。

IGHASHGPUのダウンロードはこの辺りから

IGHASHGPU

今回使ったのは、IGHASHGPU v0.93.17.1。解読できるのは以下のアルゴリズムなどです。

Plain MD4, MD5, SHA1（なぜかまだ主流のハッシュたち）
NTLM（XP時代以前のWindows系の認証）
Domain Cached Credentials
Oracle 11g
MySQL5
MSSQL
vBulletin（海外で有名な掲示板）
Invision Power Board（海外で有名な掲示板）

基本的な使い方は以下の通り。

-t:[type] 解読するハッシュのタイプ
-h:[hash] 解読したいハッシュ値（16 or 20 bytes）
-c:csdepa 使用されている文字 (caps, smalls (default), digits, special, space, all)
-max[value] 最大文字長

複数解読したい場合にはファイルで指定したりなど、他にオプションはありますが、IGHASHGPU v0.90辺りを参考に。

テスト1:"password"

パスワード人気ランキングで常に上位にいる「password」という文字列をMD5でハッシュ化した「5f4dcc3b5aa765d61d8327deb882cf99」を解読してみました。文字種の指定はデフォルトの英小文字としました。

c:\> ighashgpu.exe -h:5f4dcc3b5aa765d61d8327deb882cf99 -t:md5 -c:s -max:8
（略）
Found 1 CAL device(s)
Starting brute-force attack, Charset Len = 26, Min passlen = 4, Max passlen = 8
Charset (unicode -> 0) [abcdefghijklmnopqrstuvwxyz]
Charset in HEX: 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70 71 72 73 74 75 76 77 78 79 7a
Starting from [aaaa]
Hash type: MD5, Hash: 5f4dcc3b5aa765d61d8327deb882cf99
Device #0: [Juniper] 860.00 Mhz 800 SP
Hardware monitoring enabled, threshold temperature is 90°C.
CURPWD: umggwqur DONE: 87.12% ETA: 14s CURSPD: 1842.9M
Found password: [password], HEX: 70 61 73 73 77 6f 72 64
Processed 190 350 098 432 passwords in 1m 34s.
Thus, 2 034 328 660 password(s) per second in average.

1分34秒であっさりと解読できてしまいました。1秒で約20億回も試行してるんですね。

少し前の資料ですが、下記のIPA資料の「使用できる文字数と入力桁数によるパスワードの最大解読時間」という表によると、「OS：Windows Vista Business 32bit版、プロセッサ：Intel Core 2 Duo T7200 2.00GHz、メモリ：3GB」という環境で、英字8桁を解読するのに最大約17日掛かるそうです。Core i7とかならもう少し速いかもしれませんが、それでも1分34秒というわけにはいかないでしょう。

情報処理推進機構：情報セキュリティ：ウイルス・不正アクセス届出状況について（2008年9月分および第3四半期）

ただ、この実験がMD5のハッシュ値を解読しているのかどうか知りませんけど…。

テスト2:英小文字＋数字8桁

個人的によく使っているパスワード生成ツールで、英小文字＋数字で生成した8文字「6xi2qmgo」をMD5でハッシュ化した「8872d71d1f938345ba79e984e433fecd」を解読してみました。文字種の指定は英小文字＋数字としました。

c:\> ighashgpu.exe -h:8872d71d1f938345ba79e984e433fecd -t:md5 -c:sd -max:8
（略）
Found 1 CAL device(s)
Starting brute-force attack, Charset Len = 36, Min passlen = 4, Max passlen = 8
Charset (unicode -> 0) [abcdefghijklmnopqrstuvwxyz0123456789]
Charset in HEX: 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70 71 72 73 74 75 76 77 78 79 7a 30 31 32 33 34 35 36 37 38 39
Starting from [aaaa]
Hash type: MD5, Hash: 8872d71d1f938345ba79e984e433fecd
Device #0: [Juniper] 860.00 Mhz 800 SP
Hardware monitoring enabled, threshold temperature is 90°C.
CURPWD: 46q4qmmk DONE: 45.39% ETA: 13m 17s CURSPD: 1930.9M
Found password: [6xi2qmgo], HEX: 36 78 69 32 71 6d 67 6f
Processed 1 361 332 666 368 passwords in 12m 5s.
Thus, 1 878 472 346 password(s) per second in average.

先ほどよりは時間が掛かりましたが、それでも12分5秒ですね。

テスト3:英大小文字＋数字8桁

先ほどのパスワード生成ツールで、英大小文字＋数字で生成した8文字「6XAuiIWx」をMD5でハッシュ化した「d8ce39bdbcc84415218a31ca2bfb91be」を解読してみようとしました。

c:\> ighashgpu.exe -h:d8ce39bdbcc84415218a31ca2bfb91be -t:md5 -c:scd -max:8

が、寝る前にセットして6時間ほど動かしたところ、起きたら残り19時間だったので、そこで止めました。

他のテスト

SHA-1とsalt付きハッシュ値を試そうと思ったのですが、SHA-1は「ERROR12: Kernel unimplemented. With v0.90 GPU algorithms were seriously changed and not all kernels updated yet.」というエラーが出て、saltは「-salt」というオプションがどうも動かないようで…。
使い方が間違えているのか、環境が悪いのか。

まとめ

MD5はレインボーテーブルを使うまでもなく、家庭用のグラボのGPUで解けるレベルだということですね。
そして、IGHASHGPUの説明書を見てみると、SHA-1もその3倍ぐらいの時間で解けるみたいなので、強度的には強いと言えなさそうですね。

ATI HD5870:
~3650M/s single MD5
~1360M/s single SHA1

今後10年安心して使うことができる暗号アルゴリズムという観点で選ばれている、電子政府推奨暗号リストは2003年にできたので後2年ほどで寿命切れ。これにはMD5は当然載っていなくて、SHA-1も米国が2010年で使わないと選択したので、日本でも改訂版のリストにも載らない予定。さらに2017年度にはSHA-1も利用停止予定です。
今選ぶのであれば、SHA-2（SHA-224、SHA-256、SHA-384、SHA-512）でしょう。（SHA-3は2012年に選定予定）
米国だとSHA-1の代わりに使うのは、SHA-256だと言われているようです。