キーストレッチ

暗号学では、キーストレッチング技術は、各キーのテストに必要なリソース（時間と場合によってはスペース）を増やすことで、弱い可能性のあるキー（通常はパスワードまたはパスフレーズ）をブルートフォース攻撃に対してより安全にするために使用されます。人間が作成したパスワードまたはパスフレーズは、パスワードクラッキングを許すほど短かったり予測可能であったりすることが多く、キーストレッチングは、単一のパスワード候補を試すという基本的な手順を複雑にすることで、そのような攻撃をより困難にすることを目的としています。キーストレッチングは、ブルートフォース攻撃者の観点から長いキー長を模倣することで、キーの長さが制限されている実際のアプリケーションでもセキュリティを向上させます。^[1]

キーストレッチングにはいくつかの方法があります。1つは、暗号ハッシュ関数またはブロック暗号をループで繰り返し適用することです。たとえば、キーが暗号に使用されるアプリケーションでは、暗号のキースケジュールを変更して、実行に特定の時間がかかるようにすることができます。もう1つの方法は、大量のメモリを必要とする暗号ハッシュ関数を使用することです。これは、メモリに縛られた攻撃者による攻撃を阻止するのに効果的です。^[2]

プロセス

キーストレッチアルゴリズムは、入力キーを受け取り、ランダム性と長いキー長を模倣したストレッチ暗号（拡張キーと呼ばれる^{[引用が必要]}）を生成するためにかなりの労力を費やすアルゴリズムに依存しています。アルゴリズムには既知のショートカットがないため、入力と暗号を関連付ける最も効率的な方法は、キーストレッチアルゴリズム自体を繰り返すことです。これにより、ブルートフォース攻撃者は試行ごとに同じ労力を費やすことになります。この追加の労力が、特定のキー長を持つすべてのキーをブルートフォースキー検索する場合と比較される場合、入力キーは同じ長さだけストレッチされていると説明できます。 ^[1]

キーストレッチングにより、攻撃者には次の 2 つの選択肢が残されます。

強化された鍵の可能な組み合わせを試みるが、強化された鍵が十分に長く予測不可能な場合（つまり、アルゴリズムがランダム性を模倣しているため、攻撃者は拡張された鍵空間全体を試行しなければならない場合）には実行不可能である^[3]
弱い初期キーの可能な組み合わせを試し、初期キーがパスワードまたはパスフレーズの場合は辞書攻撃から始まる可能性がありますが、攻撃者が試行ごとに追加する労力により、コストのかかる計算とメモリ消費が予想される利益を上回った場合、攻撃は非経済的になる可能性があります。

攻撃者がユーザーと同じクラスのハードウェアを使用している場合、各推測の処理には、ユーザーが要したのと同程度の時間がかかります (たとえば、1 秒)。攻撃者がユーザーよりもはるかに多くのコンピューティングリソースを持っている場合でも、キーストレッチによって攻撃者の処理速度は低下しますが、正当なユーザーによるシステムの使いやすさに重大な影響はありません。これは、ユーザーのコンピューターは、ユーザーがパスワードを入力すると 1 回だけストレッチ関数を計算すればよいのに対し、攻撃者は攻撃で推測するたびにストレッチ関数を計算する必要があるためです。

このプロセスでは、元のキー空間エントロピーは変更されません。キーストレッチングアルゴリズムは決定論的であり、弱い入力では常に同じ強化キーが生成されますが、強化キーの組み合わせは入力キー空間と同じ数に制限されます。したがって、この攻撃は、強化キー空間の複数のインスタンスを並列にターゲットとするレインボーテーブルの開発など、特定の時間とメモリのトレードオフに対して保護されていない場合は脆弱なままです（事実上、アルゴリズムを繰り返すための近道です）。このため、キーストレッチングはソルトと組み合わせられることがよくあります。^[1]

ハッシュベース

多くのライブラリは、関数の一部としてキーストレッチングを実行する関数を提供しています。例としてはcrypt(3)を参照してください。 ^[4] PBKDF2はパスワードから暗号化キーを生成するためのもので、必ずしもパスワード認証用ではありません。出力ビット数がPBKDF2で使用される内部ハッシュアルゴリズム（通常はSHA-2（最大512ビット））以下であれば、PBKDF2は両方の目的に使用できます。また、静的データを暗号化するための暗号化キーとしても使用できます。^[5]

