MAC：メッセージ認証コード

メッセージの完全性と認証のためのコードです。

• AliceとBobは、伝送中のメッセージ$x$が改ざんされていないことを確認したいと考えています。
• Bobは、メッセージ$x$と、共有した秘密鍵$k$の関数としてMAC(y)を作ります。
  • $y = \text{MAC}_k(x)$
  • Aliceへ$(x, y)$を送ります。
• Aliceは、共有した秘密鍵$k$と受信メッセージ$x$を使い、$y$を検証します。

• 暗号学的なチェックサムです。
  • MACは、メッセージの完全性を保証します。
• 対称的な技術です。
• 任意長の入力に対し、固定長の出力を返します。
• メッセージの完全性を提供します。
• メッセージ認証を提供します。
• 否認防止は提供しません（No nonrepudiation）。

• ハッシュ関数を使う方法。
• ブロック暗号を使う方法。

• 暗号学的ハッシュ関数を、基本的な構成要素として使います。
• IPセキュリティスイート、TLS（Transport Layer Security）、SET（Secure Electronic Transaction）などで使われます。
• 特定の仮定の下で、HMACの安全性を証明できます。

1. $K$の左側に0を加えて、$b$ビットの文字列$K^+$を作ります。
2. $S_i = K^+ \oplus \text{ipad}$を計算します。ipadは、0x36を$b/8$回繰り返した値です。
3. $S_i$へ$M$を連結します。
4. $H(S_i \| M)$を計算します。
5. $S_o = K^+ \oplus \text{opad}$を計算します。opadは、0x5Cを$b/8$回繰り返した値です。
6. $H(S_i \| M)$を、$S_o$へ連結します。
7. $H(S_o \| H(S_i \| M))$を計算し、出力します。

• 証明可能な安全性を提供でき、特定の仮定の下でHMACは安全です。
• 有効なMAC出力を作ることは、使用しているハッシュ関数に対する、次のいずれかの攻撃に相当します。
  • 攻撃者に知られていない、ランダムで秘密のIVを使い、圧縮関数の出力を計算すること。
  • ランダムかつ秘密のIVが設定されたハッシュ関数で、衝突を見つけること。
  $\Rightarrow$ 使用しているハッシュ関数の衝突を見つけることに関係します。

• ブロック暗号と暗号利用モードを組み合わせます。
• 実務では、AESとCBCが最もよく使われます。

• $\text{Enc}(K, P_i) =\begin{cases}\text{EncBlock}(K, IV \oplus P_1) & \text{첫 블록의 경우}\\\text{EncBlock}(K, C_{i-1} \oplus P_i) & \text{다른 블록의 경우}\end{cases}$
• $\text{Dec}(K, C_i) =\begin{cases}\text{DecBlock}(K, C_1) \oplus IV & \text{첫 블록의 경우} \\\text{DecBlock}(K, C_i) \oplus C_{i-1} & \text{다른 블록의 경우}\end{cases}$

• 秘密鍵$k$、初期値$IV$があり、メッセージ$x$を$n$個のブロック$x_1, x_2, \cdots, x_n$に分けたとします。
  • $y_1 = \text{Enc}_{Block}(k, IV \oplus x_1)$
  • $y_i = \text{Enc}_{Block}(k, y_{i-1} \oplus x_i)$
• $2\leq i \leq n$について計算し、$(x, y_n)$を送ります。

• $(x, y_n)$が与えられたら、次を確認します。
  • $y_n \stackrel{?}{=} \text{CBC-MAC}_k(x)$