160秒で可能-Rainbow Hash Crackingを用いたパスワード解除

作者 Gavin Terrill , 翻訳者 編集部 投稿日 2007年9月13日 午後11時32分

コミュニティ

.NET,

Java,

Ruby,

Architecture

トピック

セキュリティ

Jeff Atwood氏が最近"Rainbow Hash Cracking"(source)というパスワードを解除するための技術に関する記事を書いた。その技術は辞書攻撃の変型であるが、事前に算出されたハッシュ値に対する テーブルルックアップを行う迅速な検索メカニズムに依存している。Jeff氏はパスワードが絶対にプレーンテキストに保存されるべきではないことを指摘し、パスワードストレージランドスケープを検査するのから始めた。

パスワードは絶対にプレーンテキストに保存されるべきではない。少なくとも世界で一番世間知らずのプログラマーを使用して世界で一番無用心なシステムを構築していない限り、そうするべきでない。代わりにパスワードはハッシュ機能の出力(source)として保存される。ハッシュは1方向型の動作である。もしアタッカーがあなたの細切れのパスワードを手に入れたとしても、ハッシュ値のみでそのパスワードを再構築することはできないのだ。

Rainbow Tableの技術はとても大きなテーブルの作成時間を削ってハッシュ値を事前に算出するものだ。

しかしながらレインボーテーブルを使ってパスワードのハッシュ値を攻撃するのは不可能なのだ。レインボーテーブルとは、存在し得る全ての文字のコンビネーション用の事前に算出された巨大なハッシュ値の集合体である。PCの攻撃は確実にオンザフライのハッシュ値を算出するが、攻撃マシンがメモリ内にテーブル全体を保存できるのに十分なRAMを備えていることを想定すると、事前に算出された巨大なハッシュ値を上手く生かしてすさまじい速さのオーダーを遂行するための攻撃を行うことができる。

Windowsのパスワード解読ソフトであるOphcrack(サイト・英語)はRainbow Tablesのテクニックを使用している。JeffはWinsows XPに組み込まれている5つのパスワード中二つを3分以内で見つける事が可能なophcrackに付いてくる最小のテーブルを使用することができた。この テーブルには混合された文字と数字が含まれており（約800億のハッシュ値）、Windows LanManagerのパスワードを99.9％の確率で解読することができるのだ。JeffはLMハッシュ値のサポートはRainbow Table攻撃の影響を受けやすい初期のマイクロソフト暗号化メカニズムはデフォルトでは無効となっていたという助言をしている。

私はレガシーのLan Managerサポート機能がWindows Server2003においてデフォルトで有効になっていることに驚愕した。Lan Manager値を無効にし(source)、特にユーザーのドメインクレデンシャルを保存することになったWindowsサーバでそれを行うことが大切だ。

LM Hashは"salt"を暗号化プロセスに取り込む今日の一般的なメソッドを使用していないのでこの種の攻撃に弱いのだ。暗号化されたパスワードが saltを使用していなければ、それはプレーンテキストパスワードを見つけるために比較的逆ルックアップを行うのは簡単なのである。

しかしながらリモートハッカーがサーバーかデータベースから巨大なハッシュ値のパスワードリストを手にいれたら問題なのである。レインボーアタックテーブルからの攻撃には多大なリスクがあるのだ。だからハッシュのみに頼るべきではないのである。いつもsaltをハッシュにいくつか付け加えてハッシュ値をユ ニークに保つのが大切なのである。

"salt"はパスワードと連結してハッシュ機能にインプットとして使われているランダムなビットからなっており、リスクを2方向で減らす。

• ハッシュ値の長さを増やしテーブルを生成するのに使われる文字セットの一部ではない文字を潜在的に追加する。
• それぞれのパスワードに対してユーザーによって異なるsaltとして別のRainbow Tableが必要となる。

この二つの要素は一つ一つのパスワードを解読するのにすさまじい時間をかけさせる。Jeffの記事の続きとしてThomas Ptacek氏が”Rinbow Tableはもう十分だ。パスワードスキームを管理するのに知っておくべきこと”(source)においてパスワード解読を失敗させるキーはbcrypt(source)のような比較的ゆっくりとした暗号化アルゴリズムを使うことなのだと指摘している。

どうしてそれがそんなに成功するのでしょうか？サーバと攻撃者の2方向からその問題を考えてみましょう。

まず始めにサーバです。一時間に何十何千かもしくは一秒に何十ものログインがあります。データベースヒットとページリフレッシュのIOと比べるとパスワードのチェックは無視することが可能なのです。パスワードテストが2倍もしくは10倍の長さがかかっても気になりません。なぜならパスワードのハッシュ値は20/80の法則のhot spotにはないからです。

次は攻撃者です。これは簡単です。攻撃者はパスワードテストに2倍の時間がかかったらだめなのです。もし一つのテストに2倍の時間がかかったら全体のパスワード解読の時間も2倍かかってしまうからです。

Jeffはレインボーテーブルアタックからパスワードを保護する方法はパスワードをsaltすることだと述べている。

原文はこちらから：http://www.infoq.com/news/2007/09/rainbowtables

• 次へ >