メッセージ認証符号 📖 Wikipedia

メッセージ認証コード（メッセージにんしょうコード、英: Message Authentication Code、MAC）は、メッセージを認証するための短い情報である。MACアルゴリズムは、入力として共通鍵と認証すべき任意長のメッセージを受け取り、MAC（「タグ」とも呼ばれる）を出力する。MACを付加することで、（共通鍵をもつ）検証者がメッセージ内容の変化を検出できるようになり、メッセージの完全性と認証が保証される。このため、メッセージ認証完全性コード（Message Authentication and Integrity Code、MAIC）とも呼ばれる。

MAC関数は暗号学的ハッシュ関数に似ているが、いくつかの必要条件の違いがある。MAC関数は選択平文攻撃における存在的偽造に対して耐性がなければならない。つまり、共通鍵を持ちMAC関数を計算できる神託機械にアクセスできる攻撃者が、任意に選んだメッセージに対応するMACを取得できたとしても、他の（神託機械に問い合わせていない）メッセージに対するMACを神託機械に対して問い合わせずに計算で求めることが計算量的に困難でなければならない。

MACはデジタル署名とは異なり、MAC値の生成と検証には同じ鍵が使われるので（共通鍵暗号）、送信者と受信者は通信を行う前に鍵を共有しておく必要がある。また共通鍵暗号であるために、認証されたメッセージは送信者本人が作成した物であり偽造ではないという確証、つまり否認不可性をもたない。なぜなら、受信者も含め共通鍵を知っている者であれば捏造したメッセージについてもMAC値を生成することができるからである。

公開鍵暗号を用いたデジタル署名では、メッセージの検証を公開鍵だけで行うことができるので、鍵の所有者はデジタル署名を作成できる秘密鍵を秘匿できる。したがって、デジタル署名が付与された文書はその所有者が署名したものと確定でき、否認不可な文書を作成することができる。

メッセージ認証符号（MAC）の代わりにメッセージ完全性コード（Message Integrity Code, MIC）という用語が、特に通信の分野でMACアドレスとの区別のために用いられることがある^[1]。しかし、MICは、メッセージを一意に識別するためのメッセージダイジェストの意味で用いられる場合もある^[2]。このため RFC 4949 では、MICという用語の代わりに、チェックサム、エラー検出符号、ハッシュ、鍵付きハッシュ、メッセージ認証符号、protected checksumを使うことが推奨されている。

MACアルゴリズムは他の暗号プリミティブから構築でき、ハッシュ関数を使う方式（HMAC）、ブロック暗号アルゴリズムを使う方式（OMAC/CMAC、CBC-MAC、PMAC）などがある。また、Poly1305などの高速なMACアルゴリズムはuniversal hashing^[3]をベースとしている。

鍵付きハッシュ関数の一種であるuniversal hashing、特にpairwise independentという性質を持つハッシュ関数は、鍵を一回ごとに使い捨てにするならば、安全なメッセージ認証符号として使うことができる。これは、暗号化におけるワンタイムパッドのMAC版と考えることができる^[4]。

Pairwise independentという性質は、鍵 ${\displaystyle k}$ を知らないならば、ある ${\displaystyle m}$ のハッシュ値 ${\displaystyle hash_{k}(m)}$ が分かったとしても、別のメッセージ ${\displaystyle m'(\neq m)}$ のハッシュ値 ${\displaystyle hash_{k}(m')}$ を推測できないという性質である。このような性質を持つハッシュ関数は、次のように簡単に作れる。素数 ${\displaystyle p}$ に対して鍵を ${\displaystyle k=(a,b)}$ としたとき、メッセージ ${\displaystyle m}$ のハッシュ値（MACにおけるタグ）は、${\displaystyle hash_{k}(m)=am+b\mod p}$ である。

応用例として、MACはSSH2においてトランスポート層のデータ一貫性を確保するために使用されている。MACの検証に用いる共通鍵は、通信の暗号化、復号に用いるセッション鍵と同様に、セッション開始時にディフィー・ヘルマン鍵共有によって生成された共有秘密からハッシュ関数によって生成される。実際に通信が始まったら、SSHプログラムは受信したパケットを復号したあと、MACと計算値を比較することでデータの完全性を検証している^[5][6]。

1. ^ IEEE 802.11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications ((2007 revision) ed.). IEEE-SA. (12 June 2007). doi:10.1109/IEEESTD.2007.373646. ISBN 978-0-7381-5656-9. http://standards.ieee.org/getieee802/download/802.11-2007.pdf 
2. ^ Fred B Schneider, Hashes and Message Digests, Cornell University
3. ^ “VMAC: Message Authentication Code using Universal Hashing”. CFRG Working Group. https://www.fastcrypto.org/vmac/draft-krovetz-vmac-01.txt 2010年3月16日閲覧。. 
4. ^ Simmons, Gustavus (1985). “Authentication theory/coding theory”. Advances in Cryptology: Proceedings of CRYPTO 84. Berlin: Springer. pp. 411–431 
5. ^ “rfc4251”. 2011年10月1日閲覧。
6. ^ “rfc4253”. 2011年10月1日閲覧。

• チェックサム
• HMAC
• 認証付き暗号 (AEAD)

• RSA FAQ's entry on MACs
• Ron Rivest lecture on MACs