CBC-MAC
CBC-MAC (cipher block chaining message authentication code) は、ブロック暗号からメッセージ認証符号を生成する手法である。あるブロック暗号のCBCモードでメッセージを暗号化することで暗号ブロックの連鎖を形成すると、それぞれのブロックの暗号化はその前のブロックの暗号化の結果に依存する。そのため、平文が1ビットでも変化すると、暗号化後の最終ブロックも変化することとなる。
メッセージ m のCBC-MACを計算するには、初期化ベクトルを0としてCBCモードで暗号化を行う。次の図は、メッセージ m を m_1\|m_2\|\cdots\|m_x とブロックに分割し、秘密鍵 k とブロック暗号 E を用いてCBC-MACを計算する様子を示している。
ブロック暗号が安全であれば、CBC-MACは固定長のメッセージについては安全であるが、可変長のメッセージについては安全ではない。そのため、ある鍵は固定長かつ既知の長さのメッセージにしか用いることはできない。これは、攻撃者が2組のメッセージ‐CBC-MACのペア (m, t) および (m', t') を知っている場合、CBC-MACが t' となるメッセージ m を生成することが可能であるためである。メッセージ m の生成は以下の手順となる。メッセージ m' の最初のブロックと t の排他的論理和をとり、メッセージ m とこの改変したメッセージ m' を連結する:m = m \| [(m_1' \oplus t) \| m_2' \| \dots \| m_x']。メッセージ m を計算する場合、メッセージ m の場合と同様タグ t までは通常に計算される。しかし、続く E_{K_{MAC}(m_1' \oplus t) の計算において、 t と t の排他的論理和を計算することとなるためこれは打ち消され、本来のメッセージ m はMAC値に寄与しないこととなる(E_{K_{MAC}(m_1' \oplus t \oplus t) = E_{K_{MAC}(m_1') であるからメッセージ m のCBC-MACタグは t'となる)。
この問題は、メッセージ長の情報を最後に追加することでは解決できない。可変長メッセージにおいてもCBC-MACを安全に利用するためには3つの主な改良法が存在する。一つ目は鍵の入力長の分割、2つめはメッセージ長の情報を先頭に追加すること、3つめは最後のブロックを暗号化することである。CMACやHMACのような、可変長メッセージでも安全な他の暗号利用モードを用いることも検討すべきである。
解決法の一つはメッセージ長を先頭ブロックに含めることである。メッセージ長に関する部分以外で冒頭部が一致する複数のメッセージを取り扱わない限りは、CBC-MACは安全であることが証明されている。しかし、プロセス開始時点でメッセージ長がわかっていない場合にはこの方法を用いることはできない。
最終ブロックの暗号化は \text{CBC-MAC-ELB}(m, (k_1, k_2)) = E(k_2, \text{CBC-MAC}(k_1, m)) と定義される。他の方法と違い、計算完了までメッセージ長を知る必要がない。
CBC-MACの不適切な利用に対する攻撃法を示す。
よくある間違いの一つは、CBCモードでの暗号化とCBC-MACに同じ鍵を使用することである。違う目的に鍵を使いまわすことは一般的に好ましくないが、CBC-MACにおいては攻撃を招く要因となる。
アリスがボブに暗号化したテキストブロック C = C_1\ ||\ C_2\ ||\ \dots\ ||\ C_n およびタグ t を送った。通信経路上において、イブは任意の C_1 , \dots , C_{n-1} を改変可能であり、最終ブロックが元と同じになるようにビット列を調節し、 C'=C_1'\ ||\ \dots\ ||\ C_{n-1}'\ ||\ C_n とすることができる。説明を簡略化するために、暗号化における初期化ベクトルは0とする。
ボブはまず、イブによって改変された暗号化メッセージ C'を共有した秘密鍵 K を用いて復号する。得られる平文は、アリスが送った P_n ではなくイブによって改変された P_n' となる。このとき P_n' = C_{n-1}' \oplus E_K^{-1}(C_n) となる。
続いてボブは得られた P_n' についてCBC-MACタグを計算する。タグ t' は以下のように求められる。
t' = E_K(P_n' \oplus E_K(P_{n-1}' \oplus E_K( \dots \oplus E_K(P_1'))))
t' = E_K(P_n' \oplus C_{n-1}')
この結果は C_n と等しくなる。
t' = E_K(C_{n-1}' \oplus E_K^{-1}(C_n) \oplus C_{n-1}') = E_K(E_K^{-1}(C_n)) = C_n
ゆえに t' = C_n = t となる。
このように、イブは通信経路上において、元の平文を知ることなく暗号文を改変することができ、そのCBC-MACタグも元のタグと等しいため、ボブは通信経路上でコンテンツが改変されたことを検知することができない。すなわち、メッセージ認証符号として破綻している。
暗号化と認証に異なる鍵 K_1 および K_2 を用いた場合には、この攻撃は成功しない。
この例は、CBC-MACを衝突耐性のある一方向関数として用いることができないことも示している。
ブロック暗号をCBCモードで利用してデータを暗号化する際、初めに初期化ベクトルを導入することは一般的である。初期化ベクトルはランダムに選択され、再使用されるべきではない。これにより、同じ平文を暗号化した場合でも暗号化の結果は異なるものとなり、攻撃者が「同じ暗号結果であるから元の平文は同じである」と推測することはできなくなる。
一方、CBC-MACのようなメッセージ認証符号を計算する際には、初期化ベクトルを使用してはならない。
CBCモードにおいては、平文の最初のブロックは初期化ベクトルとの排他的論理和 (P_1 \oplus IV) をとられ、これが暗号化される。
しかしながら、暗号化及び復号の際には、初期化ベクトルを平文で送る必要がある(暗号文の最初のブロックの前に平文ブロックとして送られることが多い)。CBC-MACにおいて初期化ベクトルを用いるとしたら、同様に初期化ベクトルを平文で送る必要がある。
初期化ベクトルの値を自由に選択可能な場合、CBC-MACタグを変えることなく平文の最初のブロックが改変される可能性がある。
メッセージ M_1 = P_1 | P_2 | \dots について考える。初期化ベクトル IV_1 を用いてCBC-MACを計算すると仮定すると、MACタグの計算は E_K(IV_1 \oplus P_1) から開始されることとなる。(メッセージ, タグ) のペア (M_1, T_1) が得られる。
ここでメッセージ M_2 = P_1' | P_2 | \dots を作成する。P_1' の各々のビットは、初期化ベクトル IV_1' を生成するように初期化ベクトルと対応するビットを反転したものである。これのMAC値の計算は E_K(P_1' \oplus IV_1') から開始されることとなる。平文と初期化ベクトルの対応するビットが反転していることから、この改変はキャンセルされ、 M_1 の場合と同じビット列が暗号化プロセスに回されることとなる。それ以外に平文に変更を加えないのであれば、異なるメッセージにもかかわらず同じタグが得られることとなる。
初期化ベクトルを自由に選択できないようにし、すべての実装で同じ初期化ベクトルを用いるようにすれば、この攻撃は回避できる。実際の実装では、初期化ベクトルは0とされている。
FIPS PUB 113 Computer Data Authentication において、DESをブロック暗号として用いるCBC-MACがアメリカ合衆国の標準 (FIPS) として指定されている。また、CBC-MACはISO/IEC 9797-1 MAC Algorithm 1と等価である。