Hatena::ブログ(Diary)

うさぎ文学日記 RSSフィード

 うさぎ文学日記甘味日記[甘味]

2011-06-29

グラボ(GPU)の力でMD5を解読

| グラボ(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」に対応していたので、以前から試してみたかったので使ってみました。

f:id:sen-u:20110629084904p:image

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」を解読してみました。文字種の指定はデフォルトの英小文字としました。

f:id:sen-u:20110629085027p:image

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

ただ、この実験が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だと言われているようです。

ハッシュと言えば、Webアプリなどでパスワードの保存に使っていると思います。その場合には、下記を対策として取り入れるようにしましょう。

  • MD5やSHA-1といった暗号アルゴリズムをSHA-2(主にSHA-256)に移行
  • saltを加えてハッシュ化することでレインボーテーブル対策
  • ストレッチ(ハッシュを1000回繰り返しかけるなど)を実施することで今回のような総当たり解読対策

その他、認証のインタフェースにはアカウントロック(10回失敗すると30分ログインできないなど)を取り入れて、オンラインからのパスワードクラックに対応する必要がありますね。


詳しい実装方法などは弊社の教育講座で学ぶことができます。もしくは徳丸本をどうぞ。

Taiyou-nekoTaiyou-neko 2011/07/01 10:09 前任者と言っても5年前ですが、誰にもパスワードを教えず居なくなったので、JohnTheRipperで4年掛けても見つからず、もう諦めて放置していたサーバーに光明の光が・・・と思ったらsalt付きハッシュ食べてくれなかった∩(・∀・)∩

sen-usen-u 2011/07/01 11:31 JohnTheRipperで4年!?

hj_saitohj_saito 2011/08/31 22:40 RADEON HD6970で「password」を解析したら40秒でした。

Found password: [password], HEX: 70 61 73 73 77 6f 72 64
Processed 190 513 676 288 passwords in 40s.
Thus, 4 881 086 220 password(s) per second in average.

sen-usen-u 2011/09/01 01:02 40秒とはさらに速いですねー。

utunutun 2012/01/20 21:55 >Taiyou-nekoさん
もしLinux系のお話だったら、レスキューCDからブートローダパスを上書きできたと思いますよ。


2003 | 08 | 09 | 10 | 11 | 12 |
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 02 | 03 | 05 | 11 |
2014 | 06 | 08 |