CBC-MAC

CBC-MAC（Cipher Block Chaining Message Authentication Code）とは

CBC-MACは、ブロック暗号を利用してメッセージ認証符号（MAC）を生成する手法の一つです。CBC（Cipher Block Chaining）モードでメッセージを暗号化する過程で、各ブロックの暗号化が前のブロックの結果に依存する連鎖構造を作り出すことを利用しています。この連鎖構造により、平文がわずか1ビットでも変化すると、最終的な暗号ブロックも変化するという特性を持ちます。

CBC-MACの計算方法

メッセージ `m` のCBC-MACを計算する際には、初期化ベクトル（IV）を0としてCBCモードで暗号化を行います。メッセージ `m` を `m1 || m2 || ... || mx` のようにブロック分割し、秘密鍵 `k` とブロック暗号 `E` を用いて計算を進めます。



`m`: メッセージ
`m1, m2, ..., mx`: メッセージを分割した各ブロック
`k`: 秘密鍵
`E`: ブロック暗号

固定長メッセージと可変長メッセージにおける安全性

ブロック暗号が安全であれば、CBC-MACは固定長のメッセージに対しては安全であるとされています。しかし、可変長のメッセージに対しては安全ではありません。なぜなら、攻撃者が異なるメッセージとそれに対応するMACのペアを知っている場合、別のメッセージに対して同じMACを生成することが可能だからです。

具体的には、メッセージとMACのペア `(m, t)` および `(m', t')` を攻撃者が知っている場合、以下の手順で新たなメッセージ `m''` を作成し、`t'` と同じMACを生成できます。

1. `m'` の最初のブロック `m1'` と `t` の排他的論理和を計算します。
2. `m` と改変した `m'` を連結します: `m'' = m || [(m1' ⊕ t) || m2' || ... || mx']`

この `m''` に対してCBC-MACを計算すると、`m` の部分までは通常の計算が行われますが、続くブロックの計算で、`t` と `t` の排他的論理和が打ち消し合うため、結果的に `m` の部分はMAC値に寄与しなくなります。その結果、`m''` のMACは `t'` と同じになります。


m'' のCBC-MACタグは t' となる


この脆弱性のため、一つの鍵は固定長で既知の長さのメッセージにしか使えません。

可変長メッセージへの対応策

可変長メッセージでもCBC-MACを安全に利用するための主な改良法は3つあります。

1. 鍵の入力長の分割: 複数の鍵を使用する方法。
2. メッセージ長の先頭への追加: メッセージの先頭にメッセージ長を含める方法。これにより、異なるメッセージ長のメッセージに対する攻撃を防ぎますが、メッセージの長さが事前に不明な場合は使用できません。
3. 最終ブロックの暗号化: CBC-MACの最終結果を別の鍵で暗号化する方法 (CBC-MAC-ELB)。この方法はメッセージの長さが不明な場合でも対応できます。

また、CMACやHMACのような、可変長メッセージに対して安全な他の暗号利用モードの採用も検討すべきです。

攻撃例

暗号化と認証に同じ鍵を使用した場合

暗号化と認証の両方に同じ鍵を使用すると、深刻な攻撃につながる可能性があります。

例えば、アリスが暗号化されたメッセージ `C` とそのタグ `t` をボブに送ったとします。攻撃者イブは、メッセージの一部分 `C1, ..., Cn-1` を改変し、`Cn` をそのままにすることで、改変されたメッセージ `C'` を作成します。ボブは、イブによって改変されたメッセージ `C'` を復号し、改変された平文 `P'` を得ますが、最終ブロックの`Pn'`を計算する際に `Cn-1'`の影響を受けるため、アリスの送った平文とは異なる結果となります。

しかし、改変されたメッセージ `C'` から計算されたCBC-MACタグは、元のタグ `t` と同じになります。これは、`C'` の最終ブロックが元と同じであり、CBC-MACの計算が前のブロックの暗号結果に依存するため、改変された部分の影響が相殺されるためです。

この結果、ボブは通信内容が改ざんされたことを検知できず、メッセージ認証符号としての役割を果たすことができません。

初期化ベクトルの使用

CBC-MACの計算に初期化ベクトルを使用すると、攻撃者がタグを変えることなく平文の最初のブロックを改変することが可能になります。

具体的には、攻撃者は、メッセージの最初のブロックと初期化ベクトルの対応するビットを反転させることで、異なるメッセージで同じタグを生成できます。このため、CBC-MACでは初期化ベクトルを使用せず、常に0を使用する必要があります。

標準化

CBC-MACは、FIPS PUB 113でDESをブロック暗号として使用する形式で標準化されています。また、ISO/IEC 9797-1 MAC Algorithm 1とも等価です。

関連技術

CMAC: 可変長のメッセージに対して安全な、ブロック暗号をベースにしたMACアルゴリズム。
One-key MAC, PMAC: ブロック暗号をベースとしたメッセージ認証符号アルゴリズム。

まとめ

CBC-MACは固定長メッセージに対するメッセージ認証に有効ですが、可変長メッセージに対して脆弱性があります。安全に利用するためには、メッセージ長を先頭に追加する、最終ブロックを暗号化するなどの対策が必要となります。また、暗号化と認証に同じ鍵を使用したり、初期化ベクトルを使用したりすることは避けるべきです。可変長メッセージ認証には、CMACやHMACなどのより安全なアルゴリズムの使用を推奨します。

もう一度検索