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は固定長のメッセージについては安全であるが^[1]、可変長のメッセージについては安全ではない。そのため、ある鍵は固定長かつ既知の長さのメッセージにしか用いることはできない。これは、攻撃者が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'$ となる）。

この問題は、メッセージ長の情報を最後に追加することでは解決できない^[2]。可変長メッセージにおいてもCBC-MACを安全に利用するためには3つの主な改良法が存在する。一つ目は鍵の入力長の分割、2つめはメッセージ長の情報を先頭に追加すること、3つめは最後のブロックを暗号化することである^[2]。CMACやHMACのような、可変長メッセージでも安全な他の暗号利用モードを用いることも検討すべきである。

メッセージ長の先頭への追加[編集]

解決法の一つはメッセージ長を先頭ブロックに含めることである^[3]。メッセージ長に関する部分以外で冒頭部が一致する複数のメッセージを取り扱わない限りは、CBC-MACは安全であることが証明されている^[4]。しかし、プロセス開始時点でメッセージ長がわかっていない場合にはこの方法を用いることはできない。

最終ブロックの暗号化[編集]

最終ブロックの暗号化は ${\text{CBC-MAC-ELB}}(m,(k_{1},k_{2}))=E(k_{2},{\text{CBC-MAC}}(k_{1},m))$ と定義される^[2]。他の方法と違い、計算完了までメッセージ長を知る必要がない。

攻撃法[編集]

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と等価である。

脚注[編集]

^ M. Bellare, J. Kilian and P. Rogaway. The security of the cipher block chaining message authentication code. JCSS 61(3):362–399, 2000.
^ ^a ^b ^c See Section 5 of Bellare, et al.
^ ISO/IEC 9797-1:1999 Information technology – Security techniques – Message Authentication Codes (MACs) – Part 1: Mechanisms using a block cipher, clause 6.1.3 Padding Method 3
^ C. Rackoff and S. Gorbunov. On the Security of Block Chaining Message Authentication Code.

[BKR-1] M. Bellare, J. Kilian and P. Rogaway. The security of the cipher block chaining message authentication code. JCSS 61(3):362–399, 2000.

[:0-2] See Section 5 of Bellare, et al.

[3] ISO/IEC 9797-1:1999 Information technology – Security techniques – Message Authentication Codes (MACs) – Part 1: Mechanisms using a block cipher, clause 6.1.3 Padding Method 3

[:1-4] C. Rackoff and S. Gorbunov. On the Security of Block Chaining Message Authentication Code.

[1]

[2]

[3]

[4]