パスワードクラッキング

暗号解読とコンピュータセキュリティにおいて、パスワードクラッキングとは、コンピュータシステムを保護するためのパスワードを推測するプロセスである^[1]。一般的なアプローチ（ブルートフォース攻撃）は、パスワードの推測を繰り返し試み、それをパスワードの利用可能な暗号ハッシュと照合することである^[2] 。別のタイプのアプローチは、パスワードスプレーであり、これは自動化されていることが多く、一般的なパスワードのリストを使用して、検出されないように時間をかけてゆっくりと実行されます。^[3]

パスワード クラッキングの目的は、ユーザーが忘れたパスワードを回復できるようにする (まったく新しいパスワードをインストールするにはシステム管理者の権限が必要になるため)、システムに不正にアクセスする、またはシステム管理者が簡単にクラックできるパスワードをチェックする予防措置として機能することなどです。ファイル単位では、特定のファイルのアクセス許可が制限されている場合に、裁判官がアクセスを許可したデジタル証拠にアクセスする目的でパスワード クラッキングが利用されます。

パスワードを解読するのにかかる時間は、パスワードのエントロピーの尺度であるビット強度と、パスワードの保存方法の詳細に関係しています。パスワード クラッキングのほとんどの方法では、コンピューターが多数の候補パスワードを作成し、それぞれをチェックする必要があります。1 つの例は、ブルート フォースクラッキングです。この方法では、コンピューターは成功するまですべての可能なキーまたはパスワードを試します。複数のプロセッサを使用すると、最後の可能な記号グループと最初のグループを同時に検索し、他のプロセッサを配置して指定された可能なパスワードを検索することで、この時間を最適化できます。^[4]辞書攻撃、パターン チェック、一般的な単語のバリエーションなどのより一般的なパスワード クラッキング方法は、推測回数を最適化することを目的としており、通常はブルート フォース攻撃の前に試行されます。パスワードのビット強度が高いほど、パスワードを復元するために平均してチェックする必要がある候補パスワードの数が指数関数的に増加し、パスワードがクラッキング辞書で見つかる可能性が低くなります。^[5]

コンピュータ プログラムを使用してパスワードをクラックする能力は、1 秒あたりに確認できる可能性のあるパスワードの数にも左右されます。攻撃者がターゲット パスワードのハッシュを利用できる場合、オフライン攻撃が可能であるため、この数は 1 秒あたり数十億または数兆になる可能性があります。利用できない場合、この率は、認証ソフトウェアが時間遅延、 CAPTCHA 、または一定回数の試行失敗後の強制ロックアウトによって、パスワードの試行回数を制限しているかどうかによって異なります。パスワードが暗号化キーの形成に使用される場合も、素早い推測が可能な状況です。このような場合、攻撃者は推測したパスワードで暗号化されたデータが正常にデコードされるかどうかをすばやく確認できます。

一部の種類のパスワードハッシュについては、一般的なデスクトップコンピュータは、汎用CPU上で実行されるパスワードクラッキングツールを使用して1秒あたり1億を超えるパスワードをテストでき、GPUベースのパスワードクラッキングツールを使用すると1秒あたり数十億のパスワードをテストできます^{[1] [6] [7]} （John the Ripperベンチマークを参照）。^[8]パスワードの推測率は、システムがパスワードハッシュを生成するために使用する暗号化機能に大きく依存します。bcryptなどの適切なパスワードハッシュ関数は、単純なMD5やSHAなどの単純な関数よりも桁違いに優れています。 NISTによると、よく選択されるパスワードやその他の辞書一致を除外した、数字、大文字と小文字が混在する、および記号を含むユーザーが選択した8文字のパスワードは、推定30ビットの強度に達します。 2 ^{30 は}わずか10億の順列^[9]であり、ハッシュ関数が単純であれば数秒で解読されます。ボットネットのように、通常のデスクトップ コンピュータを組み合わせてクラッキングを行うと、パスワード クラッキングの能力が大幅に拡張されます。2002 年、distributed.net は4 年かけて64 ビットのRC5キーを発見しました。この作業には、さまざまな時期に 300,000 台以上のコンピュータが参加し、平均して 1 秒あたり 120 億以上のキーが生成されました。^[10]

