パスワードクラック

保存したパスワードを保護するにあたり、設計の悪いパスワードハッシュ法をシステムが使っている場合、適切に考えられたパスワードであろうとも、攻撃者はそれを割り出す脆弱性を突くことができる。一例として、Microsoft Windows XP およびそれ以前のバージョンが標準で使っている、14文字以下でパスワードを保存するLMハッシュが挙げられる。LMハッシュはパスワードを全て大文字に変換し、それを 2 個の 7 バイト列に分け、別々にハッシュ値を求める。つまり、それぞれを個別にアタックすることができる。

MD5・SHA-512PA・SHA-1・RIPEMD-160 といった、より強力なハッシュ関数を使ったパスワード暗号法は、総当り攻撃や事前計算に対してまだ耐性を持っている。その種の攻撃は、ハッシュ関数を逆算するのではない。そうではなく、大量の単語やランダムな文字列のハッシュ値を求め、その結果を対象のパスワードハッシュ値と比較するのである。MD5-crypt[2] や bcrypt のような現代的手法は、意図的に計算量の多いアルゴリズムを使っており、一定時間内に攻撃者が試行できる候補が比較的少なくなるようにしている。後述するソルトは事前計算攻撃の難易度を飛躍的に上げるものであり、場合によってはあらゆる攻撃に耐えうるものである。しかしその使用は、各々のケースについて評価すべきである。

既存の暗号ハッシュアルゴリズムの分析を進めることは常に可能なので、今日は充分に耐性を持つハッシュであろうと、明日もそうだとは限らない。長らく安全だと思われていた MD5 と SHA-1 は、効率的に行われる総当り攻撃に対しては充分でないことが示されている。（暗号ハッシュとは別の）暗号化アルゴリズムについても、同じ事が言える。（既知の総当り攻撃に対しまだ耐性があるという程度において）DES は既に破られており、その（56ビットという）短いキーは総当り攻撃に対してすら耐性がないことが明確かつ公然と分かるほど、コンピュータの性能は上がってきている。これらの方法で攻撃から保護されているパスワードはいずれ耐性を失い、それに対応しないパスワードは暴かれることになるだろう。長く使われてきた仕組みであろうと、今日のセキュリティ問題に対していつまでも無縁でいるわけにはいかない。

類推攻撃・辞書攻撃・総当り攻撃は、はっきり区別できるものではない。パスワード候補のリストを順に試してゆくという点で、それらは似通っている。そのリストは明確に順序づけられているかもしれないし、何らかのルールに従って集められているかもしれない。それはターゲットの情報を一まとめにしたものかもしれないし、言語学的な観点から作られたのかもしれない。上記の 3 つのアプローチそれぞれ、特に辞書攻撃は、残る 2 つの攻撃方法と攻撃範囲を含めたものとして使われることが多い。

ターゲットの個人情報に関する知識から、攻撃者自身がパスワードを類推することがある。類推されそうなパスワード例として、次のようなものがある。

• パスワード無し
• "password", "passcode", "admin" および、それに類するもの
• QWERTYキーボードの列をとったもの - 「QWERTY」そのものだったり、「ASDF…」「UIOP…」あるいは「qazwsx」[3]
• 「12345…」[3]
• 上記2つを組み合わせた「1q2w3e4r5t」「1qaz2wsx」など[3]
• ユーザ名あるいはログイン名
• 恋人・友人・身内・ペットの名前
• 自分・友人・身内の出身地・誕生日
• 自分・友人・身内の車のナンバープレート
• 会社の電話番号・住所、ほか最も多いのが携帯電話の番号
• お気に入りの有名人
• 上記のどれかを少しもじったもの。例えば末尾に数字をつけたり（特に "1" が多い）、あるいは文字の順番を入れ替えたりなど。

こんにち、ターゲットの個人情報はオンライン上の様々な情報源から取得できる。攻撃者がターゲットと面識がある場合も同様に情報を得られるだろう。例えば 1978 年に Yale Law School を卒業したことから "YaleLaw78" というパスワードを使っていた場合、悪意を持った取引相手がパスワードを類推してしまうことがありうる。

類推攻撃は特に、利用者自身がパスワードの初期化を行なえるシステムでは効果的である。例えば 2008年9月に、アラスカ州知事でアメリカ副大統領候補になったサラ・ペイリンの Yahoo! メールが、何者かによって不正アクセスされる事件があった。犯人は3つあった認証用の質問のうち、彼女の郵便番号と誕生日を調べ上げ、さらに彼女が夫と出会った場所を推測できたのである[4]。

