開発者ツール · SHA ハッシュ計算ツール
雪崩効果: 変更された文字が SHA ハッシュを書き換える理由
· 仕組み
しゃ-256 暗号化 セキュリティ 検証
1 文字を変更すると、出力ビットの約半分が反転します。この投稿では、なだれのプロパティ、それが改ざん検出に不可欠な理由、および SHA-2 のラウンドがどのようにそれを実現するかについて説明します。
ハッシュが少し変わることを期待する - ほとんどの人がもたらす直感と、デザインが意図的にそれを破る理由
ほとんどの人は、同様の入力が同様の出力を生成することを期待しています。ファイル内の 1 文字を変更すると、ダイジェストがわずかに変化するはずです。代わりに、暗号化ハッシュはその逆を行うように設計されています。つまり、入力の 1 ビットの変更により、出力ビットのおよそ半分が予期せず反転されます。この特性は雪崩効果と呼ばれ、意図的に行われます。この設計は、改ざん検出という特定の目的を果たします。
ハッシュの世界では「ほぼ一致」という概念が存在しないのは、雪崩効果のためです。ハッシュは完全に一致するか、一致しません。 「十分に近い」ということはありません。このプロパティにより、ハッシュは整合性チェックやコンテンツ アドレス指定に役立ちますが、弱いハッシュ アルゴリズムはセキュリティ目的で使用できなくなります。
アバランシェは広範囲の出力拡散を意味します。この記事は出典のない正確な確率を主張するものではありません
正式には、アバランシェ効果は、1 ビットだけ異なる 2 つの入力の場合、出力ダイジェストのビットの約 50% が異なることを意味します。 SHA-256 (出力の 256 bits) の場合、1 つの入力ビットを変更すると、おおよそ 128 出力ビットが反転するはずです。効果は正確ではありません。それは統計的な性質です。しかし、これは強力です。実際には、入力のあらゆるビットが出力のあらゆるビットと完全に混合されます。
なぜ約半分なのでしょうか？なぜなら、真にランダムな出力は、(鳩の巣原理と基本統計によると) 平均してちょうど半分のビットが別のランダムな出力と異なるからです。優れたハッシュ関数はランダム性に近似します。認識できるパターンがないように見える出力が生成されます。平均して半分のビットが反転するのは、ランダム性の特徴です。ハッシュがビットの 10% のみを反転した場合、攻撃者はパターンを見つけて悪用する可能性があります。
改ざん検出が必要な理由 — 文書への小さな編集によって、一目見ただけで受け入れられるようなほぼ同一のハッシュが生成されてはなりません
改ざん検出は雪崩に依存します。ファイルをダウンロードしてその SHA-256 を計算すると、予期されるダイジェストは ba7816... (例として) になります。攻撃者は 1 バイトを変更することでファイルを変更します。新しいダイジェストは、ba7816... から 3d4e92... のようなものに変わります (まったく異なります)。予想されるダイジェストに対してファイルを検証すると、不一致は即座に完全に発生します。誤解の余地はありません。ファイルは改ざんされています。
アバランシェがなければ、攻撃者はバイトを変更することができ、ダイジェストは ba7817... (16 進数が 1 桁異なる) までわずかにシフトする可能性があります。何気なく比較してしまうと、違いを見落としてしまう可能性があります。攻撃者は、ファイルが本物であると主張して、ba78 で始まるダイジェストを生成する入力を検索することもできます。 Avalanche では、これが法外に高価になります。ダイジェストが同じ 4 つの 16 進数字で始まる 2 つの入力を見つけるだけでも、設計で許容される以上の作業が必要になります。
ラウンドがどのように変化するか — 状態全体に 1 ビットの影響を与える回転、加算、および非線形関数
SHA-256 のラウンド (および SHA-512 のラウンド) は、変更を分散するように設計されています。各ラウンドでは、非線形関数 (選択、多数決) とローテーションを使用してデータを混合します。入力の単一ビットの変更はメッセージ スケジュールに入り、ラウンドを通じて伝播します。回転するとビット位置がシフトします。非線形関数はビットの影響を隠します。選択操作で制御ビットを変更すると、選択されているデータに応じて出力ビットのいずれかが反転する可能性があります。
初期ハッシュ定数、メッセージ スケジュール定数、ローテーション量、およびラウンド数はすべて、アバランシェ効果を最大化するように選択されました。これらの数値は任意ではありません。これらは SHA-2 仕様に基づいており、広範囲に暗号化されています。定数またはラウンド数を変更すると、別のアルゴリズム (おそらく弱いアルゴリズム) が生成されます。
実用的な例 — 1 文字が異なる 2 つの入力をハッシュし、ダイジェストをビットごとに比較する
アバランチのテストは簡単です。入力 abc をハッシュし、ダイジェストをメモします。次に、abc の後にスペースをハッシュするか、1 文字を別の文字に置き換えます (abd)。 16 進出力を比較します。 SHA-256 の場合、64 の 16 進数の約半分が異なります。数えてみてください。 ToolAcre 投稿のテスト ベクトル: abc は ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad を生成します。空の文字列の場合は、e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 が生成されます。これらのダイジェストには共通の 16 進数がありません。
ToolAcre 計算機で任意の入力を使用してこれを試してください。文章をハッシュ化します。次に、文字を 1 つ変更して再度ハッシュします。異なる 16 進数を数えます。およそ半分 (ほとんどの場合、64 のうち 32) が異なることがわかります。これが雪崩効果の実際の現象です。これはアルゴリズム設計の特性であり、偶然ではありません。
Avalanche は類似性検索を提供しません。また、Avalanche 自体は衝突耐性を定量化しません。
Avalanche は類似性検索や近似一致を作成しません。ダイジェスト ba7816... があり、同様のダイジェストを見つけたい場合、近道はありません。候補入力を推測または総当たりして、それぞれをハッシュし、完全に一致するかどうかを確認する必要があります。雪崩効果により、すべての推測が同様の出力または完全に異なる出力を生成する可能性が等しくなります。一部のハッシュ アルゴリズム (局所性依存ハッシュと呼ばれる) は、類似性を維持するように設計されています。これらは、ほぼ重複の検出とクラスタリングに役立ちますが、暗号化ハッシュではありません。
Avalanche は、確定した衝突探索に対しても保護しません。暗号解析者は、同じダイジェストを生成する 2 つの異なる入力を探すことができますが、検索スペースは膨大です。決定的な衝突探索は、視覚的な拡散とは別の問題です。この記事では、誕生日に限定された数字やハードウェアのタイムラインを引用していません。なぜなら、ここではそれを導き出していないからです。擁護できる境界線は、雪崩だけでは衝突耐性を証明も定量化もできないということです。
要点: ニアミスはありません — ToolAcre SHA ハッシュ計算ツールで 1 文字の実験を試し、ダイジェスト全体の変化を観察してください
ToolAcre SHA ハッシュ計算ツールは、ブラウザーの Web Crypto 実装を通じて SHA アルゴリズムを実行します。ご自身で雪崩を検証するために使用できます。アルゴリズムのあらゆる精度が出力に反映され、Web 暗号化の実装はブラウザー ベンダーによって監査および維持されます。実際の入力に対して実際のアルゴリズムが実行されているのがわかります。 1 つの文字を変更するとダイジェスト全体が書き換えられるという直感に反する特性は欠陥ではありません。これはハッシュを機能させるための機能です。
整合性チェックにハッシュを使用する場合、雪崩に依存することになります。これをコンテンツのアドレス指定 (コンテナー イメージのダイジェストなど) に使用する場合は、小さな変更によって大きく異なるダイジェストが生成されるという特性に依存します。これをデジタル署名 (メッセージのハッシュに基づいて署名が計算される場合) で使用すると、雪崩効果により、メッセージの改ざんによって検出可能な変更が生成されることが保証されます。このプロパティはハッシュベースのセキュリティの基盤です。