SHA-1衝突検出を高速化する

SHA-1衝突検出を高速化する 2026年9月20日 要約: 衝突検出付きSHA-1が遅いことに気づき、自作することにしました。sha1dcは衝突検出を組み込んだSHA-1の書き直しであり、そのコードジェネレーターはソルバーを使用して衝突テストをSIMDレーンに適合させます。既存のクレートが28-29%の速度であるのに対し、これはプレーンSHA-1の68-81%の速度で動作し、git packの検証を2倍速くすることができます。 GitはSHA-1をどのように使用し、なぜ遅く（より遅く）ならなければならないのか Enrouteの開発の一環として、現在Gitサーバーバックエンドのパフォーマンス最適化に深く取り組んでいます。Gitサーバーで頻繁に行うことの一つに、Gitクライアントからパックファイルを受け入れることがあります。これらのパックファイルは信頼できない入力であり、検証する必要があり、これには含まれるGitオブジェクトのSHA-1ハッシュのチェックが含まれます。私はgitoxideを使用しており、その結果、パック検証は非常に遅くなる可能性があります。ベアGit/Gitクローンのパック（421,292オブジェクト、圧縮時305 MiB、展開時7.7 GiB）を私のM4で検証するには12.5秒かかり、そのうち84%がSHA-1に費やされています。下では、衝突検出付きSHA-1ライブラリであるsha1-checkedを使用しており、そのマシンでは約900 MiB/sで動作しています。対照的に、M4のSHA-1ハードウェア命令を持つプレーンsha1は、約3 GB/sで動作します。待て、衝突検出？はい: untrusted inputにとってSHA-1が困難なのは、選択的プレフィックス衝突が実用的であるため、暗号学的に壊れていることが知られていることです。理想的には、GitオブジェクトにはすべてSHA-256を使用するべきですが、移行...幸いなことに、このセキュリティ問題は、SHA-1の状態空間内でこれらの製造された衝突を検出することによって緩和できます。Gitが行っていることです。このアプローチを使用すると、Gitサーバーが衝突を検出した場合、クライアントからのこれらのオブジェクトの受け入れを拒否します。幸いなことに、これは明らかに非常に遅いです！そして、私は物事をより速くする方法を見つけ、衝突検出付きSHA-1のパフォーマンスを改善するために着手しました。 低くぶら下がっている果実 まず、sha1-checkedを詳しく調べ、すぐにできることを見つけました。それは、検出パスにハードウェアアクセラレーションがなかったことです。最新のarm64およびx86_64 CPUにはSHA-1命令があり、当初はそれらを使用しようと期待していました。しかし、この場合のハードウェア命令の落とし穴は、衝突検出が内部SHA-1メッセージスケジュールとハッシュ状態から実行されることであり、ハードウェア命令はそれにアクセスするのが難しいということです。私が変更したのは、スケジュールが展開されるときにバッファにスピルし、ハッピーパスをハードウェアで実行し、疑わしく見えるまれなブロックについてはスカラー再計算にフォールバックすることです。これにより、両方のアーキテクチャでスループットが約2倍になりました。Apple Siliconで928 → 1996 MB/s、sha_ni付きAMD EPYCで約300 → 約640 MB/sです。当時、これをsha1-checkedにプルリクエストとしてまとめましたが、レビュー前に0.11リリースを待っています。しかし、その後、さらにどれだけ改善できるか知りたくなりました。 定数の壁 簡単な修正方法により、次のボトルネックがすぐに明らかになりました。現時点でのコードから推測できた限り（理論については後述）、衝突検出はブロックごとに2つのことを行う必要があります。まず、安価なフィルターを実行します。展開されたメッセージの個々のビットに対する約150のテストで、それぞれが既知の攻撃パターンの一部を排除します。フィルターは、パターンごとに1ビットを持つマスクを保持し、テストが失敗するとビットをクリアします。次に、マスクがまだゼロでない場合のみ、問題を最終的に解決するブロックの高価な再計算が行われます。通常のデータでは、ブロックの約95%が空のマスクでフィルターを通過するため、再計算はほとんど実行されません。フィルターがない場合、ハッシュは約40 MiB/sでクロールし、フィルター自体が衝突検出付きSHA-1がプレーンSHA-1を超えて費やす時間です。しかし、問題がありました。sha1-checkedのこのコードは次のようになります。これは、元のCコードのほぼ直接の翻訳のようで、さらにその元のCコードは、それの背後にある研究論文のデータファイルからツールによって生成されたものです。 mask &= (((w[44] ^ w[45]) >> 29) & 1).wrapping_sub(1) | !(DV_I_48_0_BIT | DV_I_51_0_BIT | DV_I_52_0_BIT | DV_II_45_0_BIT | DV_II_46_0_BIT | DV_II_50_0_BIT | DV_II_51_0_BIT); mask &= ((w[47] ^ (w[50] >> 25)) & (1 << 4)).wrapping_sub((1) << 4) | !(DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT | DV_II_51_0_BIT | DV_II_56_0_BIT); これは、540行の16進テーブルの後に、約475行続きます。テストカバレッジに基づけば確かに正しいですが、少なくとも私にとっては完全に不透明です。数字の出所を理解せずに、それをより速くする方法をまったく見ることができませんでしたし、コードにはそれを助けるものはありませんでした。 論文を読む そこで、私はソースに戻りました。StevensとShumowによる高速化検出に関する論文は、フィルターが何をテストしているかを説明しています。論文自体は少し退屈かもしれませんが、スライドやビデオプレゼンテーションもあります。SHA-1衝突攻撃は、ディスターバンスベクターと呼ばれるメッセージ差のパターンから構築されており、論文は攻撃するのに最も安価な32個を選択します（32個なのはマスクが32ビット整数だからです）。検出器が試みているのは、あるブロックがそれらの32個のベクターのいずれかに沿った攻撃の一部である可能性があるかどうかを判断することです。各ベクターについて、論文は7から15のいわゆる避けられないビット条件を導き出します。これらは、攻撃が進行中である場合に保持されなければならない、展開されたメッセージのビットペア間の関係です。それぞれをチェックするのは安価であり、失敗した場合、そのベクターは除外できます。これらの条件を使用して、論文のツールリポジトリにある小さなプログラムがそれらをチェックに変換します。それは、ベクターの条件のすべての線形結合を列挙し、各ステップで、まだカバーされていない最も多くのベクターをカバーする関係を貪欲に選択し、テストの安価さでタイを破ります。次に、異なるビット位置、次に2つの単語間の最小距離です。ジェネレーターが機能する理由は次のとおりです。条件は、展開されたメッセージの2つの特定のビットが等しい（または異なる）必要があることを示します。そのような関係は連鎖します。ビットAがビットBと等しくなければならず、ビットBがビットCと等しくなければならない場合、AはCと等しくなければなりません。したがって、各ディスターバンスベクターには、チェックするペアのリストが1つだけでなく、同等のリストのファミリー全体があり、ジェネレーターはそれらの中から選択できます。論文のジェネレーターは、多くのベクターが共通して持つペアを選択するため、1つのステートメントがそれらのいくつかに同時に役立ちます。これはステートメントを最小化する選択であり、スカラー計算に最適です。しかし、SIMDユニットは、良い選択がどのように見えるかを変えることができるでしょうか？いくつかのSSE2またはNEON命令は、一度に4ペアのビットを比較できますが、4ペアが同時に処理できる場合に限ります。つまり、2つの単語間の距離、それらのビット位置などが同じである場合です。 最初からやり直す その時点で、計画が形成され始めました。特定のアーキテクチャのために手作業で実装を調整するのではなく、これらの理論的基盤をSIMDの世界に導入したいと考えました。そして、sha1dcが誕生しました。これはRustで衝突検出を組み込んだSHA-1のボトムアップ再構築です。ハッシュ自体にはx86_64およびarm64のSHA-1命令を使用し、衝突チェックのneon、sse2、およびavx2形式を生成します。下では、異なるベクトルユニットをターゲットにして、それらの特定の特性に合わせたコードを決定論的に生成できるコードジェネレーターを使用しています。 仕組み 避けられないビット条件をベクトル化すると、各ベクトルグループの実行コストは同じですが、有効性は異なります。最初の数グループは多くの効果をもたらします。なぜなら、各グループは一部のディスターバンスベクターに対して多くのブロックを排除するからです。その後、リターンは2つの理由で縮小します。ほとんどのディスターバンスベクターはほとんどのブロックですでに排除されているため、別のグループはほとんど何も変更しません。そして第二に、グループに4つフィットする条件が始まる t