ユーザはしばしば脆弱なパスワードを選ぶものである。危険なパスワードのうちには、上で挙げたものの他、辞書に載っているような一単語、自分の苗字や名前、短すぎるパスワード（6 - 7文字以下は短すぎると通常考えられる）、ひねりが無さすぎてすぐ類推できてしまうパスワード（例えば母音と子音を入れ替えたもの）が挙げられる。40年にわたり繰り返し行なわれた調査によると、ユーザが選ぶパスワードの 40% は、辞書や場合によっては個人情報も使って実行される洗練されたクラッキングソフトの前ではたちまち分かってしまうということが明らかにされている[5]。

フィッシングによって取得された MySpace のパスワードを調査したところ、それらの 3.8% は辞書に載っている一単語であり、他の 12% は一単語の末尾に数字を一個加えたものだった。その数字の 2/3 は "1" だった[6]。

ユーザの中には、アカウント取得時に与えられた初期パスワードを変更せず放っておく者もいる。システム管理者の中には、OS やハードウェアの初期パスワードを変更せず放っておく者もいる。悪い意味で有名なのが「FieldService」というユーザ名と「Guest」というパスワードの組み合わせである。システム設定をする際にこれを変更しなかった場合、そのシステムの知識を持つ誰かがそのパスワードを悪用しているかもしれない。その種のメンテナンス用アカウントは、一般ユーザのアカウントよりも大きなアクセス権限を大概は持っている。初期パスワードの一覧はインターネット上で見つけることができる[7][8] 。ゲイリー・マッキノンは「軍用コンピュータに対する、かつてないほど大規模なクラッキング」[9]を行なったとして合衆国政府から告発されたが、彼は空のパスワードを探す Perl スクリプトを使うだけで軍用ネットワークに侵入できたと主張している。言い換えると、そのネットワークには全くパスワードを設定していないコンピュータがいくつもあったのである[10]。

ターゲットの個人情報を基に、ありえそうなパスワードのパターンを生成するクラッキングソフトが存在する[11][12]。

最後の手段のひとつとしてあるのが、考えうる「全ての」パスワードを試す、いわゆる総当たり攻撃である。理論的には、試行回数に上限が無いとするならば、総当たり攻撃は必ず成功する。なぜなら有効なパスワードを決めるためのルールは公にされている必要があるからだ。しかしパスワードが長くなるにつれて、考えうるパスワードの数も増加する。パスワードが比較的短いのでなければ、総当たり攻撃は非現実的と思われるが、並行処理という手法を使えばパスワードを割り出す時間を短縮することは可能で、それは使用するコンピュータ (CPU) の数に反比例する。この攻撃方法は、攻撃者がパスワードのハッシュ値とハッシュアルゴリズムを知っているかどうかで大きく様相が異なり、知っている場合は「オフライン攻撃」（保護された対象へ接続している必要はない）、知らない場合は「オンライン攻撃」と呼ばれる。オフライン攻撃の方が通常はるかに容易である。なぜならパスワードの検証は、候補となるパスワードのハッシュを数学的に計算し、実際のパスワードのハッシュと比較するだけで済むからだ。オンライン攻撃の場合、攻撃者は全てのパスワードについて認証を試みなければならず、システムによって規則と遅延が課せられ、またそれらの試みは記録される。

パスワードは、アルファベット・数字・（句読点などの）記号をランダムに組み合わせ、8 文字以上の長さにすることが一般に推奨される。ただしこれは、md5-crypt や Blowfish ベースの bcrypt といった、強力なパスワードハッシュ法を使うシステムで意味を持つのであり、多くの Microsoft Windows システムでは不充分である。なぜなら、それらの Windows はレガシーな LAN Manager ハッシュ法を使っており、それはパスワードを 2 個の 7 バイト列に分けてしまうからだ。それらのシステムでは、8 文字のパスワードならば 7 文字のパスワードと 1 文字のパスワードに変換される。セキュリティを高めるためには、そのシステムに依存するレガシーシステムに影響がない限り、LAN Manager 形式でのパスワード保存を無効化すべきである[13]。 システムによっては、パスワードに数字しか使えなかったり、大文字しか使えなかったり、あるいは一般的に言って、パスワード用の文字に制限を設けている場合がある。そうしたシステムも、比較的容易に総当たり攻撃をかけることができる。そうした場合（可能ならば）より長いパスワードを使うことで、文字パターンの制約を埋め合わせることができる。もちろん、多くの文字を選べるシステムであっても、ユーザ自身が特定の種類の文字に限って選択を行なった場合（例えば大文字だけ選んだり、数字だけ選んだ場合）は、そのアカウントへの総当たり攻撃は非常に容易になってしまう。

単純な総当たり攻撃であっても成功することはしばしばだが、人間がどのようにパスワードを選ぶ傾向を持つかという知見を悪用した「スマートな」総当たり攻撃は、さらに大きな脅威となる。アメリカ国立標準技術研究所 SP 800-63 (2) の報告ではパスワードの品質や推奨事項などが議論されているが、例えばユーザが自分で 8 文字のパスワードを考えた場合、それがどのように選ばれるかにより、エントロピー（ランダムさの程度）は 18 - 30 ビットの範囲に収まる。24 ビットのランダムさというと、無作為に選んだ 3 バイト、あるいは無作為に選んだ 5 文字の大文字アルファベット、あるいは 4000 語の中から無作為に選んだ 2 単語に相当する。このエントロピーは、暗号化キーとして安全だと通常考えられるレベルより遥かに低い。

