負荷の高いサービスでパスワードをハッシュする方法。 Yandexの経験

Webサービスでのパスワードハッシュなどの問題について説明します。 一見すると、すべてがここで「明確」になっているように見えます。あなたは、よく考えた通常のアルゴリズムを使用し、少しのコードを書き、すべてを実稼働に移行する必要があります。 しかし、いつものように、問題に取り組み始めると、考慮しなければならない多くの落とし穴が生じます。 どれ？ それらの最初のものは、おそらく、アルゴリズムの選択です。それらの多くはありますが、それぞれに独自の特性があります。 第二-パラメータの選択方法 大きくて良い？ ユーザーへの応答時間はどうしますか？ どのくらいのメモリ、CPU、スレッド？ そして第三に、計算DoSをどうするか？ この記事では、これら3つの問題、Yandexに新しいパスワードハッシュアルゴリズムを導入した経験、および少量のコードについての私の考えを共有したいと思います。

攻撃者および防御者

アルゴリズムに移り、ハッシュスキームを構築する前に、Webサービスのセキュリティで自分が何を保護しているか、パスワードハッシュがどのような役割を果たすべきかを一般的に理解する必要があります。 通常、シナリオは、攻撃者が脆弱性のチェーンを介してWebサービス（または複数のWebサービス）を破り、ユーザーデータベースにアクセスし、そこにパスワードハッシュを確認し、データベースをダンプし、 GPU （およびまれに、 FPGAとASIC ）。



この場合、防御側は何をしますか？ まず、パスワードハッシュが侵害されたユーザーを送信し、接続された電話、メールなどを使用してパスワードの変更と追加の認証を強制します。この場合、適切なハッシュアルゴリズムは災害の規模を理解し、必要なすべてを起動する時間を与えますその結果、ユーザーアカウントが攻撃者にキャプチャされるのを防ぎます。

ハードウェア

上で説明したように、攻撃者はGPU、FPGA、ASICなどの機器を使用して計算を高速化できます。 私の意見では、非常に多くの人々が暗号通貨マイニング、3次元ゲームなどに興味を持っているため、このリストの中で最も危険なのはGPUです。GPUはパスワードハッシュの整理を開始する準備ができています。 また、FPGAは広く普及しておらず、高価であり、デバッグボードの機能が十分でないことが多く、自宅で何かをはんだ付けするのは通常非現実的です（高周波、はんだ付け品質の要件の増加など）。 そして最後に、ASICにはかなりの投資、設計、生産サイクルの立ち上げが必要です。 多くの場合、これは攻撃者がサービスをハッキングすることで取得できる情報のコストよりも高価になります。



さて、防御側は通常、Webアプリケーションを実行するサーバーCPUを使用します。 サーバーCPUには多くのコア（ただしGPUより小さい）、大きなL3キャッシュなどがあります。したがって、ハッシュアルゴリズムを開発する際の明確なアイデアは、CPU向けに最適化し、GPU、FPGA、およびASICでそれらを遅くすることです。 これらの減速方法の中で、次のものを区別できます。



1.大量のRAMの使用（GPU共有メモリでは制限され、グローバルメモリへの移動は非常に「高価」です。FPGAおよびASICでは、外部メモリをはんだ付けする必要があり、回路全体のコスト、アクセス遅延などの増加につながります）時間とメモリのトレードオフ（いわゆるメモリハードアルゴリズム）。



2. L1キャッシュに収まる小さなメモリ領域のランダムアドレスでの少量のデータの読み取り/記録の使用（GPUグローバルメモリから4バイトを読み取ろうとすると、実際には32バイトが読み取られ、GPUがメモリバスを浪費します） ）



3.乗算演算MULを使用します。 CPUでは、オフセットやADDなどの通常の操作と同じくらい高速ですが、FPGAおよびASICでは、より複雑な構成、データ処理の大きな遅延などにつながります。



4.いわゆる命令レベルの並列処理とハッシュアルゴリズムSIMDに適した設計を使用します。 最新のCPUは、SSE2、SSSE3、AVX2などのさまざまな高度な命令セットを搭載しているため、一度に複数の操作を実行し、計算を大幅に高速化できます。



リストされた手法は、すべてのアルゴリズムで使用されるわけではありません。 そのため、 Argon2 （ パスワードハッシュコンペティションの勝者）では、2つ目を除く上記のすべての手法が使用されます。 PHCコンテストで特別な評価を受けたYescryptは 、4つの手法すべてを使用します（ただし、特別な操作モードを有効にする必要があります）。



