CBC-MAC

CBC-MAC (cipher block chaining message authentication code) は、ブロック暗号からメッセージ認証符号を生成する手法である。あるブロック暗号のCBCモードでメッセージを暗号化することで暗号ブロックの連鎖を形成すると、それぞれのブロックの暗号化はその前のブロックの暗号化の結果に依存する。そのため、平文が1ビットでも変化すると、暗号化後の最終ブロックも変化することとなる。
メッセージ formula_1 のCBC-MACを計算するには、初期化ベクトルを0としてCBCモードで暗号化を行う。次の図は、メッセージ formula_1 を formula_3 とブロックに分割し、秘密鍵 formula_4 とブロック暗号 formula_5 を用いてCBC-MACを計算する様子を示している。
固定長及び可変長のメッセージにおけるセキュリティ.
ブロック暗号が安全であれば、CBC-MACは固定長のメッセージについては安全であるが、可変長のメッセージについては安全ではない。そのため、ある鍵は固定長かつ既知の長さのメッセージにしか用いることはできない。これは、攻撃者が2組のメッセージ‐CBC-MACのペア formula_6 および formula_7 を知っている場合、CBC-MACが formula_8 となるメッセージ formula_9 を生成することが可能であるためである。メッセージ formula_9 の生成は以下の手順となる。メッセージ formula_11 の最初のブロックと formula_12 の排他的論理和をとり、メッセージ formula_1 とこの改変したメッセージ formula_11 を連結する：formula_15。メッセージ formula_9 を計算する場合、メッセージ formula_1 の場合と同様タグ formula_12 までは通常に計算される。しかし、続く formula_19 の計算において、 formula_12 と formula_12 の排他的論理和を計算することとなるためこれは打ち消され、本来のメッセージ formula_1 はMAC値に寄与しないこととなる（formula_23 であるからメッセージ formula_9 のCBC-MACタグは formula_8となる）。
この問題は、メッセージ長の情報を最後に追加することでは解決できない。可変長メッセージにおいてもCBC-MACを安全に利用するためには3つの主な改良法が存在する。一つ目は鍵の入力長の分割、2つめはメッセージ長の情報を先頭に追加すること、3つめは最後のブロックを暗号化することである。CMACやHMACのような、可変長メッセージでも安全な他の暗号利用モードを用いることも検討すべきである。
メッセージ長の先頭への追加.
解決法の一つはメッセージ長を先頭ブロックに含めることである。メッセージ長に関する部分以外で冒頭部が一致する複数のメッセージを取り扱わない限りは、CBC-MACは安全であることが証明されている。しかし、プロセス開始時点でメッセージ長がわかっていない場合にはこの方法を用いることはできない。
最終ブロックの暗号化.
最終ブロックの暗号化は formula_26 と定義される。他の方法と違い、計算完了までメッセージ長を知る必要がない。
攻撃法.
CBC-MACの不適切な利用に対する攻撃法を示す。
暗号化と認証に同じ鍵を使用.
よくある間違いの一つは、CBCモードでの暗号化とCBC-MACに同じ鍵を使用することである。違う目的に鍵を使いまわすことは一般的に好ましくないが、CBC-MACにおいては攻撃を招く要因となる。
アリスがボブに暗号化したテキストブロック formula_27 およびタグ formula_12 を送った。通信経路上において、イブは任意の formula_29 を改変可能であり、最終ブロックが元と同じになるようにビット列を調節し、 formula_30 とすることができる。説明を簡略化するために、暗号化における初期化ベクトルは0とする。
ボブはまず、イブによって改変された暗号化メッセージ formula_31を共有した秘密鍵 formula_32 を用いて復号する。得られる平文は、アリスが送った formula_33 ではなくイブによって改変された formula_34 となる。このとき formula_35 となる。
続いてボブは得られた formula_34 についてCBC-MACタグを計算する。タグ formula_8 は以下のように求められる。
formula_38
この式は以下と等しく
formula_39
この結果は formula_40 と等しくなる。
formula_41
ゆえに formula_42 となる。
このように、イブは通信経路上において、元の平文を知ることなく暗号文を改変することができ、そのCBC-MACタグも元のタグと等しいため、ボブは通信経路上でコンテンツが改変されたことを検知することができない。すなわち、メッセージ認証符号として破綻している。
暗号化と認証に異なる鍵 formula_43 および formula_44 を用いた場合には、この攻撃は成功しない。
この例は、CBC-MACを衝突耐性のある一方向関数として用いることができないことも示している。
初期化ベクトルの使用.
ブロック暗号をCBCモードで利用してデータを暗号化する際、初めに初期化ベクトルを導入することは一般的である。初期化ベクトルはランダムに選択され、再使用されるべきではない。これにより、同じ平文を暗号化した場合でも暗号化の結果は異なるものとなり、攻撃者が「同じ暗号結果であるから元の平文は同じである」と推測することはできなくなる。
一方、CBC-MACのようなメッセージ認証符号を計算する際には、初期化ベクトルを使用してはならない。
CBCモードにおいては、平文の最初のブロックは初期化ベクトルとの排他的論理和 (formula_45) をとられ、これが暗号化される。
しかしながら、暗号化及び復号の際には、初期化ベクトルを平文で送る必要がある（暗号文の最初のブロックの前に平文ブロックとして送られることが多い）。CBC-MACにおいて初期化ベクトルを用いるとしたら、同様に初期化ベクトルを平文で送る必要がある。
初期化ベクトルの値を自由に選択可能な場合、CBC-MACタグを変えることなく平文の最初のブロックが改変される可能性がある。
メッセージ formula_46 について考える。初期化ベクトル formula_47 を用いてCBC-MACを計算すると仮定すると、MACタグの計算は formula_48 から開始されることとなる。(メッセージ, タグ) のペア formula_49 が得られる。
ここでメッセージ formula_50 を作成する。formula_51 の各々のビットは、初期化ベクトル formula_52 を生成するように初期化ベクトルと対応するビットを反転したものである。これのMAC値の計算は formula_53 から開始されることとなる。平文と初期化ベクトルの対応するビットが反転していることから、この改変はキャンセルされ、 formula_54 の場合と同じビット列が暗号化プロセスに回されることとなる。それ以外に平文に変更を加えないのであれば、異なるメッセージにもかかわらず同じタグが得られることとなる。
初期化ベクトルを自由に選択できないようにし、すべての実装で同じ初期化ベクトルを用いるようにすれば、この攻撃は回避できる。実際の実装では、初期化ベクトルは0とされている。
標準化.
FIPS PUB 113 "Computer Data Authentication" において、DESをブロック暗号として用いるCBC-MACがアメリカ合衆国の標準 (FIPS) として指定されている。また、CBC-MACはISO/IEC 9797-1 MAC Algorithm 1と等価である。