強さと時間

これらの例では、コンシューマ CPU が 1 秒間に約 65,000 回のSHA-1ハッシュを実行できることを前提としています。したがって、キーストレッチを使用するプログラムは 65,000 ラウンドのハッシュを使用し、ユーザーを最大 1 秒遅らせることができます。

試行パスワードまたはパスフレーズをテストするには、通常、ハッシュ操作が 1 回必要です。ただし、キーストレッチングが使用されている場合、攻撃者はテストするキーごとに強化キーを計算する必要があり、テストごとに 65,000 個のハッシュを計算する必要があります。これにより、攻撃者の作業負荷は 65,000 倍、約 2 ^{16 倍}に増加します。つまり、強化キーはキー強度が約 16 ビット増加することになります。

ムーアの法則によれば、コンピュータの速度はおよそ 2 年ごとに 2 倍になります。この仮定では、2 年ごとに 1 ビットのキー強度が総当たり攻撃で解読可能になります。つまり、16 ビットの強度が増すと、約 16×2 = 32 年後にクラッキングされることになりますが、同じレベルのセキュリティを維持するには、システムが使用するキーストレッチラウンドの数を約 2 年ごとに 2 倍にする必要があることも意味します (ほとんどのキーは必要以上に安全であるため、一貫した確定的なキー生成を必要とするシステムでは、キーストレッチで使用される反復回数を更新しない可能性があります。このような場合、設計者はキー導出システムを変更せずにどのくらいの期間使用するかを考慮し、システムの寿命に合わせて適切なハッシュ数を選択する必要があります)。

CPU 依存のハッシュ関数は、ハードウェア実装に対して依然として脆弱です。SHA-1 のこのような実装は、わずか 5,000 ゲート、400 クロックサイクルで実現されています。^[6]数百万ゲートのFPGAが100 ドル未満で購入できるため、^[7]攻撃者は完全にアンロールされたハードウェアクラッカーを約 5,000 ドルで構築できます。^[要出典]このような設計は、100 MHz で動作し、約 300,000 キー/秒をテストできます。攻撃者は、価格と速度の妥協点を自由に選択できます。たとえば、2,500 ドルで 150,000 キー/秒の設計を選択できます。^{[要出典]このような状況では、キーストレッチによって攻撃者の速度が低下します。5,000 ドルの設計でストレート SHA-1 ハッシュを攻撃すると、300,000÷2}¹⁶ ≈ 4.578 キー/秒を試行できます。 ^[要出典]

同様に、現代のコンシューマーGPUはハッシュを大幅に高速化できます。たとえば、ベンチマークでは、Nvidia RTX 2080 SUPER FEは1秒あたり100億を超えるSHA1ハッシュを計算します。^[8]

ハードウェアアプローチに対する防御として、メモリバウンド暗号化関数が開発されました。これらの関数は、キャッシュを無効にしてしまう方法で大量のメモリにアクセスします。大量の低レイテンシメモリは高価なので、潜在的な攻撃者はこのような攻撃を思いとどまります。

歴史

最初の意図的に遅いパスワードベースのキー導出関数「CRYPT」は、1978年にRobert MorrisによってUnixパスワードの暗号化用に記述されました。 ^[9]この関数は、反復回数25回、12ビットのソルト、およびサブ関数としてDESの変種を使用しました。(DES自体は、標準のDESハードウェアを使用した攻撃を阻止するために使用されませんでした。) パスワードは最大8つのASCII文字に制限されていました。当時としては大きな進歩でしたが、CRYPT(3)は現在では不十分であると考えられています。PDP -11時代に設計された反復回数は低すぎ、12ビットのソルトは不便ですが、事前計算された辞書攻撃を阻止できず、8文字の制限により、より強力なパスフレーズを使用できません。

PBKDF2などの最新のパスワードベースの鍵導出関数は、SHA-2などの暗号ハッシュ、より長いソルト（例：64ビット）、および高い反復回数を使用します。米国国立標準技術研究所（NIST）は、最小反復回数を10,000回と推奨しています。^[10]^{: 5.1.1.2} 「特に重要な鍵、または非常に強力なシステムやユーザーが認識するパフォーマンスが重要ではないシステムの場合、反復回数は10,000,000回が適切である可能性があります。」 ^[11]^{: 5.2}

