ハッシュ関数の内部構造（Merkle–Damgård と SHA-3 のスポンジ構造）

ハッシュ関数は「任意長→固定長」をどう実現するか

暗号学的ハッシュ関数は任意長の入力を固定長の出力へ写します。だが暗号プリミティブの中核は、たいてい固定長しか扱えません。SHA-256 の中身は 512 ビット入力を取る圧縮関数、SHA-3 は 1600 ビット状態への置換です。この「固定長の部品で任意長を処理する」橋渡しの設計が構造（construction）であり、SHA-2 系の Merkle–Damgård と SHA-3 のスポンジは、ここで思想が真っ向から分かれます。構造を理解すると、衝突耐性や長さ拡張攻撃といった性質が「なぜそうなるか」が見えてきます。前提となる一方向性や衝突耐性の定義は 暗号の基礎 を参照してください。

Merkle–Damgård 構造：圧縮関数の反復

Merkle–Damgård（MD）構造は、二入力を一出力にまとめる圧縮関数 f: {chaining値, メッセージブロック} → chaining値 を反復します。手順はこうです。

1. パディング: メッセージ末尾に 1 ビットの 1、0 を詰め、最後に
   「元のメッセージ長」を符号化して付与する（長さ詰め＝MDストレングス化）
2. 固定長ブロック M1, M2, ..., Mn に分割
3. H0 = IV（規格で固定された初期値）
4. for i in 1..n:  Hi = f(Hi-1, Mi)   ← 前段の出力を次段へ引き継ぐ
5. 出力 = Hn（最後の chaining 値そのもの）

要点は2つ。ひとつは末尾に必ずメッセージ長を埋め込むこと（Merkle–Damgård strengthening）。これにより、長さの異なるメッセージが偶然同じパディング後系列にならず、構造由来の衝突を防ぎます。もうひとつは、圧縮関数 f が衝突耐性を持てば、全体も衝突耐性を持つことが証明されている点です（Merkle–Damgård 定理）。設計者は固定長の f の安全性に集中すればよく、これが MD の強みでした。

SHA-256 の処理を分解する

SHA-256 は MD 構造の代表です。圧縮関数は 256 ビットの chaining 値（a から h の8ワード）と 512 ビットメッセージブロックを取り、64 ラウンドの混合を行います。

入力: 8ワードの状態(a..h) と 512ビットブロック
1. メッセージスケジュール: 512ビットを16ワード(W0..W15)に分け、
   W16..W63 を σ0/σ1（ローテートとシフトのXOR）で再帰生成
2. 64ラウンド: 各ラウンドで
     T1 = h + Σ1(e) + Ch(e,f,g) + Kt + Wt
     T2 = Σ0(a) + Maj(a,b,c)
   を計算し、a..h を1つずつローテートしながら更新
   （Ch=選択, Maj=多数決, Σ/σ=ビット回転と排他的論理和の混合）
3. 最後に入力状態 a..h を加算（Davies–Meyer 風の前後加算）

ラウンド関数はビット回転・シフト・加算・XOR・非線形関数 Ch/Majだけで構成され、入力1ビットの変化が出力全体へ伝播する雪崩効果を生みます。最後の「入力状態の加算」は重要で、f を一方向にする（圧縮関数からブロック暗号を作る Davies–Meyer 構成に対応）役割を担います。SHA-224 は SHA-256 と IV と出力長だけが違い、SHA-384/512 は 64 ビットワード・1024 ビットブロック・80 ラウンドへ拡張した同系統で、いずれも骨格は同じ MD＋類似ラウンドです。ファイル改ざん検知でこの出力（ダイジェスト）を使う発想は ハッシュ化と暗号化の違い で扱った通りです。

長さ拡張攻撃：MD構造の構造的弱点

MD構造には**長さ拡張攻撃（length extension attack）**という固有の弱点があります。出力が「最後の chaining 値そのもの」だからです。

攻撃者が hash(secret || message) の値と message の長さだけを知っているとします。すると secret を知らなくても、そのハッシュ値を内部状態として復元し、続きから計算を再開できます。結果、hash(secret || message || padding || 攻撃者の追記) の正しいハッシュを偽造できてしまう。

回避策は3つあります。(1) HMAC を使う（最も標準的）。(2) 出力を切り詰めた変種を使う――SHA-512/256 は内部 512 ビット状態の半分しか出力しないため、攻撃者は完全な内部状態を得られず長さ拡張が成立しません。(3) そもそも晒さない構造のハッシュ＝SHA-3 を選ぶ。SHA-256 の生の出力をそのまま secret || data 形式の認証に使わないこと、これが実務上の要点です。

スポンジ構造：吸収と搾出

SHA-3（Keccak）は MD と無関係なスポンジ構造（sponge construction）を採用します。中心にあるのは圧縮関数ではなく、固定幅の置換 f（Keccak-f[1600]、1600 ビットの可逆変換）です。内部状態 b ビットを レート部 r と容量部 c に分け（b = r + c）、入力はレート部にだけ触れます。

状態 S = r ビット || c ビット（初期は全 0、合計 1600 ビット）

吸収相 (absorbing):
  入力をパディングして r ビットのブロック P1..Pn に分割
  for each Pi:
    S[レート部] = S[レート部] XOR Pi   ← 入力はレート部にだけXOR
    S = f(S)                            ← 1600ビット全体を撹拌

搾出相 (squeezing):
  必要な出力長になるまで:
    出力に S のレート部 r ビットを取り出す
    （まだ足りなければ S = f(S) を回して続きを絞る）

スポンジ＝海綿の比喩通り、入力を吸い込み（吸収）、撹拌した状態から欲しい分だけ絞り出す（搾出）。搾出相が独立しているため、SHA-3 は同じ構造のまま任意長出力（SHAKE128/256 の XOF）も自然に表現できます。これは固定長出力に縛られる MD には真似のしにくい柔軟性です。

Keccak-f 自体は、5×5×64 ビットの3次元配列状態に対し θ（列パリティ拡散）ρ（ビット回転）π（レーン置換）χ（唯一の非線形ステップ）ι（ラウンド定数XOR）の5工程を24ラウンド適用します。AESのような S-box ルックアップを使わず論理演算中心なので、サイドチャネル耐性やハードウェア実装で有利という設計上の利点もあります。

構造の違いが生む攻撃耐性の差

両構造を性質ごとに対比します。

最大の差は長さ拡張攻撃です。SHA-3 は出力が容量部に守られた状態の一部にすぎず、攻撃者は完全な内部状態（1600 ビット）を復元できません。レート部 r は見えても、撹拌され続ける c が分からない限り f を正しく再開できないため、攻撃は原理的に不可能になります。一方 SHA-256 は内部状態そのものが出力なので、追加の構成（HMAC）でしか守れません。

ハッシュ関数を「ブラックボックスの一方向変換」で済ませず、f の反復か置換の吸収・搾出かまで分解できると、HMAC が必要な理由や SHA-512/256 という変種の存在意義が腑に落ちます。実際にパスワード保存で低速ハッシュを選ぶ判断（パスワードの安全な保存）も、こうした内部構造の理解が土台になります。