MAC と HMAC の設計原理（メッセージ認証はなぜ難しいか）

メッセージ認証コードとは何を保証する道具か

メッセージ認証コード（MAC：Message Authentication Code）は、メッセージと秘密鍵から短いタグを計算し、「このメッセージは鍵を知る者が作り、改ざんされていない」ことを受信側が検証できるようにする仕組みです。送信側は tag = MAC(key, msg) を計算してメッセージに添え、受信側は同じ鍵で再計算し一致を確かめます。守るのは真正性・完全性であって機密性ではありません（暗号化との役割分担は ハッシュ化と暗号化の違い と 暗号の基礎 を参照）。

似て非なるものとの線引きが要点です。ハッシュは鍵を持たないので誰でも再計算でき、改ざん者がデータとハッシュを同時に差し替えれば検知できません。デジタル署名は公開鍵で誰でも検証できる「公開検証可能」な道具ですが、MAC は鍵を共有する当事者間でしか検証できない代わりに、署名より桁違いに高速です。MAC は対称鍵の世界の認証プリミティブだと位置づけられます。

偽造不可能性：MAC の安全性はどう定義されるか

MAC の安全性は直感ではなく形式的な攻撃モデルで定義されます。基準は **EUF-CMA（Existential Unforgeability under Chosen-Message Attack）**です。

ゲーム（攻撃者 A 対 検証者）:
  1. 鍵 key をランダムに選ぶ（A には秘密）
  2. A は好きなメッセージ m1, m2, ... を選び、
     その正しいタグ MAC(key, mi) を何度でも問い合わせられる（CMA）
  3. A は、一度も問い合わせていない新しい m* と、その偽造タグ t* を出力する
  4. MAC(key, m*) == t* なら A の勝ち（存在的偽造に成功）
勝率が無視できるほど小さい ⇔ その MAC は EUF-CMA 安全

ここが「メッセージ認証はなぜ難しいか」の核心です。攻撃者は選んだメッセージの正しいタグを好きなだけ集められる前提で、それでもなおたった一つの新しいメッセージのタグすら作れてはいけない。多数のサンプルを与えてもまったく外挿させない、という強い要求がメッセージ認証を難しくしています。なお「メッセージとタグの組」自体が漏れることは想定内で、漏れて困るのは鍵だけです。

素朴な鍵付きハッシュがなぜ壊れるか

「鍵とメッセージを連結してハッシュすればよい」という直感は、SHA-256 のような Merkle–Damgård 構造のハッシュでは破綻します。

危険な自作 MAC:
  tag = SHA256(key || msg)     # secret-prefix MAC

この構成は**長さ拡張攻撃（length extension attack）**で偽造されます。MD 構造のハッシュは内部状態（chaining 値）をそのまま出力するため、攻撃者は得られた tag を内部状態として復元し、鍵を知らないまま key || msg || padding || 追記 の正しいタグを計算できてしまいます（この機序は ハッシュ関数の内部構造 で詳説）。EUF-CMA の言葉でいえば、msg のタグ一つを観測しただけで新メッセージ msg || ... のタグを偽造できる、明確な敗北です。

では tag = SHA256(msg || key)（secret-suffix）にすれば長さ拡張は防げますが、今度はハッシュ自体に衝突 H(a) = H(b) が見つかると a || key と b || key のタグが一致し、衝突耐性の低下がそのまま MAC の偽造に直結します。鍵とハッシュを単純連結する自作 MAC は、置き方を変えてもどこかで穴が開く——これが HMAC という専用構成が必要になった理由です。

HMAC の構造：ipad と opad の二重ネスト

**HMAC（Hash-based MAC, RFC 2104）**は、任意の Merkle–Damgård ハッシュ H を二重にネストして安全な MAC を作る汎用構成です。

HMAC(K, m) = H( (K' XOR opad) || H( (K' XOR ipad) || m ) )

K'   = 鍵をブロック長に整える（長ければ H で縮め、短ければ後ろに 0 を詰める）
ipad = 0x36 をブロック長ぶん繰り返した定数（inner pad）
opad = 0x5c をブロック長ぶん繰り返した定数（outer pad）