2009年には、キーテストを高速化するためにカスタムの高度に並列化されたハードウェアの使用を制限することを目的として、メモリを大量に消費するキー強化アルゴリズムであるscryptが導入されました。^[12]

2013年、グラフィックプロセッサや特殊用途ハードウェアからの攻撃に耐える改良されたキーストレッチ標準を選択するためのパスワードハッシュコンペティションが開催されました。優勝者は2015年7月1日にArgon2に選ばれました。^[13]

キーストレッチを使用する一部のシステム

一部のディスク暗号化ソフトウェア（すべてではありません）（ディスク暗号化ソフトウェアの比較を参照）
7-ジップ^[14]
Apache .htpasswd "APR1" とOpenSSL "passwd" は、1000 ラウンドのMD5キーストレッチを使用します。
KeePassとKeePassXC、オープンソースのパスワード管理ユーティリティ。2020年現在、最新バージョンではデフォルトで1秒のキーストレッチ遅延を備えたArgon2dを使用しています。 ^[15]^[16]
Linuxやその他のUnix系システムでは、デフォルトで5000回のSHA256またはSHA512ハッシュ反復を実行するSHAcryptモードが提供されており、最小値は1000、最大値は999,999,999です。^[17]
Password Safe オープンソースのパスワードマネージャー。
PGP、GPG暗号化ソフトウェア。GPGはデフォルトでハッシュを65536回反復します。^[18]
個人モードのWi-Fi Protected Access (WPA および WPA2) ワイヤレス暗号化プロトコルでは、4096 回の反復を持つPBKDF2が使用されました。(WPA3 では、パスワードハッシュを公開しないと主張する同時同等認証が使用されます。)

参照

キー導出関数– キーストレッチングを使用することが多い
- PBKDF2、bcrypt、scrypt、Argon2 – 広く使用されているキーストレッチアルゴリズム
ハッシュチェーン

参考文献

^ abc ケルシー、ジョン、シュナイアー、ブルース、ホール、クリス、ワグナー、デビッド A. (1997)。「低エントロピー鍵の安全な応用」。オカモト、エイジ、ダビダ、ジョージ I.、マンボ、マサヒロ (編)。情報セキュリティ、第 1 回国際ワークショップ、ISW '97、辰口、日本、1997 年 9 月 17 ～ 19 日、議事録。コンピュータサイエンスの講義ノート。第 1396 巻。シュプリンガー。pp. 121 ～ 134。doi :10.1007/ BFb0030415。ISBN 978-3-540-64382-1。
^ Reinhold, Arnold (1999 年 7 月 15 日)。「HEKS: キーストレッチングアルゴリズムのファミリー」(PDF)。
^ McMillan, Troy (2022-07-07). CompTIA Advanced Security Practitioner (CASP+) CAS-004 認定ガイド. ピアソン IT 認定. ISBN 978-0-13-734870-1。
^ crypt(3) – FreeBSDライブラリ関数マニュアル
^ Moriarty, Kathleen (2017). 「PKCS #5: パスワードベースの暗号化仕様、バージョン 2.1」
^ O'Neill, Máire. 「RFID タグ用の低コスト SHA-1 ハッシュ関数アーキテクチャ」(PDF) 。2012 年 3 月 19 日のオリジナル(PDF)からアーカイブ。
^ 「新しい 90nm Xilinx Spartan-3 FPGA が半導体業界を一変させる (0333) : Xilinx プレスリリース」。2011 年 7 月 16 日時点のオリジナルよりアーカイブ。2010年 8 月 8 日に閲覧。
^ https://gist.github.com/epixoip/47098d25f171ec1808b519615be1b90d 、PBKDF2-HMAC-SHA1 を 1,000 回反復すると、速度 5,164.9 kH/s で 2,002 SHA-1 ハッシュが生成され、1 秒あたり 10,340,129,800 SHA-1 ハッシュになります。
^ Morris, Robert; Thompson, Ken (1978-04-03). 「パスワードセキュリティ: 事例研究」. Bell Laboratories . 2003-03-22 時点のオリジナルよりアーカイブ。2011-05-09に閲覧。
^ Grassi Paul A. (2017 年 6 月). SP 800-63B-3 – デジタル ID ガイドライン、認証、ライフサイクル管理。NIST。doi : 10.6028 /NIST.SP.800-63b。
^ Meltem Sönmez Turan、Elaine Barker、William Burr、Lily Chen (2010 年 12 月)。SP 800-132 – パスワードベースのキー導出に関する推奨事項、パート 1: ストレージアプリケーション。NIST。doi :10.6028/ NIST.SP.800-132。{{cite book}}: CS1 maint: multiple names: authors list (link)
^ Percival, Colin (2009). scrypt: 新しい鍵導出関数。BSDCan 2009。2024年6月29日時点のオリジナルよりアーカイブ。
^ パスワードハッシュコンテスト
^ 「7zフォーマット」。
^ KBDF4 より
^ KeePassXC—初めてのデータベース作成
^ Drepper, Ulrich. 「SHA-256 と SHA-512 を使用した Unix 暗号化」
^ RFC 4880