グラフィックス プロセッシング ユニットは、特定のハッシュ アルゴリズムの場合、汎用コンピューターの 50 ～ 100 倍の速度でパスワード クラッキングを実行できます。たとえば、2011 年に市販された製品は、高性能グラフィックス プロセッサを搭載した標準的なデスクトップ コンピューターで 1 秒間に最大 28 億個のNTLMパスワードをテストできると主張していました。 ^[11]このようなデバイスは、10 文字の単一ケースのパスワードを 1 日で解読できます。作業を多数のコンピューターに分散すると、同等の GPU を搭載したコンピューターの数に比例して速度が向上します。ただし、一部のアルゴリズムは GPU 上では低速で実行され、低速で実行されるように特別に設計されています。例としては、DES、Triple DES、bcrypt、scrypt、Argon2などがあります。

GPUのハードウェア アクセラレーションにより、ほとんどのハッシュ アルゴリズムに対するブルート フォース攻撃の効率と速度を向上させるためにリソースを使用できるようになりました。2012 年、Stricture Consulting Group は 25 基の GPU クラスターを発表しました。このクラスターは、1 秒あたり 3,500 億回の NTLM パスワード推測というブルート フォース攻撃速度を達成し、5.5 時間でパスワードの組み合わせをチェックできるようになりました。これは、企業環境で一般的に使用される 8 文字の英数字特殊文字パスワードをすべて解読するのに十分な時間です。仮想OpenCLクラスター プラットフォームで ocl- Hashcat Plus を使用することで、^[12] Linux ベースのGPU クラスターは、「LinkedIn のユーザーに属する 650 万のパスワード ハッシュの 90% を解読」するために使用されました。^[13]${\textstyle 95^{8}}$

特定のハッシュアルゴリズムでは、CPUとGPUは相性がよくありません。高速で実行するには専用のハードウェアが必要です。カスタムハードウェアは、FPGAまたはASICテクノロジーを使用して作成できます。どちらのテクノロジーの開発も複雑で（非常に）高価です。一般的に、FPGAは少量に適しており、ASICは（非常に）大量、エネルギー効率が高く、高速に適します。1998年、電子フロンティア財団（EFF）は、ASICを使用した専用のパスワードクラッカーを構築しました。彼らのマシンであるDeep Crackは、56時間でDES 56ビットキーを破り、1秒あたり900億を超えるキーをテストしました。^[14] 2017年に漏洩した文書は、ASICが、より弱い暗号化でインターネット通信の多くの部分をコード解読する可能性があった軍事プロジェクトに使用されていたことを明らかにしました。^[15] 2019年以来、John the RipperはFPGAを使用した限られた数のハッシュアルゴリズムのパスワードクラッキングをサポートしています。^[16]民間企業は現在、パスワードクラッキングにFPGAベースのセットアップを使用しています。^[17]

覚えにくいパスワードはシステムのセキュリティを低下させます。

• ユーザーはパスワードを書き留めたり、安全でない方法で電子的に保存したりする必要があるかもしれない。
• ユーザーは頻繁にパスワードをリセットする必要があり、
• ユーザーは同じパスワードを再使用する可能性が高くなります。

同様に、パスワードの強度に関する要件が「大文字と小文字と数字を混ぜる」や「毎月変更する」など厳格であればあるほど、ユーザーがシステムを破壊しようとする度合いは高くなります。^[18]

「パスワードの記憶性と安全性」^[19]で、ジェフ・ヤンらは、適切なパスワードの選択についてユーザーに与えるアドバイスの効果を検証しています。彼らは、フレーズを考え、各単語の最初の文字を取ることに基づいたパスワードは、単純に選択したパスワードと同じくらい記憶に残りやすく、ランダムに生成されたパスワードと同じくらい解読が難しいことを発見しました。無関係な2つの単語を組み合わせるのも、別の良い方法です。わかりにくいパスワードを生成するために個人的に設計された「アルゴリズム」を持つのも、別の良い方法です。

しかし、ユーザーに「大文字と小文字の混合」からなるパスワードを覚えてもらうことは、ビットのシーケンスを覚えてもらうことに似ています。覚えるのは難しく、解読するのはほんの少しだけ難しくなります (たとえば、7 文字のパスワードの場合、解読は 128 倍難しくなりますが、ユーザーが文字の 1 つを大文字にした場合はさらに難しくなります)。ユーザーに「文字と数字の両方」を使用するように依頼すると、多くの場合、「E」→「3」や「I」→「1」などの推測しやすい置換が行われます。これは攻撃者によく知られている置換です。同様に、パスワードをキーボードの 1 行上に入力することは、攻撃者によく知られている一般的なトリックです。

