ハッシュ関数における衝突
Collisions in Hash Functions (collisions.zksecurity.xyz)
要約
この記事は、ハッシュ関数の衝突(異なる入力が同じハッシュ値を持つこと)に関する研究ツール「atlas」を紹介しています。ここでは、公開されたハッシュ関数の衝突ペアを収集・検証しており、MD4、MD5、SHA-0、SHA-1などの古い関数や、SHA-256、SHA-512などの新しい関数に対する弱化されたバージョンでの衝突がリストアップされています。このツールはzkSecurityによって開発され、研究目的で提供されています。
全文翻訳
ハッシュ関数における衝突
ここでの衝突の定義
完全なブレークとは、完全なハッシュにおける衝突を意味します:すべてのラウンド、標準の開始状態、通常のパディング、および完全な出力。これは衝突耐性の崩壊を示しており、 preimage 攻撃を主張するものではありません。完全な高さのバーだけでは不十分です。80ステップのSHA-1選択IVの例は、依然として圧縮関数衝突にすぎません。
掲載されるためには、ペアは以下を満たす必要があります
- 完全な形で公開されていること。衝突が存在すると述べるか、そのコストを推定する論文はカウントされません。両方の入力が必要です。
- どの関数を壊したかを正確に述べること:ラウンド数、開始状態、パディング、出力長。
- 我々自身のコードで生き残ること。両方の入力をハッシュし、比較します。入力が同一であることが判明した場合、またはダイジェストがわずかにずれている場合、そのペアは除外されます。
これは何を意味しないか
- ここにあるSHA-256、SHA-512、SHA-3、RIPEMD-128、RIPEMD-160、SM3のペアは、弱化されたバージョンを使用しています。完全な衝突ブレークは、MD4、MD5、3または4パスのHAVAL、オリジナルのRIPEMD、SHA-0、SHA-1をカバーしています。
- Keccak Crunchyのエントリは、160ビットの容量を持つコンテストパズルです。これらはSHA3-256でもEthereumのKeccak-256でもありません。SHA-3およびSHAKEのエントリは、24ラウンド中3〜5ラウンドで停止します。
- 手作業で選ばれた開始状態を必要とするペアは、ハッシュ衝突ではありません。なぜなら、実際のハッシュでは選択できないからです。これは、すべての80ステップをカバーするSHA-1ペアにも当てはまります。
- 123ペアは123回の攻撃ではありません。多くは、複数のラウンド数での1回の攻撃、またはプレフィックスにカットダウンされた1回の衝突です。
私たちの言葉を鵜呑みにしないでください
$ python3 -m atlas list
$ python3 -m atlas verify --fetch
$ python3 -m unittest discover -s tests -v
Python 3.10とそれ以外は必要ありません。これらをリポジトリのルートから実行してください。
--fetchは2つのPDF、オリジナルのSHA-1衝突(約825 KiB)をダウンロードし、それらを使用する前にSHA-256をチェックします。それ以外はすべてリポジトリに16進数形式で含まれており、オフラインで実行できます。フラグをオフにすると、欠落しているファイルで実行が失敗します。決して静かにスキップすることはありません。
仕様からハッシュ関数を自分で記述し、公開されているテストベクトルに対してそれぞれテストしました。31ステップではなく64ステップでSHA-256を実行する他の方法はありません。完全なMD5とSHA-1はPythonのhashlibを使用します。攻撃が付属していたコードは決して実行しません。
これはzkSecurityの研究ツールであり、サービスではありません。ここにリストされていない衝突が存在しないという意味ではありません。