オフライン攻撃を考えると、この脆弱さは「あまりに脆弱すぎる」という話であり、また部分的には攻撃者の技量とリソース（例えば時間とマシンパワー）に負うものである。後者はコンピュータの性能が上がるにつれ大きくなるだろう。広く使われているハッシュ法は、さらに解析を早めるため、それに特化したハードウェアとして実装することも可能である。多数のコンピュータを並列に連結し、広大な探索空間の一部を各々が受け持つことも可能である。夜間や週末で使われていない事務所のコンピュータも、この目的に使うことができる。

あるサービスから流出したパスワードを用いて、別のサービスへの不正ログインを試みる攻撃

最も基本的な形態として、事前計算とは辞書（あるいはパスワード候補の探索空間）の各語のハッシュ値を計算し、ハッシュ値の一覧を検索できるよう平文パスワードとハッシュ値のペアを保存しておくことである。こうしておけば、暗号化されたパスワード（ハッシュ値）を新しく入手した際、平文パスワードを割り出すのは造作もないことである。ソルトが適切に使われていない場合、辞書攻撃において事前計算は非常に有効であり、大容量記憶媒体の劇的な低価格化で、かなりの大型辞書を使うことも現実的になった。

さらに効率的な事前計算攻撃の手法も考えられる。すなわち時間と空間のトレードオフを考慮すると、次のような妥協点が導かれる。サイズが N の探索空間は、サイズが O(N^2/3) のデータベースへ収めることができ、かつその探索にかかる時間は O(N^2/3) となる。この理論は、最近になって実際の技法として洗練されたものになっている。別の例[14]では、アルファベットと数字からなる Windows LAN Manager パスワードを二、三分で解析してしまうものもある。非常に脆弱なパスワードハッシュ法を使っていた過去の LAN Manager の場合は、さらに時間が短縮される。Windows Vista/Server 2008 よりも前の Windows では、後方互換のためパスワードの計算と保管に LAN Manager ハッシュを標準で使っていた[13]。

事前計算と似た手法に、いわゆるメモ化がある。これは複数パスワードの解析を、一個分の解析コストで済ませるために使われる。パスワードの暗号化は、記憶済みハッシュの比較よりもずっと時間がかかるため、一度暗号化したパスワードの内容は記憶しておき、効率的な探索アルゴリズムを使って各々暗号化したパスワードと比較するのである。無論、この2つの手法は組み合わせることもできる。時間と空間のトレードオフを考慮した攻撃手法は、個別に解析するより短い時間で複数パスワードを同時に解析するよう、作り変えることができる。

事前計算とメモ化の長所は、ハッシュの過程をランダム化することで打ち消すことができる。この仕組みはソルトと呼ばれる。ユーザがパスワードを設定する際、「ソルト」（salt; 塩）という短いランダムな文字列をパスワードの末尾に加えた上で暗号化するのである。ソルトは、認証の際に利用できるよう、暗号化したパスワードと共に保管される。通常、ソルトはユーザ毎に異なるため、各パスワード候補のハッシュ値を一個しか計算していない事前計算リストはもはや役に立たない。初期の Unix システムは 12 ビットのソルトを使っていた。それでも攻撃者は、よく使われるパスワードについては 12 ビットのソルトからなる全 4096 パターンのリストを作っていた。しかしソルトが充分な長さを持っているならば、考えうるパターンは膨大なものになり、攻撃者は各ユーザの各パスワード候補ごとに暗号化を試さなければならなくなる。md5-crypt や bcrypt といった現代的な手法は、それぞれ 48 ビット、128 ビットのソルトを使っている[15]。

初期 Unix の実装はパスワード長を 8 文字以下に制限しており、12 ビットのソルトを使っていた。この場合、ソルトが作るパターンは 4096 種類になる。1970年代における殆どの用途ではこの 12 ビットで充分だと考えられていたが、2005年までには記憶媒体の低価格化が進み、よく使われる何百万種ものパスワードのハッシュ値を、全 4096 種のソルトの分も含めて、攻撃者は事前計算して一個のポータブル HDD に用意できるようになった。攻撃者に資金があれば、6 文字以下の全てのパスワードと 7 - 8 文字のよく使われるパスワードについて、4096 パターンのソルトを含めた暗号化データを作成し、それを保存したディスク群 (disk farm) を構築することも可能である。また数千ものパスワードを一度に解析対象とする場合、メモ化もやはり利点がある。