パスフレーズ vs. パスワード Part 2

公開日: 2004年11月24日

Jesper M. Johansson, Ph.D., ISSAP, CISSP Security Program Manager Microsoft Corporation

パスワード vs パス フレーズの第 2 回目です。第 1 回目のコラム では、パスワードおよびパス フレーズの基礎、これらの保存方法などを説明しました。今回は、パスワード各種の相対的な強さを説明し、数学的なアプローチで例証します。第 3 回目のコラムでは、パスワードの選択とパスワードのポリシーの構成方法に関する結論とガイダンスについてお話しする予定です。

長所、短所に関する論争

パス フレーズは多くの理由により、流行し始めています。その理由の １ つは、数分間で多くのパスワードをクラックできるツールが開発されていることです。この様なツールは以前より知られていました。Quakenbush Password Appraiser は 1998 年には公開されており、この時点でパスワードのクラックを行う機能が実装されていました。。新しい点は、Phillippe Oechslin 博士 (英語情報) により提唱された時間と空間のトレードオフ (time/space trade off) に基づく理論と実践です。時間と空間のトレードオフとは、すべての生成可能なハッシュを保存することはできないということを意味しています。もしも NT ハッシュを保存しようとするのであれば、宇宙に存在するストレージよりも多くの容量が必要となるでしょう。76 文字の文字セットについて、14 文字までのすべての NT ハッシュを保存する場合、5,652,897,009 の 1018 バイトのストレージが必要となるでしょう。これは今日のいかなるファイル システムの容量をも超過します。すべての LM ハッシュを保存するためには、ほんの 310 テラバイトのみが必要となりますが、これも依然として実行不可能です。このジレンマを解決するために、Oechslin 博士はハッシュの一部分とそれに関連するパスワードのみが保存される時間と空間のトレードオフを提案しました。これにより必要なストレージ容量は劇的に削減され、わずか 17 ギガバイトのストレージで、同じ文字セットの LM ハッシュを保存することができるのです。お気づきのように、パス フレーズの主な論点は、ストレージ容量の要件をなくし、事前計算によるハッシュ攻撃を破るということです。

主張 1: ユーザーはパスフレーズを覚えることができる

パス フレーズ支持者がまず主張する点は、ユーザーは長いパスワード (10 文字以上) よりもパス フレーズの方が覚えやすいということです。これは正しいかもしれませんが、10 文字以上で構成されるパスワードを使用しているユーザーはほとんどいませんので、この主張が正しいかどうかを判断することは難しいのでしょう。この点を明らかにするために、ユーザーが 10 文字で構成されているパスワードを覚えられるかどうについて、まったく科学的ではない調査を行ってみました。管理者に意見を聞いてみましたが、その 99% が、ユーザーが 10 文字のパスワードの使用を強制された場合、そのパスワードを覚えられないばかりでなく、パスワードの強制に抗議するだろうと答えました。では、ユーザーは 10 文字のフレーズを覚えることができるでしょうか? 10文字のフレーズはいくつかのトークン (この場合、単語) でしかないため、おそらく覚えられるでしょう。有名な論文を引用したいと思います｡Miller 氏の 1956年に発表されたものです。「The Magical Number Seven, Plus or Minus Two: Some Limits On Our Capacity For Processing Information. (魔法の番号 7。プラスまたはマイナス 2。我々が情報を処理する能力の限界。)」 (英語情報)。すばらしい論文というものはそのタイトルだけで言わんとすることがわかるものですが、この論文もそういったすばらしい論文の 1 つです｡この論文の前提は、人間が情報を処理する能力には限界があるということです。私たちが 1 度に記憶できる情報 ”チャンク” は、 7 つ前後プラスマイナス 2 だということです。7 という実際の数字はここではさほど重要ではなく、私たちの情報処理能力には限界がある、ということがここでの重要な点です｡記憶できる数は 5 プラスまたはマイナス 2 であると主張する人もいます。また、少数派ではありますが、記憶できる数は 3 であると主張する人もいます。個人的には、記憶できる数が 3 つである人は単に非常にフラストレーションのたまる仕事をしているのだと思いますが｡いずれにしても、人間の情報処理能力は非常に限られたものです。

