ハードウェアクラッキングに耐えられるハッシュアルゴリズムにはどのようなものがありますか?

序文

ブルートフォース クラッキング ツール hashcat を使用したことがある人なら誰でも、このソフトウェアの威力が CPU よりもはるかに高速な GPU コンピューティングをフル活用する能力にあることを知っています。したがって、WiFi ハンドシェイク パケットとデータベース内のパスワード ハッシュ値をクラッキングする場合、計算効率が大幅に向上します。

もちろん、GPU はまだ汎用ハードウェアであり、明らかにまだ最適化されていません。特定のアルゴリズム用に特定のハードウェアを構築すると、効率が数桁高くなる可能性があります。ビットコインマイニングマシンが良い例です。

ハードウェアは今も改良が続けられており、システムのセキュリティレベルが向上しなければ、ブルートフォースクラッキングはますます容易になるでしょう。したがって、「ハードウェアクラッキング」に耐えられるハッシュアルゴリズムが非常に必要です。

時間コスト

ハードウェアとの戦い方を議論する前に、まずは過去の「ブルートフォースクラッキング」との戦い方について説明しましょう。

MD5、SHA256 などの古典的なハッシュ アルゴリズムの中には、計算速度が非常に速いものがあります。パスワード ハッシュでこのタイプの関数を使用すると、攻撃者は将来辞書を実行するときに非常に高速化できます。十分に強力でないパスワードは簡単に解読される可能性があります。

この状況を緩和するために、暗号学者は「ストレッチング」という概念を導入しました。これは、ハッシュを複数回繰り返して計算時間を増やすというものです。

たとえば、PBKDF2 アルゴリズムはこの考え方を利用しています。その原理は非常に単純で、指定された関数 F を N 回繰り返します。

関数PBKDF2(F, ..., N)  
 ...  
 i = 0からNまで 
 ...  
 x = F(x, ...)  
 ...  
 ...  
 xを返す

これにより、ハッシュの時間コストを柔軟に設定できます。たとえば、これを 10,000 に設定すると、開発者にとっては計算時間が数十ミリ秒増加するだけですが、攻撃者にとってはクラッキング速度が 10,000 分の 1 に低下します。

時間コスト制限

PBKDF2 は確かに非常に効果的ですが、ハードウェア クラッキングに対する対策は提供していません。

PBKDF2 は元の関数の単純なラッパーに過ぎず、それをさらに数回実行するためです。元の機能がハードウェアに対抗できない場合は、PBKDF2 のレイヤーを適用しても機能しません。

たとえば、WiFi WPA2 プロトコルでは、HMAC-SHA1 を 4096 回繰り返すことができます。

 DK = PBKDF2(HMAC−SHA1,パスワード, SSID, 4096, ...)

単一のハッシュよりも数千倍遅いですが、ハードウェアクラッキングを防ぐことはできません。

ハードウェアは、その「高い同時実行性」を活用して、各スレッドが異なるパスワードの PBKDF2 を計算できるようにすることができます。

確かに時間の消費は何倍にも増加しましたが、ハードウェアのパフォーマンスには影響していません。同じクラッキング効率でも CPU よりはるかに高くなります。

したがって、時間コストは「ハードウェアクラッキング」に抵抗できません。

スペースコスト

コンピューティング性能だけから見ると、このハードウェアは非常に強力ですが、他の要素を考慮すると、それほど強力ではない可能性があります。

ハードウェアが同時に 100 個のスレッドを開いてクラッキングできるが、合計メモリが 100 MB しかないとすると、これは明らかに大きな欠点です。

空間複雑度が 2M の PBKDF アルゴリズムがある場合、メモリ不足のためスレッドの半分は実行できなくなります。

極端に言えば、空間複雑度を 100M に増やすと、ハードウェア全体で 1 つのスレッドしか開けなくなり、計算能力の 99% が使用できなくなります。

このように、ハードウェアの計算性能がどれだけ強力であっても、最終的にはメモリのボトルネックで行き詰まってしまいます。

しかし、アルゴリズムが大量のメモリを消費しながらも、簡単にバイパスされないようにするにはどうすればよいでしょうか? 以下に簡単な例を示します。

関数MemoryHard(..., M)  
整数 スペース[M]  
 i = 0 .. 10000の場合 
 x = ハッシュ(x, ...)  
スペース[ int (x) % M] ^= int (x)  
ハッシュ(スペース)を返す

もちろん、この例は適当に書いたもので、厳密なものではありません。しかし、主なアイデアは次のとおりです。

