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

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

要点: 衝突検出を行うSHA-1は遅いと判明したため、自作することにしました。sha1dc は衝突検出機能を追加したSHA-1の書き直し版で、そのコードジェネレーターはソルバーを使用して衝突テストをSIMDレーンに適合させます。既存のクレートがプレーンSHA-1の28〜29%の速度で動作するのに対し、これは68〜81%の速度で動作し、Gitのパック検証を2倍速くすることができます。

GitはSHA-1をどのように使用し、なぜ遅く（より遅く）ならなければならないのか

Enroute の開発の一環として、現在Gitサーバーバックエンドのパフォーマンス最適化に深く取り組んでいます。Gitサーバーでは、Gitクライアントからパックファイルを受け入れることがよくあります。これらのパックファイルは信頼できない入力であり、検証する必要があり、これには含まれるGitオブジェクトのSHA-1ハッシュのチェックが含まれます。

私はgitoxide を使用しており、パック検証は非常に遅くなる可能性があります。私のM4マシンで、ベアなgit/git クローン（421,292オブジェクト、圧縮時305 MiB、展開時7.7 GiB）のパックを検証するのに12.5秒かかり、そのうち84% がSHA-1に費やされています。

内部的には、衝突検出付きのSHA-1ライブラリであるsha1-checkedというクレートを使用しており、このマシンでは約900 MiB/sで動作します。対照的に、M4のSHA-1ハードウェア命令を使用したプレーンなsha1は、約3 GB/sで動作します。

［画像: Apple M4での衝突検出のコスト。sha1クレートは2979 MiB/sでハッシュし、sha1-checkedは856 MiB/sで、プレーンSHA-1の29%です。git/gitのシングルスレッドパック検証は12.55秒かかり、その84%が検出付きSHA-1で、このスループット比で分割すると、約3.0秒がハッシュ自体、7.5秒（実行時間の60%）が衝突検出、それに加えて1.4秒のzlibと0.6秒のその他です。］

待ってください、衝突検出？ はい: 未知の入力に対して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の速度でしか進みませんが、フィルター自体が、衝突検出付き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つの単語間の距離が最も小さい）でタイをブレークします。

［画像: ジェネレーターのトイ例。6ビットAからFのディスターバンスベクトル2つ：最初のものはA=B、B=C、E≠Fで到着し、2番目のものはA=C、D≠Eで到着します。A=BかつB=CはA=Cを意味するため、最初のベクトルは代わりにA=Cをチェックし、2番目のベクトルがすでにチェックしているペアであるため、コードは5回のチェックではなく4回のチェックで済み、そのうちの1つが両方のベクトルをクリアします。］

ジェネレーターが機能する理由は次のとおりです。条件とは、展開されたメッセージの2つの特定のビットが等しくなければならない（または異ならなければならない）ことを示します。そのような関係は連鎖します。ビットAはビットBと等しくなければならず、ビットBはビットCと等しくなければならない場合、AはビットCと等しくなければなりません。したがって、各ディスターバンスベクトルには、チェックするペアのリストが1つあるのではなく、同等のリストのファミリがあり、ジェネレーターはそれらの中から選択できます。

論文のジェネレーターは、多くのベクトルが共通して持つペアを選択するため、1つのステートメントが複数のベクトルに同時に役立ちます。これはステートメントを最小化する選択であり、スカラー計算に最適です。

しかし、SIMDユニットは、良い選択がどのように見えるかを変えることができるでしょうか？

いくつかのSSE2またはNEON命令は、4つのビットペアを一度に比較できますが、それらの4つのペアが同時に処理できる場合、つまり4つのペアが単語間の距離、それらのビット位置などが同じである場合に限ります。

最初からやり直す

その時点で、計画が形成され始めました。特定のアーキテクチャのために実装を手作業で調整しようとするのではなく、これらの理論的基盤を取り入れてSIMDの世界に導入したいと考えました。

そして、sha1dcが誕生しました。これは、Rustで衝突検出を行うSHA-1のボトムアップ再構築です。ハッシュ自体にはx86_64およびarm64のSHA-1命令を使用し、衝突チェックのneon、sse2、avx2形式を生成します。

基盤となるのは、異なるベクトルユニットをターゲットにして、それらの特定の特性に合わせたコードを決定論的に生成できるコードジェネレーターです。

仕組み

避けられないビット条件をベクトル化する際、各ベクトルグループの実行コストは同じですが、有効性は異なります。最初のいくつかのグループは多くのメリットをもたらします。なぜなら、各グループがディスターバンスベクトルの多くのブロックを排除するからです。その後、リターンは2つの理由で減少します。ほとんどのディスターバンスベクトルはほとんどのブロックですでに排除されているため、別のグループはほとんど何も変更しません。そして第二に、グループに4つ適合する条件が尽き始めます。残りはほとんどが4つのレーンのうち1つを埋めるだけになります。

そのため、sha1dcはチェックを2つの部分に分けて生成します。その間の分割は損益分岐点を表します。

• プレフィックスは、すべてのブロックで無条件に実行されます。その単位はグループです。これは、連続する単語の1つの形状の最大4つまたは8つの条件をカバーする2つのベクトルロードです。
• テールは、スカラー条件の連鎖であり、完全にスカラーな実装と非常によく似ています。これは、ブロックが以前にプレフィックスによって無効化されなかった場合にのみ実行されます。

［画像: チェックの形状、条件ごとに1つの正方形。Cから派生したチェックは、すべてのブロックで47個のスカラーステートメントを実行し、他の109個の条件をマスクテストの後ろに保持します。sha1dcが生成するNEON形式は、すべてのブロックで4レーン幅で66個の条件をカバーする17個のベクトルグループを実行し、次にマスクゼロリターン、そしてブロックの28%しか到達しない93個のガード付き条件のテールを実行します。］