「チャンク」の定義もまた、何をしようとしているのかにより変化します。ランダムな 10 文字のパスワードでは、「チャンク」とは記号のことであり、Miller 氏なら、ほとんどの人は 10 個のランダムな記号を覚えられないと言うでしょう。ユーザーは 2、3 の語またはチャンクで構成されている 10 文字のパス フレーズの方をより覚える傾向があるでしょう。

ユーザーが 7 つのチャンク、語または記号を覚えることができるとすると、ユーザーが使用できる最長のパスワードは 9 文字ということになるでしょう。この見解は経験試験により確認されています。パスワードの強度を評価するために、大規模ドメインから 28,000 のパスワードをクラックしてみました。全パスワードのうち、23,311 のパスワード、全体の 83% は完全にクラックすることができ、また 13.16% を部分的にクラックすることができました。この例はすべてのパスワードについて有効ではありませんが、このコラムのこれ以降の部分で出てくる統計は、クラックされた 23,311 のパスワードの分析に基づいています。その分析によると、「限界が 9 文字」に信憑性があります。ドメインのクラックされたパスワード (最低 7 文字を必要とするものでした) の 64% は、9 文字またはそれ以下でした。少なくともドメインのパスワード全体の 90.37% は 15 文字以下でした。(パスワードがクリアテキストでキャプチャされない限り、15 文字以下のパスワードがどれだけ存在するかは正確には言えませんが。) このため、LM ハッシュなしのこれらのパスワードは、なんらかの理由で LM ハッシュを使用していない場合も含め、15 文字またはそれ以上であると仮定されます。

パス フレーズでは、各語がチャンクです。英語の単語の長さの平均は 5 文字です。また、英語では、1 単語につき 5 文字は 1 分間に何ワードタイピングできるかを測定するために使用される標準でもあります。同様に、1995 年の 45 PGP ユーザーの調査 (英語情報) で、Arnold Reinhold 氏は、平均的な PGP パス フレーズには 5.3 文字の語が含まれていることを発見しました。興味深いことに、Reinhold 氏はすべての語の 8 分の 5 は英語辞書に載っている単語であったことも報告していますそのサンプルは非常に小さいため、ここから結論を導き出す事は科学的にみて無効ですが、数少ない文献の中では最善のものです。

話を Miller 氏に戻すと、7 語の文章を覚えられるユーザーは 41 文字のパスワードを持つことができます。この推論には、いくつかの注意点があります。まず、実際のパス フレーズがそのような長さであることはまずないという点。たとえば、私の現在のパス フレーズ (私もパス フレーズを使用しています) はたったの 35 文字ですが、既にやっかいであると感じています。また、Reihold 氏は、中間のパス フレーズにはたったの 4 語のみが含まれていることを確認しました。

主張 2: より長いとより強い

パス フレーズについての主張には、パス フレーズはより長いため、それだけより強いというものがあります。しかし、パス フレーズの長さは直接パスワードの長さと比較できるわけではありません。より長いパスワードは、より強度が高いと考えられています。これはパスワードの強度を測る典型的な方法 - パスワードのクラックに要する時間 - に起因しています｡たとえば、前回お話ししたように、8 文字のパスワードをクラックするには 7 文字のパスワードよりも 5 年と 11 ヶ月余計に時間がかかると考えられます。しかし、これはパスワードが実際にランダムであり、すべての記号のパスワードに使用される可能性が等しい場合のみです。パスワードが実際にはランダムでない場合、この計算は成り立ちません。

