ハッシュ関数とSHA-256

問い

1. ファイルの1文字を変えるだけで、そのハッシュの約半分が変わるのはなぜでしょうか？
2. 可能な入力は無限にあるのに出力は有限個しかないとしたら、衝突する2つの入力を見つけることが依然として計算上不可能なのはなぜでしょうか？
3. 前身のSHA-1が破られたのに、SHA-256が安全だったのはなぜでしょうか？

探究

1. 暗号学的ハッシュ関数は、任意の長さのデータを固定長のダイジェストに変換します。決定的であり、同じ入力からは常に同一の出力が得られます。計算は高速ですが、逆算することは計算上不可能です。この一方向性が原像耐性（プリイメージ耐性）を定義しています。攻撃者がハッシュ値しか持っていなければ、元のメッセージを導き出すことはできません。この不可逆性が、分散システム全体で完全性チェックや本人証明の安全性を支えています。
2. SHA-256は、入力のサイズに関係なく256ビットの出力を生成します。入力が1バイトでも1ギガバイトのファイルでも、ダイジェストは常にちょうど32バイトです。長さが一定であるため、一貫した保存と比較が可能になります。この関数はデータを512ビットのブロック単位で処理し、64ラウンドの論理演算を行います。設計はMerkle–Damgård構造に従っており、圧縮関数をブロック間で連鎖させています。出力をかき混ぜているのは、この圧縮関数による攪拌処理です。
3. アバランシェ効果は重要な特性で、入力の1ビットを反転させると出力ハッシュの約半分のビットが変化します。この感度の高さにより、ごくわずかなデータの破損や改ざんでもまったく異なるダイジェストになります。そのため、ハッシュ関数はファイルの完全性の検証や改変の検出に最適です。どれほど微細な変更でも、期待されるハッシュと計算したハッシュは一致しなくなります。
4. 衝突耐性は最も厳しい要件です。誕生日限界（バースデイバウンド）により、同じハッシュを生成する2つの異なる入力を見つけるにはおよそ2^128回の演算が必要です。SHA-256では、この計算コストのため、現在のハードウェアによるブルートフォース攻撃は現実的ではありません。対照的に、SHA-1は2017年にGoogleとCWIの研究者によって実証された、SHAtteredとして知られる実用的な衝突攻撃の被害を受けました。この脆弱性により、セキュリティが重要な用途ではSHA-1からの移行を余儀なくされました。
5. ビットコインはSHA-256を2回適用しており、これはダブルハッシュと呼ばれます。ブロックヘッダーとトランザクションIDはSHA-256でハッシュ化され、その結果がもう一度SHA-256でハッシュ化されます。サトシはこの選択理由を説明していません。よくある説明は、SHA-256のようなMerkle–Damgård型ハッシュの既知の性質である長さ拡張攻撃への対策というものです。チェーン上のすべてのブロックハッシュとトランザクションIDは、この2回のハッシュ処理の出力です。
6. 任意のターミナルまたはオンラインツールを開き、文字列'MSTR Cat'のSHA-256ハッシュを計算してください。次に、1文字の大文字・小文字だけを変えた'MSTR cat'のハッシュを計算します。2つの64桁の16進数出力を比較してください。両者はまったく異なり、識別できるパターンは何も共有していません。この即座の食い違いは、アバランシェ効果が実際に働いている様子を示しています。わずか1ビットの変化でダイジェスト全体がかき混ぜられることから、この関数が入力に極めて敏感であることが確認できます。

重要な事実

演習 九・六・三・一

事実確認

日付、数字、主張は、下記に記載された公表資料と照合して確認しました。

• NIST, FIPS 180-4: Secure Hash Standard (2015)
• A. M. Antonopoulos & D. A. Harding, Mastering Bitcoin, 3rd ed. (2023)
• D. Stevens et al., 'The first collision for full SHA-1' (2017)