[ISW97-1] ケルシー、ジョン、シュナイアー、ブルース、ホール、クリス、ワグナー、デビッド A. (1997)。「低エントロピー鍵の安全な応用」。オカモト、エイジ、ダビダ、ジョージ I.、マンボ、マサヒロ (編)。情報セキュリティ、第 1 回国際ワークショップ、ISW '97、辰口、日本、1997 年 9 月 17 ～ 19 日、議事録。コンピュータサイエンスの講義ノート。第 1396 巻。シュプリンガー。pp. 121 ～ 134。doi :10.1007/ BFb0030415。ISBN 978-3-540-64382-1。

[2] Reinhold, Arnold (1999 年 7 月 15 日)。「HEKS: キーストレッチングアルゴリズムのファミリー」(PDF)。

[3] McMillan, Troy (2022-07-07). CompTIA Advanced Security Practitioner (CASP+) CAS-004 認定ガイド. ピアソン IT 認定. ISBN 978-0-13-734870-1。

[4] crypt(3) – FreeBSDライブラリ関数マニュアル

[5] Moriarty, Kathleen (2017). 「PKCS #5: パスワードベースの暗号化仕様、バージョン 2.1」

[6] O'Neill, Máire. 「RFID タグ用の低コスト SHA-1 ハッシュ関数アーキテクチャ」(PDF) 。2012 年 3 月 19 日のオリジナル(PDF)からアーカイブ。

[7] 「新しい 90nm Xilinx Spartan-3 FPGA が半導体業界を一変させる (0333) : Xilinx プレスリリース」。2011 年 7 月 16 日時点のオリジナルよりアーカイブ。2010年 8 月 8 日に閲覧。

[8] ttps://gist.github.com/epixoip/47098d25f171ec1808b519615be1b90d 、PBKDF2-HMAC-SHA1 を 1,000 回反復すると、速度 5,164.9 kH/s で 2,002 SHA-1 ハッシュが生成され、1 秒あたり 10,340,129,800 SHA-1 ハッシュになります。

[9] Morris, Robert; Thompson, Ken (1978-04-03). 「パスワードセキュリティ: 事例研究」. Bell Laboratories . 2003-03-22 時点のオリジナルよりアーカイブ。2011-05-09に閲覧。

[sp800-63B-10] Grassi Paul A. (2017 年 6 月). SP 800-63B-3 – デジタル ID ガイドライン、認証、ライフサイクル管理。NIST。doi : 10.6028 /NIST.SP.800-63b。

[sp800-132-11] Meltem Sönmez Turan、Elaine Barker、William Burr、Lily Chen (2010 年 12 月)。SP 800-132 – パスワードベースのキー導出に関する推奨事項、パート 1: ストレージアプリケーション。NIST。doi :10.6028/ NIST.SP.800-132。{{cite book}}: CS1 maint: multiple names: authors list (link)

[12] Percival, Colin (2009). scrypt: 新しい鍵導出関数。BSDCan 2009。2024年6月29日時点のオリジナルよりアーカイブ。

[13] パスワードハッシュコンテスト

[14] 「7zフォーマット」。

[15] KBDF4 より

[16] KeePassXC—初めてのデータベース作成

[shacryptcode-17] Drepper, Ulrich. 「SHA-256 と SHA-512 を使用した Unix 暗号化」

[18] RFC 4880