動作は二段構えです。まず内側で K' XOR ipad を鍵としたハッシュでメッセージを処理し、固定長の中間ダイジェストを得ます。次に外側で K' XOR opad を頭に置き、その中間ダイジェストを再びハッシュします。

ipad と opad が異なる定数（0x36 と 0x5c）なのも理由があります。両者は多くのビットで食い違っており、K' XOR ipad と K' XOR opad は実質的に独立した二つの鍵Ki, Ko のように振る舞います。これにより内側と外側のハッシュが同じ鍵を共有することによる相互作用を避けられます。

HMAC の安全性証明の概略

HMAC が EUF-CMA 安全であることは、ハッシュ全体の理想性ではなく、より弱い前提に帰着して証明されています。骨子は二段階です。

前提: 圧縮関数 f が
  (1) 鍵付きで PRF として振る舞う、かつ
  (2) （弱い意味の）衝突耐性を持つ

主張: NMAC（HMAC の理論モデル）は PRF である
   ↓ PRF ⇒ EUF-CMA 安全
結論: HMAC は安全な MAC

理論モデルの NMAC は、内外で独立な二鍵 Ki, Ko を使う構成 f(Ko, f(Ki, m)) です。証明の流れは、(1) 内側 f(Ki, ·) が任意長を固定長に潰す擬似ランダムな関数として働き、(2) 外側 f(Ko, ·) がその固定長出力を擬似ランダムなタグに変換する、という二段で「全体が PRF」を示します。HMAC は NMAC の二鍵を「単一鍵を ipad/opad で派生」して近似したものなので、追加の仮定のもとで NMAC の安全性が HMAC に引き継がれます。

多項式ハッシュ系 MAC：設計思想の対立軸

HMAC が「汎用ハッシュを反復して安全性を稼ぐ」道具なら、Poly1305 や GHASH に代表される多項式ハッシュ系 MAC は「一回の代数計算で済ませて速度を稼ぐ」道具で、思想が真逆です。これらは情報理論的な **Universal Hashing（普遍ハッシュ）**を土台にします。

Poly1305 の骨格（記号化）:
  メッセージを 16 バイト断片 c1, c2, ..., cn に分割し係数とみなす
  tag = ( c1*r^n + c2*r^(n-1) + ... + cn*r ) mod (2^130 - 5)  +  s  (mod 2^128)
    r = 秘密の評価点、s = メッセージごとに変わる一回限りのマスク

メッセージを多項式の係数列、秘密鍵 r をその評価点とみなし、素数 2^130 - 5 を法として一発で評価します。安全性の根拠は EUF-CMA でも PRF でもなく、差分確率の上限です。二つの異なるメッセージが同じハッシュ値を与えるのは「ある多項式が評価点 r で 0 になる」場合に限られ、次数 n の多項式の根は高々 n 個なので、ランダムな r でそれに当たる確率は n / 2^130 程度と極小に抑えられます。

実装上の落とし穴：タグ比較は定数時間で

理論的に安全な MAC でも、検証側のタグ比較を素朴に書くと破られます。if (tag == expected) のような先頭から比較して不一致で早期 return する実装は、一致したバイト数で処理時間が変わり、攻撃者はタグを 1 バイトずつ計測で当てられます（サイドチャネル攻撃 のタイミング攻撃）。

まとめ

メッセージ認証が難しいのは、攻撃者が選んだメッセージのタグを好きなだけ集めても新しいメッセージのタグ一つ作れない、という EUF-CMA の強い要求を満たさねばならないからです。鍵とハッシュの単純連結は長さ拡張や衝突でこの要求を破り、だからこそ HMAC の ipad/opad 二重ネストが必要になります。HMAC は外側ハッシュで内部状態を隠して長さ拡張を封じ、安全性は圧縮関数の PRF 性に帰着して証明されます。一方 Poly1305 などの多項式系は普遍ハッシュと一回限りマスクで高速かつ証明可能な認証を実現しますが、その代償として nonce・マスクの一意性が生命線になります。汎用性と再利用耐性なら HMAC、速度と AEAD 統合なら多項式系——用途で道具を選ぶ判断は、暗号の基礎 の「目的で使い分ける」原則の延長線上にあります。