Argon2を選択したのは、このアルゴリズムが十分に研究されており、理解と実装が簡単で、x64とSIMDに最適化されているためです。

計算上のDoS問題

アルゴリズムが動作中に大量のメモリを使用し、一定のCPU時間を消費することが保証されている場合、小さなRPSがWebサービスを無効にしたり、ユーザーへの応答を大幅に遅くしたりする可能性がある場合、パラメーターの軽率な選択は計算上のDoS状況につながる可能性があります。 現実には、状況から抜け出す方法は多くありません。 それらのいくつかを次に示します。



1.「問題を鉄で埋める」-Webサービスが機能する多くのサーバーを追加します。 ある意味では、これは適切な負荷分散で計算DoSに対処するのに役立ちますが、この方法ではユーザーへの長い回答の問題は解決しません。 つまり、大量のリソースを追加しても応答時間は短縮されず、クラスターあたりのピークRPSが増加するだけです。 ご想像のとおり、これは私たちのやり方ではありません。



2.ハッシュアルゴリズムコードの最大最適化、 SIMD命令の使用など。



3.使用されているアルゴリズムパラメータを許容可能なレベルに減らします-パスワードハッシュスキーム全体のレベルでさまざまな緩和策を追加します。



明らかに、最後の2つのポイントは実行する価値があります。 高性能がそれほど重要ではない場合、最適化されたバージョンのアルゴリズムを使用すると、より多くのパラメーターを使用できるため、GPU、FPGA、ASICでパスワードを並べ替えることがさらに難しくなります。 また、パスワードハッシュスキームのレベルで緩和策を追加すると、ハッシュベースに対するオフライン攻撃が不可能（または少なくとも実行が困難）になり、攻撃者がネットワーク上にある場合にのみハッシュをソートできるため、検出と調査が容易になります事件。

プロトコルレベルの緩和

現在、ハッシュスキームレベルの緩和策は何ですか：



1.ローカルパラメータ（ローカルパラメータ）の使用。 このアイデアは非常に単純です-アルゴリズムに秘密パラメーターを追加する必要があります。これはデータベースではなく、アプリケーション（たとえば、環境変数）に保存されます。 したがって、攻撃者がパスワードハッシュを使用してデータベースにアクセスするだけでは不十分です。アプリケーションも破損する必要があります。 また、データベース管理者は、GPUを使用して自宅でハッシュをダンプして楽しむこともできません。



2.パスワードをハッシュするときに大きなROM（読み取り専用メモリ）を使用して、そこから値を混合します。 このアイデアは、大規模なパスワードハッシュのためのアルゴリズムの適応の1つとしてYescryptによって提案されました。 実際、100 GB程度のROMを使用する場合、それを盗むことは困難です。CPUをすばやく検索するには、100 GB以上のメモリを備えたサーバーが必要です。 GPU、FPGA、およびASICでは、すべてが低速になります。これは、大きなROMを使用するだけでなく、ハッシュアルゴリズムを最適化して、これらのタイプの機器などで低速になるためです。アイデアの欠点は、すべてを行う必要があることですこの大きなROMで生活する時間は、おそらくそれをなくすことはないでしょう。



3. CryptoAnchorsを使用する-1つの操作のみを実行する小さなマイクロサービス： HRFなどの秘密鍵を使用してPRFを使用します。 秘密鍵はマイクロサービスに保存され、決して残されません。 アイデアの本質は、マイクロサービスが小さくシンプルであるということです。 監査は簡単で、ハッキングは非常に難しいため、これを使用すると、オフライン攻撃をオンライン攻撃に変えることができます。 つまり、ハッシュベースを攻撃するには、攻撃者はネットワーク内にとどまり、このマイクロサービスにリクエストを送信する必要があります。







CryptoAnchorsのアイデアは、 Passwords Onionと呼ばれるFacebookパスワードハッシュスキームで使用されますが、インフラストラクチャの他の部分でも使用できます 。