これを達成するために、sha1dcはソルバーを使用します。ソルバーの仕事は、どの条件をベクトルプレフィックスに入れ、どのグループに入れるかを決定することです。これにより、プレフィックスは許可されたグループ数に対してできるだけ多くのブロックを排除します。排除されなかったものはスカラーテールに渡されます。問題は、グループがその完全な4レーンのコストを支払うのは、同じ形状の4つの条件が連続する単語で整列した場合のみであり、最もよく整列する条件が必ずしも最も多くのブロックを排除する条件ではないということです。

ハッシュされているランダムなブロックを考えてみてください。プレフィックス内の各独立した条件はコインフリップです。2つのビットは一致するか、一致しないかのどちらかです。したがって、r個のそのような条件を持つベクトルは確率 2^(−r) で生存し、32個のベクトル全体でそれを合計すると、生存者の期待値が得られます。これがソルバーが統計的にテールがどれくらいの頻度で実行される必要があるかを知る方法です。

この数値はグループごとに改善し続けますが、スループットはそうではありません。M4で測定すると、テールエントリー率が最低になるずっと前にピークに達します。このトレードオフがエンコードされる方法は、各命令セットの予算を通じて行われます。ソルバーは、スループットを最大化するように設定されたプレフィックスグループ数の制限を受け取ります。

［画像: Apple M4でのプレフィックス予算に対するテールエントリー率と測定スループット。NEON: 予算が5グループから35グループに増加するにつれて、テールに到達するブロックの割合は98%から6%に低下し、スループットは14〜21グループの間でプラトーに達し、17グループ（出荷された予算）で2364 MiB/sでピークに達し、その後35グループで2144に低下します。スカラー: 20〜80ステートメントで、テールシェアは96%から14%に低下します。スループットは、45〜60ステートメントで約920 MiB/sでほぼ横ばいになり、それ以外は低くなり、45が出荷されます。］

テスト方法

テストに関しては、固定テストバッテリーでは見つけられない問題を特定するために、ファジングとプロパティテストの大ファンです。したがって、当然のことながら、sha1dcには多くのプロパティテストがあります。

しかし、純粋にランダムな入力には、このケースでは大きな盲点があります。プレフィックスチェックのいずれもトリガーされなかった場合にのみテールに進みます。そして、プレフィックスチェックの効果を特に最適化していることを考えると、ランダムな入力でトリガーするのは非常に困難になります。

幸いなことに、これも解決できます。SHA-1は入力ブロックを線形に展開して内部バッファをシードするため、そのビットの2つに対する条件はブロックのビットに対する方程式です。1つのベクトルをアクティブに保つことは、最大15個の方程式を満たすことを意味し、512ビットを自由に操作できます。一度計算すると、制約のない数百ビットをランダムな値で埋めることができ、満足のいくブロックが何度でも作成されます。

sha1dcのテストは、1つのシードから各ベクトルに対して64個のこのような証人を生成し、合計2,048個を生成するため、最もまれなベクトルに隠されたチェックさえも実行されます。

最終結果

sha1dcの最初のバージョンがcrates.ioで公開されました。これにより、命令セットに応じて、プレーンSHA-1とのギャップが19〜32%に縮小されます。

マイクロベンチマーク

16 KiBの疑似ランダム入力を2つのベースラインで測定します。

1. 検出は行いませんが、ハードウェアアクセラレーションを備えたsha1クレート。
2. 検出を行いますが、ハードウェアアクセラレーションがないsha1-checkedクレート。

MiB/sでのスループット、およびsha1行に対する割合：

［画像: 3台のマシンでのsha1、sha1dc、sha1-checked、およびハードウェアアクセラレーションPR付きsha1-checkedのスループット。Apple M4: 2979、2400 (81%)、856 (29%)、1712 MiB/s (57%)。Xeon Platinum 8488C: 1887、1285 (68%)、523 (28%)、877 (46%)。Graviton4: 1616、1286 (80%)、462 (29%)、980 (61%)。］

sha1とsha1dcの両方がマシンのSHA-1命令を使用していることを考えると、それらの間のギャップは、他のすべてが等しいと仮定した場合、sha1dcでの衝突検出のコストです。マシンに応じて19%から32%です。

sha1-checkedとのギャップは大きく、2.5倍から2.8倍であり、そのほとんどはハードウェアアクセラレーションによるものです。sha1-checkedに対する私のPRを追加すると、より明確な状況が得られます。ハードウェアSHA-1命令はそれをプレーンSHA-1の46%から61%にし、ベクトルチェックはさらに1.3倍から1.5倍になります。

実世界のパフォーマンス

これらすべては、gitをより速くしたいという思いから始まりました。どうなっているでしょうか？ 通常gix-hash（sha1-checkedをラップする）からSHA-1を取得しているgitoxideを測定しています。テストのために、sha1dcをスワップインしました。すべてのテストは私のM4マシンで実行され、5回の実行のうち最速のものを選びました。

この記事の冒頭の数値は、期待どおりに動いています。検出付きSHA-1は、シングルスレッドのpack verifyの84%から73%になり、ハッシュがその周りで縮小するにつれて、zlibインフレーションは11%から18%に増加します。

次は何ですか

すでにEnrouteで使用していますが、これをgitoxide自体にアップストリームして、RustベースのGitエコシステム全体が恩恵を受けられるようにしたいと考えています。

とはいえ、pack verifyプロファイルで最も大きな要素は依然としてSHA-1なので、この旅はまだ終わりではありません。続報にご期待ください！

編集 (2026-09-21): sha1dcはPR #3008によりgitoxideにマージされました。