より長いパスワードについての追加の論点として、14 文字を超えるパスワードは LM ハッシュ値を生成しないことが頻繁に引き合いに出されます。そのほかの方法で LM ハッシュを排除できることを考えると、単に LM ハッシュが排除されることは、パス フレーズの利点とはなりません。それでは長さの利点はあるのでしょうか?それも、ありません。現在のパスワード クラッカーは記号をクラックするよう設計されていますが、今後のパスワード クラッカーが単語を記号として使用しないという保証はないのです。実際に、それはありうると考えられます。このため、より長いパスワードは不変の利点を提供しません。これらのパスワードは単に今日利用可能なクラッキング ツールを阻止する手助けとなるだけです。

主張 3: パスフレーズはさらにランダム性を持つことができる

パス フレーズの明確な利点が 1 つあります。それは、より高いエントロピーです。エントロピーとは、一般的にランダム性の度合いを表します｡エントロピーには 3 つの構成要素があります。選択されたアイテム数、アイテムが選択されたセットのサイズ、および個々の各アイテムが選択される可能性です。パス フレーズはパスワードよりも長いため、同じ文字セットから選択されても、パスワードよりもエントロピーが高い可能性があります。これは注目すべき点です｡なぜなら、パスワード クラッカーは確率に基づいて動作するよう設計されているからです。単純にパスワード内の文字の可能な組み合わせをすべて試行するのではなく、パスワード クラッカーは通常辞書からの一般的な組み合わせから始め、次に文字の頻度に基づいた文字の順列の試行へと進みます。このため、7 文字のパスワードをクラックするために 28 日かかるという計算は正確でないかもしれません。実際、パスワードがどのように構成されているかによって、わずか数秒間で多くのパスワードをクラックすることが可能です。このため、エントロピーは単なる長さや文字セットよりも、パスワードの強度の測る上でよりよい基準となります。