2015年4月にカーネギーメロン大学の数人の教授が発表した論文で詳細に説明されている研究によると、人々が選択するパスワード構造は、多くの場合、いくつかの既知のパターンに従っています。たとえば、パスワード要件で16文字などの長い最小文字数が要求されている場合、人々はパスワード内で文字や単語全体を繰り返す傾向があります。^[20]その結果、パスワードは数学的な確率が示すよりもはるかに簡単に解読される可能性があります。たとえば、1桁の数字を含むパスワードでは、その数字がパスワードの最後に不釣り合いに含まれています。^[20]

1998年7月16日、CERTは、攻撃者が186,126個の暗号化されたパスワードを発見した事件を報告した。侵入が発見された時点で、47,642個のパスワードがすでに解読されていた。^[21]

2009 年 12 月、Rockyou.comで大規模なパスワード侵害が発生し、3,200 万件のパスワードが流出しました。その後、攻撃者は 3,200 万件のパスワードの完全なリスト (その他の識別可能な情報なし) をインターネットに漏洩しました。パスワードはデータベースに平文で保存され、 SQL インジェクションの脆弱性を通じて抽出されました。Impervaアプリケーション防御センター (ADC) は、パスワードの強度に関する分析を行いました。^[22]主な調査結果は次のとおりです。

• 約30%のユーザーが7文字未満のパスワードを選択しました。
• ほぼ60%のユーザーが限られた英数字の文字からパスワードを選択し、
• ユーザーの約50％が名前、俗語、辞書に載っている単語、または連続した数字や隣接するキーボードキーなどの弱い構成を採用した簡単なパスワードを使用していました 。例えば、RockYouアカウント所有者の間で最も一般的なパスワードは単に「123456」でした。^[22]

2011年6月、NATO（北大西洋条約機構）はセキュリティ侵害に遭い、電子書籍ストアの登録ユーザー11,000人以上の氏名、ユーザー名、パスワードが公開されました。このデータは、Anonymous、LulzSec、その他のハッカーグループや個人を含む運動であるOperation AntiSecの一環として漏洩されました。 ^[23]

2011年7月11日、ペンタゴンのために相当量の仕事を請け負っている大手米国コンサルティング会社ブーズ・アレン・ハミルトンのサーバーがアノニマスにハッキングされ、同日中に情報が流出した。「『ミリタリー・メルトダウン・マンデー』と名付けられたこの流出情報には、米中央軍事委員会、特殊作戦軍、海兵隊、さまざまな空軍施設、国土安全保障省、国務省職員、民間請負業者と思われる人々の軍人9万件のログイン情報が含まれている。」^{[24]これらの流出したパスワードはソルト}なしのSHA-1でハッシュ化されていたことが判明し、後にImpervaのADCチームによって分析され、軍人の中にも「1234」のような弱いパスワードを使用していた者がいたことが明らかになった。^[25]

2011年7月18日、Microsoft Hotmailはパスワード「123456」を禁止した。^[26]

2015年7月、「The Impact Team」と名乗るグループがアシュリー・マディソンのユーザーデータを盗んだ。^{[27]多くのパスワードは、比較的強力な}bcryptアルゴリズムと、より弱いMD5ハッシュの両方を使用してハッシュ化されていた。後者のアルゴリズムを攻撃することで、パスワードクラッキンググループCynoSure Primeは約1100万のプレーンテキストパスワードを復元することができた。^[28]

パスワードが破られるのを防ぐ方法の 1 つは、ハッシュ化されたパスワードにさえ攻撃者がアクセスできないようにすることです。たとえば、Unix オペレーティング システムでは、ハッシュ化されたパスワードは元々、公開ファイルに保存されていました/etc/passwd。一方、最近の Unix (および類似の) システムでは、ハッシュ化されたパスワードはシャドウ パスワードファイルに保存され/etc/shadow、拡張された権限 (つまり、「システム」権限) で実行されているプログラムのみがアクセスできます。これにより、悪意のあるユーザーがハッシュ化されたパスワードを最初に入手することは難しくなりますが、このような保護にもかかわらず、パスワード ハッシュのコレクションが多数盗まれています。また、一般的なネットワーク プロトコルの中には、パスワードを平文で送信したり、弱いチャレンジ/レスポンス方式を使用したりしているものもあります。^{[29] [30]}