4.いわゆる部分的忘却型PRFの使用 （実際、これはパラグラフ3の一部です）。 HMACのようなものでCryptoAnchorsを使用する場合、秘密鍵が侵害されたときに変更するという問題があります。 この問題を解決する1つの方法は、別のHMACレイヤーを作成することです。これにより、さまざまな不便が生じます。 さらに、従来のCryptoAnchorsの場合、このマイクロサービスは、アプリケーションが送信するすべてのハッシュを参照します。 つまり、サービスがハッキングされた場合、攻撃者はハッシュを純粋な形で収集し、オフライン攻撃を行うことができます。 これら2つの問題を解決するために、CornellTechの研究者は、 billinearペアリングに基づいた部分的忘却 PRFの使用を提案しました。 この設計により、秘密鍵を変更し、各ユーザーのリクエスト数のロギングと制限を整理できます。 同時に、マイクロサービスはハッシュを平文で表示しません。 詳しくは彼らの記事をご覧ください 。







つまり、アプリケーションはパスワードをハッシュし、ブラインドを使用してそれをマスクし、マスクされたパスワードをユーザーID tとともにマイクロサービスに渡すという考え方です。 マイクロサービスは、それだけが知っているキーkを使用してこれらの値にbillinearペアリングを適用し、結果をアプリケーションに転送します。アプリケーションは、ブラインド解除（マスク解除）を適用し、結果をデータベースに保存されているものと比較できます。 billinearペアリングの線形性により、POPRFを使用したマイクロサービスは、キーを更新するためのトークンをアプリケーションに提供でき、アプリケーションはデータベースを通過してレコードを更新できます。

パフォーマンスの最適化。 Argonische-Argon2の実装

GitHubにはArgon2アルゴリズムの公式実装がありますが、 ‑march=native



を使用します。異なるプロセッサモデルを使用するため、 Illegal instruction



除きサービス‑march=native



します。この設定により、コンパイラはアセンブリが実行されるプロセッサモデルのコードを最適化します。 最も移植性の高いアセンブリ構成を作成すると、可能なパフォーマンスの15〜20％の間（AVX2の場合は最大65％）が失われます。 したがって、Argon2アルゴリズムの実装を作成しました。これにより、コードが実行されるCPUの機能を最大化できます。







実装では、ランタイムCPUディスパッチと呼ばれる手法を使用します。 その本質は、アルゴリズムコードでライブラリを初期化するときにcpuid



命令が実行され、現在のCPUでサポートされている高度な命令セットが決定され、対応する最適化を備えたコードブランチが選択されることです。 ライブラリには、SSE2、SSSE3、SSE4.1、AVX2命令セット用に最適化されたコードが含まれています。 パラメーターp=1,m=2048,t=1



Argon2dでのパフォーマンスの違いは、以下のグラフで確認できます。







Argon2はBlake2Bを使用しているため、上記の命令セット用に最適化されたボーナスとしてBlake2Bを取得しました。 内部的には、 SHA-1



およびHMAC-SHA-1



迅速かつ安全な代替品としてBlake2Bを使用することをお勧めします。 そのため、Argon2の公式実装との違いは次のとおりです。



1. C ++ 14およびビルドシステムとしてのcmake。

2.ランタイムCPUディスパッチ。

3. SSE2、SSSE3、SSE4.1、AVX2用に最適化されたBlake2B。

4. pthreadではなくOpenMP。OpenMPがない場合は、すべての計算が順番に実行されます。



また、このプロセスでは、AVX2命令セット用のArgon2のバージョンをゼロから作成し、PRを公​​式リポジトリに送信しました 。そこで、メンテナーが変更を受け入れました。



一般的に、大規模で負荷の高いサービスでのパスワードハッシュの問題は解決されます。 それを解決するには、次のものが必要です。



•ハッシュアルゴリズムの実装を高速化します。

•応答時間のKPIに基づいてアルゴリズムパラメーターを選択します。

•ハッシュスキームを変更して、オフライン攻撃から保護します。

謝辞

Solar Designer （別名Alexander Peslyak）に、大規模なインターネット企業でのパスワードハッシュの問題に関する膨大な数の考え、アイデア、実験、および有益な議論に感謝します。 また、パスワードハッシュへのさまざまなアプローチのさまざまなアイデア、共同ディスカッション、分析についてDmitry Khovratovichに感謝します。 Igor cerevra Klevanetsに深く感謝します 。Crev++は、C ++標準に変更を加える間、Argon2の実装のコードをレビューするのに時間をかけました。

便利なリンク

• GitHubのArgonischeプロジェクト

• 公式リポジトリArgon2

• PythiaおよびPartial-Oblivious PRFに関する記事

• インテル組み込み関数ガイド

• PASS：エンタープライズパスワード強化の強化と民主化