ブルートフォース攻撃の仕組み

暗号に対するブルートフォース攻撃では、正しい鍵が見つかるまで、考えられるすべての鍵を試します。nビットの鍵には2^n通りの鍵があります。3ビットの鍵なら可能性はわずか8通りですが、56ビットの鍵では72,000兆通りを超えます。ブルートフォース攻撃への基本的な防御は、総当たり探索が現実的な時間内には計算上実行不可能になるほど、十分に長い鍵を選ぶことです。

DES（Data Encryption Standard）は56ビットの鍵を使用し、鍵空間はおよそ7.2 * 10^16です。1977年当時、これは膨大な大きさに思われました。1998年には、EFFのDeep Crackマシンが250,000ドルで56時間以内にDESを解読しました。2006年には、専用クラスターを使えば10,000ドル未満で9日以内にDESを解読できました。教訓は明白でした。意欲のある攻撃者に対して、56ビットはもはや十分な安全性を提供しません。

AES-128は128ビットの鍵を使用するため、可能な鍵は2^128通り、約3.4 * 10^38通りあります。観測可能な宇宙にあるすべての原子が、ビッグバンの時点から毎秒10億個の鍵をテストするコンピューターになったとしても、探索が完了に近づくことはありません。将来、ハードウェアが指数関数的に高速化したとしても、128ビットの鍵は当面、古典的なブルートフォース攻撃に対して安全であり続けると予想されています。

オンライン総当たり攻撃は、認証リクエストを繰り返し送信して稼働中のシステムを標的にします。ネットワーク遅延、サーバーの応答時間、レート制限の影響を受けるため、処理には時間がかかります。オフライン総当たり攻撃は、パスワードハッシュのデータベースなど、盗み出されたデータに対して実行されます。攻撃者はハッシュを入手すると、ネットワークによる制約を受けず、ローカルのハードウェアを使って毎秒数十億もの候補をテストできます。

最新のGPUには、浮動小数点演算に最適化された数千個の並列処理コアが搭載されています。主要なGPUハッシュ解析ツールであるHashcatは、ハイエンドGPU 1台で毎秒1,000億個を超えるMD5ハッシュをテストできます。GPU 8台の構成であれば、毎秒8,000億個を超える候補をテストできます。そのため、適切に選ばれていないパスワードや脆弱なハッシュ関数は、オフラインで迅速に解析される危険があります。

特定用途向け集積回路（ASIC）は、1つの計算だけを実行するように設計されたチップです。Bitcoinのマイナーは、毎秒数十テラハッシュの速度でSHA-256ハッシュを計算するASICを使用しており、これはどのGPUよりもはるかに高速です。Bitcoin用ASICがパスワード解析とは異なる演算を行うとしても、原理は同じです。特定の暗号計算では、専用に設計されたハードウェアによって、汎用ハードウェアを桁違いに上回る高速化が実現します。

ムーアの法則は、トランジスタの集積密度が約2年ごとに倍増し、歴史的にはそれに伴って計算能力も同程度に向上することを示したものです。現在安全と見なされている鍵長は、将来数十年にわたるハードウェアの進歩に対しても安全であり続けなければなりません。そのため、セキュリティの推奨事項には大きな安全余裕が含まれています。AES-128が古典的な総当たり攻撃に対して脆弱になるには、計算能力が2^64倍になる必要があり、これはムーアの法則をどのように延長しても現実的には想定できない規模です。

NIST SP 800-57は、暗号アルゴリズムのセキュリティ強度を規定しています。112ビットのセキュリティ強度が、新しいシステムに対する現在の最低基準です。長期的な保護には128ビットのセキュリティ強度が推奨されます。256ビットの共通鍵は、現在予測できる古典計算機の脅威を上回る安全余裕を提供します。NISTは、80ビット以下のセキュリティレベルを推奨していません。これらは、新しいアプリケーションには不十分と見なされています。

Groverの量子探索アルゴリズムは、構造化されていない探索を二次的に高速化します。つまり、N個の要素からなる鍵空間を、Nステップではなく、およそsqrt(N)ステップで探索できます。AES-128では、量子攻撃者に対する実効安全性が64ビットまで低下します。AES-256では、Groverのアルゴリズムに対する実効安全性は128ビットです。そのため、ポスト量子セキュリティには256ビットの共通鍵が推奨されます。

Groverのアルゴリズムを実行する量子コンピューターに対して128ビットの安全性を維持するには、共通鍵の長さを少なくとも256ビットにする必要があります。AES-256はすでにこの長さであり、共通鍵暗号では量子計算機に対して安全と見なされています。参考までに、鍵長を128ビットから256ビットへ倍増しても、正規の利用者側の計算量は倍増しません（AESのラウンドが数回増えるだけです）。一方、攻撃者は量子リソースを二乗規模に増やす必要があります。

セキュリティチームは、攻撃者に悪用される前に脆弱な認証情報を特定するため、許可を受けたパスワード監査で総当たり攻撃ツールを使用します。HashcatやJohn the Ripperをエクスポートしたパスワードハッシュデータベースに対して実行し、どの程度の割合のパスワードが解析可能かを調べます。監査結果は、最小長の要件、複雑性のルール、bcryptやArgon2など最新のパスワードハッシュアルゴリズムの導入といった、パスワードポリシーの改善に役立ちます。

Groverの量子アルゴリズムは、AES-128の実効安全性にどのような影響を与えますか？

総当たり攻撃は考えられるすべての鍵を試すため、安全性を確保するには、現実的には列挙できないほど大きな鍵空間が必要です。56ビットのDESは1998年に破られました。2^128個の鍵を持つAES-128は、古典計算機では現実的に解析できません。GPUクラスターは、オフライン環境で毎秒数千億個のハッシュを解析できます。Groverの量子アルゴリズムはビット安全性を半減させるため、ポスト量子環境で128ビットの安全性を確保するには256ビットの鍵が必要です。NISTは、新しいシステムに対して最低128ビットのセキュリティ強度を推奨しています。