ハッシュに組み込まれる各パスワードに固有のランダムな値であるソルトを使用すると、複数のハッシュが同時に攻撃されるのを防ぎ、レインボーテーブルなどの事前に計算された辞書の作成も防ぎます。

もう 1 つのアプローチは、サイト固有の秘密鍵とパスワードハッシュを組み合わせることです。これにより、ハッシュ値が盗まれた場合でも、平文のパスワードの復元を防止できます。ただし、保護されたハッシュファイルを盗む権限昇格攻撃によって、サイトの秘密が漏洩する可能性もあります。3 つ目のアプローチは、パスワードが推測される可能性を減らす鍵導出関数を使用することです。 ^{[31] : 5.1.1.2}

現代の Unix システムでは、従来のDESベースのパスワードハッシュ関数crypt() を、crypt-SHA、bcrypt、scryptなどのより強力な方法に置き換えています。^[32]他のシステムもこれらの方法を採用し始めています。たとえば、Cisco IOS は当初、パスワードの暗号化に可逆なVigenère 暗号を使用していましたが、現在は「enable secret」コマンドが使用されるときに 24 ビットのソルトを持つ md5-crypt を使用しています。^[33]これらの新しい方法では、大きなソルト値を使用して、攻撃者が複数のユーザーアカウントに対して同時にオフライン攻撃を効率的に実行できないようにします。また、アルゴリズムの実行速度がはるかに遅いため、オフライン攻撃を成功させるのに必要な時間が大幅に長くなります。^[34]

MD5やSHAファミリなど、パスワードの保存に使用されるハッシュの多くは、メモリ要件が低く、ハードウェアで効率的に実装され、高速に計算できるように設計されています。これらのアルゴリズムの複数のインスタンスをグラフィックス プロセッシング ユニット (GPU) で並列に実行できるため、クラッキングが高速化されます。その結果、高速ハッシュは、ソルトを使用してもパスワード クラッキングを防ぐのに効果的ではありません。PBKDF2やcrypt-SHAなどの一部のキー ストレッチアルゴリズムは、パスワード ハッシュを反復的に計算し、反復回数が十分に多い場合は、パスワードをテストできる速度を大幅に削減できます。scrypt などのその他のアルゴリズムはメモリに負担がかかり、時間のかかる計算に加えて比較的大量のメモリが必要になるため、GPU やカスタム集積回路を使用してクラッキングするのがより困難です。

2013年にパスワードハッシュの新しい標準アルゴリズムを選択するための長期パスワードハッシュコンペティションが発表され、 ^{[35] 2015年に}Argon2が優勝者に選ばれました。別のアルゴリズムであるBalloonはNISTによって推奨されています。^[36]どちらのアルゴリズムもメモリが困難です。

セキュリティ トークンなどのソリューションは、パスワードを常に変更することで、正式な証明の回答^{[説明が必要]}を提供します。これらのソリューションは、ブルート フォース攻撃に使用できる時間枠を大幅に短縮します(攻撃者は 1 回のシフトでパスワードを破って使用する必要があります)。また、有効期間が短いため、盗まれたパスワードの価値も低下します。

パスワードクラッキングソフトウェアツールは数多くありますが、最も人気のあるものは^[37] Aircrack-ng、Cain & Abel、John the Ripper、Hashcat、Hydra、DaveGrohl、ElcomSoftです。多くの訴訟支援ソフトウェアパッケージにもパスワードクラッキング機能が含まれています。これらのパッケージのほとんどは、クラッキング戦略を組み合わせて使用​​しており、ブルートフォース攻撃と辞書攻撃を組み合わせたアルゴリズムが最も効果的であることが証明されています。^[38]

コンピュータの処理能力が向上し、初心者でも簡単に使用できる自動パスワードクラッキングソフトウェアがさまざまな保護スキームで利用できるようになったことで、スクリプトキディによる攻撃が可能になった。^[39]

• ブルートフォース攻撃
• コールドブート攻撃
• 辞書攻撃
• パスワードの強度
• スマッジ攻撃

• フィリップ・エクスリン: 暗号解読の時間とメモリのトレードオフを高速化する。CRYPTO 2003: pp617–630
• 2011 年に The Anonymous と LulzSec が行ったリークのまとめ
• 国際パスワード会議
• パスワードセキュリティ: 過去、現在、未来、Passwords12 プレゼンテーション
• Skullsecurity の侵害されたパスワードコレクションのリスト