Ophcrack による解析

セキュリティ

Windows 用のパスワード解析ソフトというと、Ophcrack が有名です。CD ブートさえ出来れば、ほぼ自動的に解析してくれます。

ただ、Ophcrack の解析は、Rainbow Table に大きく依存しているところがあります。

前回(id:JULY:20100515)、脚注で Rainbow Table に付いて少し触れましたが、もう少し詳しく書いてみます。

Rainbow Table とは？

Windows のログオンパスワードに限らず、パスワードをハッシュ値のような「元に戻せない値」に変換して保存することは、よくあります。ハッシュ値から元のパスワードを復元する計算方法はありませんが、だったら、あらかじめ「パスワード」と「ハッシュ値」の組み合わせをデータベース化してしまえば、後は検索するだけになります。このデータベースを Rainbow Table と言います。

例えば、パスワードが「TEST」の場合、LM ハッシュの値は「01FC5A6BE7BC6929AAD3B435B51404EE」になります。こういったペアをひたすら計算してデータベース化して置けば、「LM ハッシュが「01FC5A6BE7BC6929AAD3B435B51404EE」だったら、パスワードは「TEST」という事が分かる、という仕掛けです*1。

Ophcrack と Rainbow Table

Ophcrack では、無償で使えるテーブルと、有償となるテーブルがいくつか用意されています。無償で使えるのは下記の通りです。

  • XP free small
  • XP free fast
  • Vista free

XP free small と XP free fast は本質的な違いは無く、XP free small はメモリが節約出来るけど検索はその分遅くなり、XP free fast はメモリは食うけど検索は速い、ということになります。XP 用の Live CD には XP free small が、Vista 用の Live CD には Vista free が含まれています。「XP」、「Vista」と書かれていますが、要は「XP」の方は LM ハッシュのテーブル、「Vista」は NT ハッシュのテーブルです。

これらのテーブルがダウンロード出来るページ（ http://ophcrack.sourceforge.net/tables.php ）に、それぞれのテーブルにどんなものが含まれているかをグラフ化したものがあります。これを見ると、Ophcrack がどうやってパスワード解析をしているのかがよく分かります。

「length」と書かれたところの右側に「1-4」とか書かれていますが、これがパスワードの文字列長です。で、この絵を見ると、「1-4」の上に「brute force」と書かれています。実は Ophcrack は４文字までのパスワードは総当たりで合致するものが無いか調べます。

xp_free_small or xp_free_fast と書かれているのが、14 文字までカバーしているのが分かります。LM ハッシュの場合、パスワードの最大文字列長は 14 文字ですから、15 文字以上は実在しません。このグラフを見ると、有償のテーブルも含めて、みな、14 文字までのパスワードをカバーしているように見えますが、違いは、使われている文字種です。

XP free の場合は英数字のパスワードに対するものであるのに対し、XP special は記号文字を含めています。「character set」と書かれているところに、使われている全文字が列挙されています。XP german は文字通り、ドイツ語で使われる文字が含まれています。

Vista free の場合には、辞書に登録されている単語とその変形のパスワードを集めたもので、ランダムなパスワードは含まれていません。

Ophcrack の盲点

Ophcrack が、

  • 4 文字までは総当たり
  • 5 文字以上は Rainbow Table から検索

という方法で高速な解析を実現している、という事は分かりました。しかし、Rainbow Table にはすべてのパスワードが収録されている訳ではありません。ということは、そこを外すと、Ophcrack では解析出来ないことになります。

例えば、5 文字のパスワードで記号が 1 文字でも入っていると、無償の XP free では見つかりません。

具体的に、「+TEST」というパスワードを考えてみます。この場合、

  • 5 文字なので、総当たりでは見つからない。
  • 記号文字を含んでいるので、XP free のテーブルには含まれていない。
  • XP special のテーブルには含まれている。
  • 「TEST」という単語が、辞書ベースの Vista free のテーブルに含まれていて、これに記号を１文字追加しただけのものも含まれていると推定される。

ということになります。つまり、Ophcrack を無料で使っている場合、「+TEST」というパスワードは LM ハッシュからパスワードを見つけられる事は無いけど、NT ハッシュからは見つかってしまう、ということになります。

次に、「Ohk6fau」というパスワードを考えてみます。この場合、

  • 6 文字なので、総当たりでは見つからない。
  • 記号文字が含まれないので、XP free のテーブルには含まれている。
  • 辞書ベースの Vista free では見つからない。