• スペースコストMを導入し、対応するメモリを要求した
• 古典的なハッシュ関数の結果を配列インデックスとして使用してメモリを読み書きする
• メモリの読み取りと書き込みはすべて最終結果に影響します

ハッシュ関数の結果は予測不可能であるため、どの場所がアクセスされるかを事前に知ることは不可能です。十分なメモリを用意することによってのみ、O(1) のアクセス速度を実現できます。

同じ速度を達成するには、攻撃者は同じ量のメモリを消費する必要があります。

空間と時間のトレードオフ

通常、ハードウェアの「コンピューティング リソース」は「ストレージ リソース」よりもはるかに豊富であるため、「時間とスペースを交換する」戦略、つまりより複雑なストレージ管理メカニズムを使用してスペースの割り当てを減らし、より多くのスレッドを開始できるようにする戦略を検討できます。

たとえば、スペースを 50% 節約する代わりに速度を 40% 犠牲にすると、次のようになります。

スペースコストが以前の半分になったため、2 倍のスレッドを開始できます。減価償却を考慮しても、最終速度は依然として 20% 増加しました。

もちろん、パフォーマンス低下率 > スペース圧縮率の場合、このソリューションは意味をなさなくなります。

アクセスボトルネック

実際、メモリには容量だけでなく、アクセス頻度にも制限があります。

メモリ自体に関しては、1 秒あたりの読み取りと書き込みの回数に上限があります。第二に、コンピューティング ユニットとメモリ間の相互作用が大きなボトルネックとなります。

MD5 や SHA256 などのハッシュ関数は、空間複雑度が非常に低くなります。ハードウェアをクラッキングする場合、各コンピューティング ユニットは独自のレジスタとキャッシュにのみ依存する必要があり、メモリにアクセスする必要はほとんどありません。

しかし、メモリハード機能の場合はそれほどスムーズではありません。大量のメモリを消費するだけでなく、メモリに非常に頻繁に「ランダムアクセス」するため、キャッシュにヒットすることが困難です。つまり、ほぼすべてのアクセスにはメモリとのやり取りが必要となり、多くの帯域幅が消費されます。

複数のコンピューティング ユニットが頻繁にアクセスすると、メモリ帯域幅がボトルネックになります。これにより同時実行も抑制されます。

たとえば、bcrypt アルゴリズムは同様の考え方を採用しており、計算プロセス中に 4KB のメモリ空間に頻繁にアクセスし、帯域幅リソースを消費します。

しかし、ハードウェアの発展に伴い、bcrypt の利点は徐々に減少しています。メモリ サイズをより柔軟に設定するために、時間コストとスペース コストの両方を備え、より永続的に耐性を持つ scrypt アルゴリズムが導入されました。

もちろん、スペースコストは絶対的に効果的というわけではありません。攻撃者が、どんな犠牲を払ってでも十分なストレージ「容量」と「帯域幅」を備えたハードウェア デバイスを作成するつもりであれば、クラッキングは依然として効率的に実行できます。

平行次元

過去 10 年間でメモリ容量は数倍に増加しましたが、CPU 周波数はあまり増加していません。物理的要因の制約により、メイン周波数を上げることは難しく、マルチコアに向けてのみ発展することができます。

ただし、PBKDF2 などのアルゴリズムでは、各ハッシュが前のハッシュ結果に依存するため、シングルスレッド計算しか使用できません。このシリアル モードは複数のタスクに分割できないため、マルチスレッドの利点を享受できません。

つまり、時間コストが最終的にボトルネックに達することになります。

マルチスレッドは本当にこれに対して何もできないのでしょうか?

単一の PBKDF を分割することはできませんが、相互に依存しない複数の PBKDF が必要になる場合があります。ここでマルチスレッドが役に立ちます。

たとえば、PBKDF をカプセル化すると、4 つの完全に独立した計算を実行し、その結果を結合する必要があります。

関数Parall(パスワード、ソルト、...)  
 -- この部分は並列化できます --    
 i = 0 .. 4の場合 
 DK[i] = PBKDF(パスワード, ソルト + i, ...)  
 ------------------    
ハッシュ(DK)を返す

このようにして、4 つのスレッドを開始し、これら 4 つの PBKDF を同時に計算できます。

これまでの4秒間の強さを1秒で手に入れることができるようになりました！攻撃者が破った場合、コストは4倍に増加します。

今日の主流のパスワード ハッシュ関数はすべて「並列次元」をサポートしています。たとえば、scrypt や、より高度な argon2 は、パラメーター p を通じて設定できます。

スレッドオーバーヘッド

実際には、スペースコストも考慮する必要があるため、スレッド数は並列処理の次元と同じではない場合があります。

