「LMハッシュの脆弱性」と呼ばれるもの

question:1270750577 の回答で、Ophcrack で 4 分で解析できた結果をもって、LM ハッシュが保存されていなくても同じ、と誤解されそうな雰囲気があったので、ちょっと解説してみます。

LM ハッシュの計算方法

詳細な計算方法は下記のページにある、11 ステップの LM レスポンスの計算方法のうち、7 ステップ目までの計算で得られる値になります。

http://www.monyo.com/technical/samba/translation/ntlm.html#theLmResponse

パスワード解析ソフトの処理内容

本来、パスワードから一方向関数で変換された値（ハッシュ値）から、直接、元のパスワードを計算する方法はありません。というか、計算出来ないから「一方向関数」な訳です。

ハッシュ値の計算手順や実装上の問題から、元のパスワードが計算しやすくなる、という事は無いわけではないですが、多くのパスワード解析ソフトが実際に行っている処理は、パスワードの候補となる文字列からハッシュ値を計算し、解析対象のハッシュ値と一致するか、という処理をひたすら行っているに過ぎません*1。

その「パスワードの候補」を、例えば辞書にある単語やその変形、とか、人間が付けるパスワードの癖を利用して、「当たりやすいパスワードの候補から試す」ということをします。パスワードを設定する際に、「単語をそのまま使わないように」とか「英数記号を必ず混ぜて」というのは、パスワード解析ソフトが真っ先に試すようなパスワードを避ければ見つかりづらい、ということです。

「な〜んだ、単に見つかりづらくするための時間稼ぎかぁ」と思うかもしれませんが、実は、この時間稼ぎは非常に重要です。入力可能なすべてのパスワードを試せば、必ずパスワードは見つかります。自転車のワイヤーロックでダイアル式のものがありますが、パスワードはこれに似ています。すべてのパターンを試せば必ず開きます。

もし、完全にランダムなパスワードであれば、平均的な確率としては「入力可能なすべてのパスワードのバリエーション数の２分の１」回試せば、パスワードが見つかることになります。

では、パスワードのバリエーションが、実際にどのくらいになるか見てみます。

LM ハッシュのバリエーション

ダイアル式のロックだと、例えば、４つのダイアルで各ダイアルが１〜８だった場合、4,096通り（ $8^4$ ）になります。最悪でも 4,096 回目、平均で 2,048 回目には、ロックが外れる事が期待されます。

では、パスワードの場合はどうでしょう。

先の LM ハッシュの計算手順を見ると、受け入れられる最大のパスワード長は 14 文字です。全ての ASCII 図形文字（いわゆる英数字記号。0x21-0x7e の範囲の文字）と半角スペースの 95 文字が使えるとすると、

パスワード長	計算式	バリエーションの数
0	-	1
1	-	95
2	$95^2$	9,025
3	$95^3$	857,375
..	......	......
13	$95^{13}$	51,334,208,327,950,511,474,609,375
14	$95^{14}$	4,876,749,791,155,298,590,087,890,625
合計	$1+95^1+95^2+95^3+\ldots+95^{13}+95^{14}$	4,928,630,108,082,482,617,642,017,121

つまり、最長 14 文字のパスワードが設定可能であれば、4,928,630,108,082,482,617,642,017,121 通りのパスワードのハッシュ値を求めて一致するかどうかをチェックすれば、必ず、元のパスワードが見つかることになります。

ところが、LM ハッシュの場合、この数よりもはるかに少ない数で一致するものが見つかってしまいます。

まず、小文字は全て大文字に変換されて処理されることになっています。よって、パスワード解析ソフトは小文字は無いものとして計算すれば良いので、１文字辺りのバリエーションは 95 - 26 = 69 文字になります。

パスワード長	計算式	バリエーションの数
0	-	1
1	-	69
2	$69^2$	4,761
3	$69^3$	328,509
..	......	......
13	$69^{13}$	803,596,764,671,634,487,466,709
14	$69^{14}$	55,448,176,762,342,779,635,202,921
合計	$1+69^1+69^2+69^3+\ldots+69^{13}+69^{14}$	56,263,591,126,494,879,335,720,611

この時点で、パスワード候補は 100 分の 1 近くに減少しています。

ただ、NT 系の OS（NT、2000、XP、Vista、7 など）では、実際にログオンするには NT ハッシュを使うので、パスワードの大文字小文字は区別されます。LM ハッシュが保存されている状態であれば、

まず、LM ハッシュと合致するパスワードを見つける。
LM ハッシュに合致したパスワードから、大文字小文字のバリエーションを作って、NT ハッシュと合致するものを見つける。

とすれば、効率よく、パスワードを見つける事ができます。ひとまず、この点は後回しにします。

次に肝になっているのは「７文字ずつに分けて計算する」部分です。

例えば、パスワードが「ABCD1234」であった場合、「ABCD123」のハッシュ値と「4」のハッシュ値を計算し、この２つの値を保存しています。ということは、パスワードを解析する側としては、７文字のパスワードに対するハッシュ値を求める処理を、前半７文字用、後半７文字の２度実行すれば良いことになります。

