InfoQ

News

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
ブックマーク
digg+,
reddit+,
del.icio.us+,
dzone+,
Hatena

No comments

返信

ジャンル別一覧

ファイルシステムでHello World

この連載では"ファイルシステムの作り方"をご紹介します。第1回目の今回は簡単なイントロダクションと単純なHello Worldファイルシステムの作り方を説明します。次回以降で詳しい解説と本格的なファイルシステムの作り方をご紹介しようと思います。

Guice(ジュース)を早飲みしすぎていませんか?

あなたのチームが、既存アプリケーションを「シングルトンの入れ子」設計から依存性注入(DI)へ移行しようとしているなら、この論文に心引かれるでしょうが、DIへの移行は難しいことが分かっています。論文にはGoogleのJava DIコンテナ(Guice)の名を入れていますが、Javaや.NET、Python、Rubyなどにも当てはまります。

チームがキュービクルと引き換えにコミュニケーションスキルを得る手助けをせよ

アジャイルの「自己組織化チーム」のパラダイムでは、チームのメンバに新しいスキルが要求されます。この記事では、発展しつつあるチームの自己組織化を壊さずに、新たなスキルを伝えるためのいくつかの戦略を提案します。そして、新しいスキルを身につけるのに役立つ資料のありかを提示しています。

F#の土台を越えて - 非同期ワークフロー

今回の記事では、非同期ワークフローと呼ばれるワークフロー機能の面白い使用法を考察しますが、非同期ワークフローは.NETの非同期プログラミングモデルを単純化することを目的としています。

言語としてのアーキテクチャ: ストーリー

アーキテクチャは一般に、Word文書に主として見られるような極めて実体のない、ソフトウェアシステムの概念的な側面であるか、または完全に技術によって駆動されるものかのいずれかです。そのどちらも間違っています。では、どう対処すればよいでしょうか? この記事ではアイデアを説明します、そしてアプローチのキーポイントを要約します。

メタプログラミングを使ってRubyにプロパティを追加する

Werner Schuster氏が、簡単な例を示しながら、Javaのようなプロパティをメタプログラミングを使ってRubyに追加する方法を示します。

BlazeDSとAMFでWebとデスクトップのアプリケーションを構築する

現在のRIAアーキテクチャにおいて、クライアント/サーバーの通信は重要な位置を占めています。本稿では、James WardとShashank TiwariがアドビによるオープンソースのBlazeDSメッセージングサーバーの世界へ飛び込みます。

業務ソフトに手を加えずに暗号化を実現する~秘文の挑戦~

hibun

ウィルス対策ソフトや情報漏えい防止用のソフトは、いわば影の存在です。ユーザの操作性やGUIを工夫する以上に、いかに目立たない存在となるかにその技術を注ぎ込んでいます。ここでは日立ソフトが開発した「秘文」の事例を紹介します。