辞書攻撃とレインボーテーブル

辞書攻撃は、考えられるすべての組み合わせを試すのではなく、使われる可能性が高いパスワードを厳選したリストを試します。実際の利用者は、一般的な単語、人名、日付、フレーズなど、限られた語彙からパスワードを選ぶ傾向があります。使われる可能性が高いパスワード100万個のワードリストをテストする方が、8文字の文字列をすべて試す（200兆通り）よりはるかに高速です。辞書攻撃が成功するのは、人間が選ぶパスワードが予測しやすいためです。

2009年、ソーシャルネットワーキングサイトのRockYouが侵害され、3,200万件のユーザーパスワードが平文で流出しました。その結果作成されたリストは現在rockyou.txtと呼ばれており、およそ1,400万個の一意なパスワードが含まれています。これは、パスワード解析で最初に使われる標準的なワードリストです。rockyou.txtを調べると、最も一般的なパスワードは123456、password、そして人名の後ろに数字を付けたものだと分かります。

ハイブリッド攻撃は、変換ルールを適用して基本ワードリストを拡張します。たとえばpasswordは、Password、P@ssword、p4ssword、password1、password123など、数百種類のバリエーションに変換されます。Hashcatのルールエンジンでは、先頭文字を大文字にする、2桁の数字を追加する、文字を記号に置き換えるといった、適用する変換を正確に指定できます。これにより、完全にランダムな文字列を試さなくても、対象範囲を大幅に広げられます。

Leetスピークによる置換（文字を数字に置き換える方法：e=3、a=4、i=1、o=0、s=5）は、かつてパスワードの安全性を高めると考えられていました。ルールベースの解析ツールには、これらの置換が標準的な変換として含まれています。s3cur1tyのようなパスワードは、基本単語securityにLeet置換のルールを適用するだけで簡単に解析できます。解析ツールは、辞書にある単語の末尾に!、123、現在の年などを追加する一般的なパターンも試します。

レインボーテーブルは、ハッシュ値を元のパスワードに対応付ける、大規模な事前計算済みデータベースです。攻撃者は候補をハッシュ化して比較する代わりに、テーブルからハッシュを検索します。テーブルの構築には膨大な時間とストレージが必要ですが、各検索は瞬時に実行できます。8文字の英数字パスワードすべてに対するMD5のレインボーテーブルは数テラバイトに収まり、テーブルに一致するパスワードであれば数ミリ秒で解析できます。

レインボーテーブルは、時間とメモリのトレードオフを具体化したものです。最初に時間をかけてテーブルを計算し、その後はメモリを使って検索を高速化します。テーブルにはハッシュチェーンが保存されます。各チェーンは推測値から始まり、その値をハッシュ化し、還元関数を適用して別の推測値を生成する処理を繰り返します。チェーンの末尾だけを保存することで、ストレージと計算量のバランスを取りながら、チェーンを再構成してハッシュからパスワードを復元できます。

ソルトとは、ハッシュ化する前にパスワードへ追加するランダムな値です。ユーザーごとにソルトが異なるため、同じパスワードを使っている2人のユーザーでも、生成されるハッシュ値は異なります。これにより、攻撃者はソルト付きパスワード用のレインボーテーブルを事前計算できません。考えられるソルト値ごとに別のテーブルを構築する必要があり、計算量的に実行不可能だからです。安全なパスワード保存システムでは、ソルトの付与が必須です。

初期の多くのWebアプリケーションは、ソルトなしのMD5ハッシュとしてパスワードを保存していました。文字列passwordのMD5は5f4dcc3b5aa765d61d8327deb882cf99という固定値です。このハッシュを以前に見たことがある人や、事前計算済みデータベースで検索した人は、パスワードを瞬時に知ることができます。CrackStationのようなサイトは、事前計算済みのMD5およびSHA-1ハッシュを何十億件も保持しています。一般的なパスワードをソルトなしで保存した場合、1秒未満で解析されます。

セキュリティ研究者のTroy Huntが作成したHave I Been Pwned（HIBP）は、大規模なデータ侵害から流出したパスワードハッシュを集約しています。利用者は、自分のメールアドレスやパスワードが侵害に含まれていたかどうかを確認できます。開発者は、k-匿名性モデルを使用するHIBP APIで、候補パスワードを8億5,000万件の流出ハッシュと照合できます。SHA-1ハッシュの最初の5文字の16進数だけをAPIに送信し、サーバーが完全なハッシュを知ることなく、一致する後半部分を受け取ります。

クレデンシャルスタッフィング攻撃では、ある侵害で流出したユーザー名とパスワードの組み合わせを、別のサービスに対して試します。多くの利用者が複数のサイトで同じパスワードを使い回すため、セキュリティの低いサイトでの侵害から、銀行やメールなど価値の高い標的で有効な認証情報が得られることがあります。自動化ツールは、複数のサービスに対して毎秒数千回のログイン試行を送信します。レート制限と多要素認証が、クレデンシャルスタッフィングに対する主な防御策です。

安全なパスワード保存では、ソルトの付与と低速な適応型ハッシュ関数を組み合わせます。bcrypt、Argon2、scryptは計算コストが高くなるように設計されており、ハッシュ1回あたりマイクロ秒ではなくミリ秒を要します。これにより、攻撃者が毎秒実行できる試行回数を数十億回から数千回に制限できます。ハードウェアが高速化した場合はコストパラメータを引き上げることで、必要な作業量を一定に保てます。これらのアルゴリズムが、現在のパスワード保存における標準です。

辞書攻撃は、すべての組み合わせではなく、使われる可能性が高いパスワードをテストします。rockyou.txtには、実際の利用環境から得られた1,400万個の例が含まれています。ハイブリッド攻撃やルールベース攻撃は、変換によってワードリストを拡張します。レインボーテーブルを使うと、ソルトなしのハッシュを瞬時に検索できます。ソルトを付けるとハッシュごとに値が異なるため、レインボーテーブルを無効にできます。HIBPを使うと、パスワードが既知の侵害に含まれているか確認できます。安全に保存するには、bcryptやArgon2などの適応型ハッシュ関数が必要です。