いくつかの例をみてみましょう。テストにより、ここでのサンプルの 83% 以上が、文字、数字および記号 (!@#$%^&*()-_+=) で構成されている文字セットのみから作成されていることが分かります。その文字セットには英語で 26+26+10+14=76 の記号があり、そのほかの言語ではもう少し多くあります。さらに、これらのパスワードに使用されている記号の 80% は、これらの 76 の記号のうちわずか 32 から選択されています。32 の一般的な記号を使用頻度順に並べると次のようになります｡

 ea1oirn0st2lud!m3hcyg94kSbpM758B

さらに興味深いことに、パスワードの 10% はこれらの 32 の記号だけを使用して作成されていました。 76 の記号の文字セットの自然なエントロピー、または絶対的な割合は、記号ごとに R=Log2L = 6.25 ビットです。絶対的な割合は通常エントロピーの上限と考えられており、各文字が選択される可能性は等しいと推定されています。しかし、C.E. Shannon 氏は英語の 8 文字のチャンクでは、文字ごとのエントロピーを、1 文字につき 2.3 ビットと計算しました (Shannon, C.E., “Predication and Entropy in Printed English,” Bell System Technical Journal, v. 30, n. 1, 1951, pp. 50-64)。Shannon 氏の研究は 26 文字セットを使用する英単語に基づいたものであり、ここで取り上げている 76 記号の文字セットではないことに注意して下さい。それでもなお、ユーザーが使用する記号のほとんどを 32 の記号から選択していることが分かります。いずれの場合でも、パスワード内の記号ごとの実際のエントロピーは、おそらく Shannon 氏により計算された 2.3 以上であり、絶対的な割合である 6.25 以下というところでしょう。Log2 32 = 5、これは確信していたものよりも少々高いのですが、パスワードのビットごとのエントロピーの上限の推定となるはずです。平均的なパスワードの長さが 9.16 文字 (ここでは切り捨てて 9 とします) であるため、9*5=45 ビット以上のエントロピーはありません。

パス フレーズの論点は、ほとんどの人が知っている単語が 76 単語以上あるということです。また、パス フレーズは言語 - パス フレーズを構成するために使用される言語で利用可能な語 - から構成されているとも考えられます。オックスフォード英英辞典には 616,500 語が収録されていますが、そのうちの 614,000 語を使用するのはスペリング コンテストの競技者や大学入試を受ける受験生だけです。実際、アメリカ人の平均的なボキャブラリの数は (ここでは同義的に正しい欧州人が挿入するであろう無数の不当な言動は控えます) 言語学者 Richard Lederer 氏により 10,000 から 20,000 まで (英語情報)、また言語学者 James L. Fidelholtz 氏によると 50,000 から 70,000 まで (英語情報) と推定されています。両方の言語学者は、ほとんどの人が言葉の存在を思い出す、すなわち、ある言葉を聞くとそれを思いだしますが、使用はしない場合が多い、ということに同意しています。平均的な人は自分のボキャブラリの一部分のみを使用しているに過ぎません｡

パス フレーズは 300 語のみのセットに基づいていると仮定しましょう。これは非常に保守的な推定ですが、その一方で、これらの語のほとんどは、特定の方法で組みあわされると、パス フレーズのランダム性を著しく減少させ、このような場合のみ意味を持ちます。

パス フレーズの実際のエントロピーを計算するためには、何語使用されているかを知る必要があります。前述の PGP の研究の語の中間の数は 4 でしたが、平均はこれよりも高いものでした。Miller 氏に敬意を表して、5 語のパス フレーズの平均を使用しましょう。

1 語につき 5 文字あるとすると、25+4=29 文字あり、このうち、パス フレーズに 4 つのスペースがあります。パス フレーズがどのくらいエントロピーを含んでいるかは、どの推定を使用するかによります。文字ごとに 2.3 ビットという Shannon の推定を使用すると、8 文字の語には、エントロピーは合計 29*2.3=66.7 ビットです。66.7 ビットという計算はおそらく、理にかなったパス フレーズのエントロピーの上限でしょう。また、45 ビットのエントロピーしかない 9 文字のパスワードと有利に比較されます。下限について、Bruce Schneier 氏の推定である文字ごとに 1.3 ビットを使用することができます。これは Thomas Cover 氏による研究に基づいています。(1996 年 B. Schneier, “Applied Cryptography, 2nd Edition,” Wiley)Shannon 氏は 16 文字の語について文字ごとに 1.3 ビットを提唱しているため、ここでの 5 文字の語には完全には当てはまらないでしょう。いずれの場合でも、1.3 をエントロピーの推定として使用すると、計算は 29*1.3= 37.7 となり、これは実際には 9 文字のパスワードよりも悪くなります。その数字に基づいて、9 文字のパスワードとだいたい同じエントロピーを得るためには 6 語のパス フレーズが必要となるでしょう。

次に、またここでのパス フレーズのエントロピーの計算は、これらの例について推定した語彙を考慮に入れていません。パス フレーズが一般的になった場合、攻撃者は記号ではなく、語を単位とする「パス フレーズ クラッカー」を使用し始めることが推定されます。この状況は、パスワードのランダム性をどのように計算するかで著しく変化するでしょう。単位として語を使用することは、語を構成する文字を記号として使用するよりも適切であるかもしれません。パス フレーズに語彙の中から 300 語を使用し、これらがランダムに組み合わされると仮定した場合、語ごとの絶対的な割合は、語ごとに Log2300 = 8.23 ビットとなります。5 語のパス フレーズを使用すると、エントロピーは 8.23*5= 41.2 ビットとなり、6 語のパス フレーズを使用すると、エントロピーは合計 49.4 ビットとなります。

単位として語を使用することにより、パス フレーズはパスワードよりも攻撃者にとって魅力的ではなくなります。実際、5 から 6 語のパス フレーズはだいたい 9 文字のパスワードと同じ強度です。これは科学的に証明された結果とは言えないでしょう。これらのエントロピーの計算を検証するため、さらに研究が必要です。

この記事は、マイクロソフト セキュリティ ニュースレターで配信しました。

ページのトップへ