ということになります。このとき、もし LM ハッシュが保存されていなかったら、どうなるでしょう？ XP なんちゃらというテーブルは LM ハッシュの値に対する Rainbow Table です。つまり、LM ハッシュが保存されていない時には、XP free や XP special のテーブルは使えません。

実際に試してみる

実際に Ophcrack で上記の理屈が正しいか、確認してみます。

確認は Lubuntu（デスクトップ環境を LXDE 化した Ubuntu）の 10.04 を VMware Player 上で動かし、この Lubuntu に Ophcrack を Ubuntu のリポジトリからインストールした物で行いました。仮想マシンの搭載メモリは 512MBで、実際のマシンは、Let's note CF-R5 でメモリ 1.5GB、ホスト OS は Windows 7 です。

Live CD の場合は、自動的に Windows 上のアカウント情報を読み込んで解析を始めますが、いろんなパスワードを試すために、都度再起動するのは面倒です。そこで、Perl の Crypt::SmbHash を使って、指定したパスワードがどんなハッシュ値になるかを計算させ、そのハッシュ値を Ophcrack に解析させます。

さて、先の予想が正しいかどうか、「+TEST」と「Ohk6fau」のパスワードに対して解析させた結果は以下の通りです。

パスワード XP free Vista Free
+TEST Not found 1分24秒
Ohk6fau 19秒 Not found

まとめ

実は、実際に試してみるまで、Ophcrack がこれほどまで Rainbow Table に依存しているとは思いませんでした。その Rainbow Table にどんなパスワードが含まれているかを考えれば、LM ハッシュの問題点と、どんなパスワードが安全なのかが分かってくると思います。

まず、全くダメなパスワードは、

  • 4 文字以下のパスワード

です。これは Rainbow Table とは無関係に、総当たりで解かれてしまいます。

次に、

  • 単語、および、単純な変形によるパスワード

は、Vista free のテーブルで解けてしまいます。必ず、NT ハッシュの値は保存されているので、このようなパスワードは、「その単語、または、変形の仕方が、たまたま Vista free 上に無い」事を願うしかありません*2。

ここまでは、LM ハッシュが保存されているかどうかに関わらず、Ophcrack で解くことが出来ます。

LM ハッシュが保存されている状態であれば、

  • 14 文字以下の英数字のパスワード

は XP free のテーブルで解けます。ただし、記号文字が含まれていると、XP free では解けません。有償のテーブルが必要になります。

有償のテーブルを使えば、

  • 14 文字以下の任意のパスワード

は、必ず解ける事になります*3。しかし、LM ハッシュが保存されていない場合、前述の「単語、および、単純な変形」以外で解けるのは、

  • 7 文字以下の任意のパスワード(Vista special, Vista seven)
  • 8 文字以下の英数字と一部記号（! と *）のパスワード(Vista special, Vista eight)
  • 9 文字の小文字英数字のパスワード(Vista special, Vista nine)
  • 12 文字以下の数字だけのパスワード(Vista num)

となります。

これを裏返すと、Ophcrack で解けないパスワードが分かります。

LMハッシュの有無利用するテーブル安全なパスワード
有り無料5文字以上で記号が入ったランダムなパスワード
有料無し
無し無料5文字以上でランダムなパスワード
有料8文字以上でランダムなパスワード*4

こうしてまとめてみると、LM ハッシュの問題点がはっきりします。LM ハッシュが保存されている状態では、有料のテーブルを購入すれば、どんなパスワードでも解けることになります。しかし、LM ハッシュが保存されていなければ、有償のテーブルを使っても、8 文字以上で英数記号文字を使ったランダムなパスワードは解けません。

先の理論編でも書きましたが「正しいパスワード」でも解けてしまうのが、LM ハッシュの問題点です。

*1:ただし、LM ハッシュは７文字ずつ計算した２つの値をつなげているので、Rainbow Table の作りとしては、「01FC5A6BE7BC6929」が「TEST」、「AAD3B435B51404EE」が空パスワード、というデータになります。

*2:Live CD の場合、XP 用の Live CD には XP free のテーブルしか無いので、そのままでは、記号文字が含まれていれば見つかりません。しかし、Vista 用の Live CD で XP の入っている PC も解析できるので、そっちで見つかってしまいます。

*3:厳密には ASCII 以外の文字でも、ヨーロッパの言語でアルファベットに記号が付いたような文字も許容されるようなので、そういった文字が入ったパスワードは解けません。ただし、ドイツ語で使われる文字に関しては用意されています。

*4:8文字の場合は、「!」「*」以外の記号、9文字の場合は、大文字、もしくは、記号文字が含まれている必要があります。