パスワードはいつまで持つか

安全性について知っておくべき事(yohgaki's blog)
セキュメモ経由。PS3も大変ですがもっと大変なのはDirectX10世代のGPUですよ。
参考:Elcomsoft Debuts Graphics Processing Unit (GPU) Password Recovery Advancement(Symantec)
要はGPUってのは最近プログラマブルシェーダに対する要求が強くなって進化してきた結果、いきなり数百GFflops級の演算能力を持つコプロセッサとして使えるようになったのです。それをHPC業界の人はGPGPUなんて言葉でうれしがって使ってるんですが(そしてそれは大変ありがたくうれしいのですが)セキュリティ業界にとっては別のインパクトがあるよという話。
Schneierさんはそんなの今更だよというけど、私は甘いと思います。AccessDataのPRTKやDNAがよくできているのは認めるけどこのインパクトは性質が違うのでは。
GPUはCPUよりはるかに速い伸びで演算速度が上がってきた。CPUと違って単純な並列化で速度が上がるのでプロセス微細化が進む限り性能は上がる。HDエンコード/デコードやGPGPUなどによるニーズとうまくマッチして市場性が確保されている間は、近いうちにあと1ケタ、もしかしたら2ケタは十分性能がのびる「伸びしろ」がある。これによって今クラック速度がCPUの25倍といってるものが近い将来2500倍になってもおかしくない(あくまで今のCPU比です念のため)。
それでもセキュリティ的にはたかだか2ケタかもしれない。でも問題はHDDも猛烈な速度で容量が上がっている点(年2倍ペース)。これは、「ハッシュに関して総当り後の結果を溜め込んでおいて表引きする」、いわゆるRainbow Table(Wikipedia)がどんどん実用になることを意味する。いまophcrackなんかでLM hashが使い物にならなくなってしまったのはよく知られているけど(参考はこちら)、LM hashがバカなのはパスワード14文字といいながら実質7文字×2でsaltも固定なので探索空間が格段に狭いことにある。でも逆に言えば7文字の(ほぼ)全解探索はもう終わっている。8文字にしたって英小文字+数字8文字のMD5のRainbow Tableはたかだか36GBで作れている(参考)。Rainbow Tableは作り方で大きさが変わるから一概に言えないけど、8文字くらいまでの(ほぼ)全解探索後の表を個人で持てる時代はそんなに遠くないように思う。Time-space tradeoffをもう少し突き進めれば、9とか10とかでも現実的な数字だろう。10いけるとsaltを含めて10文字の古いDES式crypt passwordはおしまいだ。
ただし表を持つには誰かが全解探索しないといけない。それが今まで難しかったのが、GPUの進化やPS3の普及でぐっと楽になるだろう。いままで分散でチマチマやっていた人々には大変な朗報かもしれない。
ここにbotnetなんてのが加わると、ワルい人たちにとってパズルのピースが全部そろっちゃってる気がするのは私だけなんでしょうかね。