上記の PBKDF のスペースコストが 512 MB であると仮定すると、4 つのスレッドを開くと 2 GB のメモリを占有することになります。ユーザーが 1.5 GB の空きメモリしか持っていない場合は、2 つのスレッドのみを開く方がスムーズになります。

もちろん、3 つのスレッドを開くこともできますが、これでは速くなりますか? もちろんそうではありません!

4 つのタスクが 3 つのスレッドに分割されるため、常に 1 つのスレッドで 2 つのタスクを実行する必要があり、最終的な時間は短縮されません。代わりに、スレッドの作成、メモリの割り当てなどのオーバーヘッドが増加します。

scrypt アルゴリズムのオンラインデモはこちらです: https://etherdream.github.io/webscrypt/example/basic/

時間と空間のコスト (N)、並列次元 (P)、スレッド数 (Thread) がコンピューティングに与える影響を体験できます。

まとめ

ここまで、ひび割れを防ぐ3つの要素について説明しました。

• 時間コスト（反復回数）
• スペースコスト（メモリ容量、帯域幅）
• 並列ディメンション (マルチスレッド リソース)

おそらく、ハッシュ アルゴリズムにさらに多くのハードウェア機能を組み込めるようにするというアイデアをすでに実現しているでしょう。このように、総合的なパフォーマンスが高いハードウェアだけがスムーズに動作し、特定の機能向けに構築されたハードウェアではボトルネックが発生します。

この考え方に従って、想像力を働かせることもできます。アルゴリズムが多くの条件分岐命令を使用し、CPU が強力な分岐予測機能を備えていると仮定します。これにより、アルゴリズムは CPU 上で実行する場合、非常に高いパフォーマンスを実現できますが、他の合理化されたハードウェア上では実現できません。

もちろん、これは単なる想像であり、独自の暗号化アルゴリズムを作成することはお勧めできません。実際には、argon2、scrypt などのより信頼性の高いアルゴリズムを使用する必要があります。

応用

この記事で紹介した対策はすべてハードウェアの消費に基づいています。しかし、そうすることで、1,000人の敵が負傷するだけでなく、800人の自国民も負傷することになります。

サーバーがパスワードをハッシュするのに毎回 1 秒と 1 GB のメモリを費やす必要がある場合、数十人が同時にアクセスするとシステムがそれをサポートできない可能性があります。

サーバー リソースを無駄にせずに高コストのハッシュを使用する方法はありますか? 実際、パスワード ハッシュはクライアント側で計算できます。

 DK = Client_PBKDF(パスワード、ユーザー名、コスト...)

パスワードとDKの対応が一意であるためです。アカウント登録時に DK を送信します。ログイン時に送信した DK が同じであれば、パスワードが同じであることが証明されます。

したがって、クライアントは元のパスワードを提供する必要がなく、サーバーも認証できます。これが「ゼロ知識証明」です。このソリューションを使用すると、ネットワーク盗聴やサーバー上の悪意のあるプログラムなどによるパスワード漏洩のリスクをさらに軽減できます。

もちろん、サーバーは DK を受信した後、すぐにそれを保存することはできません。 DK が漏洩した場合、攻撃者はパスワードを知らなくても、それを使用してユーザーのアカウントにログインできるためです。

そのため、サーバーは DK に対してハッシュ処理を実行する必要があります。

ただし、今回必要なのは高速ハッシュ関数だけです。 DK は不規則なデータ（エントロピーが高い）なので、辞書を実行しても復元できず、単純なハッシュで保護できます。

このようにして、サーバーは最小限のコンピューティング オーバーヘッドで強力なパスワード セキュリティを実現できます。

将来、データベースがドラッグされたとしても、攻撃者は次のハッシュ関数を使用してのみ辞書を実行できます。

 f(x) => server_hash( client_hash(x) )

client_hash が使用されているため、この最終関数はハードウェア クラッキングにも耐性があります。

デモ

上記のアイデアに基づいて、私の仮想空間に置いた簡単なデモンストレーションを以下に示します: http://www.etherdream.com/webscrypt/example/login/

（そしてバックグラウンドプログラムとデータは公開されており、データベースに引き込まれるシナリオをシミュレートします）

実際、この仮想空間の構成は非常に低いですが、これは高強度パスワードの実現には影響しません。コンピューターの構成が高く、ブラウザのバージョンが新しい限り、それで十分です。

これらはすべて、これ以上弱くすることができないデジタル パスワードですが、コストは MD5、SHA256 などを使用するよりも少なくとも 100 万倍高くなります。解読にどのくらいの時間がかかるか試してみてください。成功すると、赤い封筒が表示されます。