69 の文字種で 7 文字のパスワード長となると、そのバリエーションは下記のようになります。

パスワード長	計算式	バリエーションの数
0	-	1
1	-	69
2	$69^2$	4,489
3	$69^3$	300,763
..	......	......
6	$69^6$	107,918,163,081
7	$69^7$	7,446,353,252,589
合計	$1+69^1+69^2+69^3+\ldots+69^6+69^7$	7,555,858,447,480

愚直なプログラムを書けば、7,555,858,447,480 × 2 回のハッシュ値計算を行えば、合致するパスワードが見つけられることになりますが、７文字のパスワード候補から計算したハッシュ値１つに対して、前半に合致するのか、後半に合致するのかを判定していけば、7,555,858,447,480 通りのパスワードを試したときには、前半部、後半部の文字列が判明します。

ここで、NT ハッシュでは大文字小文字が区別される点を考慮します。

例えば、前半７文字の LM ハッシュに合致する元の文字列が「ABC#%12」だったとします。この時、大文字小文字をバリエーションを考えると、実際のパスワードの候補は、

ABC#%12
aBC#%12
AbC#%12
abC#%12
ABc#%12
aBc#%12
abc#%12

の６通りになります

NT ハッシュでは 7 文字に分割することはしていないので、14 文字全てがアルファベットだった場合、
大文字小文字のバリエーション $2^{14}=16,384$ 通りに対して、NT ハッシュと一致するかを確認する必要があります。

よって、LM ハッシュが保存されている時にパスワードを解析するプログラムが、元のパスワードにたどり着く最悪のケースで、

７文字のパスワード、7,555,858,447,480 通りの最後で、LM ハッシュ値に合致するものが見つかる。
その見つかったパスワードが全てアルファベットだった場合、16,384 通りの一番最後で、NT ハッシュと合致するものが見つかる。

ということになり、LM ハッシュ、NT ハッシュ合わせて、7,555,858,463,864 通りのハッシュ値を求めれば、必ず元のパスワードが見つかることになります。

一方、LM ハッシュが無ければ、NT ハッシュを計算して一致するかを調べることになります。NT ハッシュでは大文字小文字は区別しますし、7 文字で分割、といったこともしないので、同じ 14 文字以下、ASCII 図形文字の条件であれば、最初に計算した4,928,630,108,082,482,617,642,017,121 通りのパスワードを全て計算すると、パスワードが判明することになります。

この差、およそ 650 兆倍になります。

つまり、仮に LM ハッシュが保存されている状態で、最悪の場合でも 1 秒でパスワードが解析出来たとしても、NT ハッシュだけの場合であれば、およそ 2000 万年かかることになります。

パスワード解析ソフトでパスワードが分かる理由

Ophcrack で Windows 7 のパスワードが解析出来ることで、LM ハッシュの問題が無くなっていない、と誤解しそうですが、Ophcrack は LM ハッシュが無くても NT ハッシュだけで解析処理を行えます。なので、LM ハッシュが保存されていない状態でも Ophcrack は使えます。

ただ、LM ハッシュが有ると無いとではその解析時間には大きな差があり、たとえ LM ハッシュ有りで数秒でパスワードが分かったとしても、無ければ人類が生き延びているかどうかすら分からないような未来になってしまいます。計算機の能力が 10 倍、100 倍となったところで、焼け石に水な事が分かります。

しかし、実際に LM ハッシュが無くても解析結果が得られる事はあります。

Vista 以降であれば、デフォルトで LM ハッシュは保存されませんが、かといって、10 文字で英数記号大文字小文字を混在させたパスワードを設定している人がどのくらいいるでしょうか？結局、ハッシュ値の保存方法が安全になったとしても、安易なパスワードは解析ソフトが真っ先に試すので、すぐに見つかってしまいます。

LM ハッシュの問題は、適切なパスワードを設定していても、ランダムな 7 文字のパスワードよりも低い、ということです。

.... と理論的な事を書きましたが、時間があったら、実際にいろんなパスワードを解析ソフトにかけて、試してみたいと思います。

2010-05-17 追記：
使える文字数の数が間違っていた（２個少なかった）ので修正しました。

*1:あらかじめ「このハッシュ値の時は元のパスワードはこれ」という表を作っておく、という事もあります。この表の事を「Rainbow Table」と言います。Ophcrack でも有料で表データを取得する事ができるようになっています。実際に表を作ると、「何文字まで」と制限を付けないと現実的なサイズに収まらないのですが、LM ハッシュの場合、事実上 7 文字までのパスワードに対応した表を作ると良いので、実際に Ophcrack で使える LM ハッシュ用の表は 7.5GBしかありません。これも LM ハッシュの問題の一つです。また、Windows のパスワードの場合、「ソルト」と呼ばれる、パスワードに付加する乱数が無いので、同じパスワードから必ず同じハッシュ値が得られる、という側面もあります。UNIX 系 OS では「ソルト」が付加されるので、Rainbow Table が作りづらくなっています。