

I240 暗号理論 2019
モード型共通鍵暗号と MAC（２）2019/10/30 講師 藤崎

1 はじめに
モード型共通鍵暗号、MAC に共通する長い可変長の平文をどういうルールで分割するかを説明する。CBCモードは共通鍵暗号、MAC への利用ともに脆弱性があることを解説する。

2 メッセージの分割とパディング
モード型共通鍵暗号、MAC では、任意長の平文 m ∈ {0, 1}∗ を内部で固定長のブロックに分解し、ブロック暗号に入力して行く。ブロック暗号のブロックのサイズ n は方式によるが、AES ならば n = 128 ビット（16 バイト）である。この時、平文長が（ブロック暗号への平文（暗号文）の入力が n ビットとして）n の倍数になっていない場合、padding によりデータを埋めて n の倍数の長さにする必要がある。例えば、IETF(Internet Engineering Task Force) の RFC2040 では余ったバイト数の数だけ、そのバイト数を表現する数を埋める。例えば、22, 333, 55555 のように。実際は 16 進表現で、0x02 0x02,0x03 0x03 0x03,0x05 0x05 0x05 0x05 0x05のようなパディングが後方につけられる。平文がブロックの長さのぴったり倍数である場合は（１ブロック＝16z}|{16 バイトの場合）、余分に１ブロック追加し、0x10 · · · 0x10 で埋める。
他に、余ったバイトを全て 0x00 で埋めて（決まっていれば 0x00 でなくても良い）、１ブロック余計に加えてそのブロックに m のビット数 |m| を書き出すなど。これ以外にも様々なパディング方法があるがここでは紹介しない。
可変長の平文を扱うニーズは確実にあるが、しばしば脆弱性の原因となる（CBC モード暗号や CBC-MACのケース）。

3 CBC モード暗号への攻撃■CBC モード暗号（再掲載）

E, D をそれぞれブロック暗号の暗号化アルゴリズム、復号アルゴリズムとす∗る。平文 m ∈ {0, 1} をブロック暗号の入力サイズ n により t 個に分割 m = m1 | · · · |mt (mi ∈ {0, 1}n ) した後、図 2 のように暗号化、復号を行う。復号の際、平文のパディングが正しいか確認し、パディングが正しくない場合は ⊥（エラー）を返す。
■CBC モード暗号への攻撃 RFC2040 の平文のパディングを少し一般化する。ブロック暗号の１ブロックをb 個のワードからできているとし、W を 1 ワード取りうる個数とする（b ≤ W ）。RFC2040 では、W = 256,b = 16 n = 128 となっている。平文が (b − w) ワード（1 ≤ w < b）から出来ていれば、最後の w ワードをbwz }| {z }| {w · · · w で埋める（平文がちょうど b ワードなら、１ブロック追加して、b · · · b で埋める）。

1*&*)⋯*(+,+, ⋯+,!)!(#$* = *& | ⋯ |*(! = #$ |!& | ⋯ |!(#$!&⋯

図 1 CBC モード

CBC-Enc Ecbc (k, m)

CBC-DEC Dcbc (k, c) :iv ← {0, 1}n ; c0 := iv;

Parse as c = c0 |c1 | · · · |ct ;for i = 1, . . . , t dofor i = 1, . . . , t do

ci := E(k, ci−1 ⊕ mi );xi := D(k, ci ) ⊕ ci−1

return c := iv|c1 | · · · |ct .

If xt is a correct padding,return m := x1 | · · · |xt ,otherwise ⊥.
図 2 CBC-Encryption■パディングオラクル攻撃 実環境で、自分の望む暗号文を自由に復号してくれる選択暗号文攻撃可能な環境はなかなか無い。だが、暗号文が正しい暗号文かそれとも壊れた正しく無い暗号文かを判定してくれる環境は実環境でも十分ありうる。実際 TLS/SSL などでもそのようなことが起きる。パディングオラクルとは、暗号文を復号したとき、平文のパディングが正しければ 1 を、正しくなければ 0 を返し、作られた暗号文が正しいものか否かを判定してくれるオラクルである。Vaudenay はそのようなパディングオラクルがあれば、CBCモード暗号を破れることを示した。
定理 1（Vaudenay [Vau02]） 平文へのパディングが RFC2040 に準拠するものとする。このとき、敵は高々N bW 回のパディングオラクルへのアクセスで、ターゲット暗号文を全て解読できる。ここで、N はターゲッ
ト暗号文 c のブロック数（|c| = nN ）である。実際は、平均 N bW回のアクセスで暗号文を解読できる。
2(証明) 簡単のためターゲット暗号文 c = (iv, c1 )（iv, c1 ∈ {0, 1}n ）とする（すなわち、N = 1）。敵は、
rb ∈ [1, W − 1] を一つ選び、最初の b − 1 ワードを 0 にしたブロック暗号の１ブロック（n ビット長）を作る。
b−1z }| {Rb = (0, . . . , 0, rb ) ∈ {0, 1}n .
次に、暗号文 c′ = ((Rb ⊕ iv), c1 ) をパディングオラクルへ渡す。パディングオラクルは x′ = (Rb ⊕ iv) ⊕Dk (c1 ) を計算し、x′ のパディングが正しければ 1 を返し、そうでなければ 0 を返す。いま、ターゲット暗号文の平文を m = (x1 , . . . , xb ) とする（xi ∈ [0, W − 1]）。x′ の最後のワードは rb ⊕ xb であることに注意する。
もし、rb ⊕ xb = 1 であれば、x′ は (b − 1) ワードの平文に最後のワードに 1 をパディングしたものとなるので、パディングオラクルは 1 を返し、そうでなければ、0 を返してくる。よって、rb ∈ [1, W ] をすべてのワードで試すことで、どこかで、rb ⊕ xb = 1 を見つけることができ、それにより、xb = rb ⊕ 1 を求めることができる。

2

この手順を繰り返すことで平文全てを次のように求めることができる。xb はすでに知っているので、

rb := xb ⊕ 2 と rb を改めて定義しなおす。適当なワード rb−1 を選び、b−2z }| {Rb−1 = (0, . . . , 0, rb−1 , rb ) ∈ {0, 1}nとする。次に暗号文 c′ = ((Rb−1 ⊕ iv), c1 ) をパディングオラクルへ渡す。前と同様、パディングオラクルは x′ = (Rb ⊕ iv) ⊕ Dk (c1 ) を計算する。x′ の最後のワードは、2(= xb ⊕ rb ) となっているので、もし、xb−1 ⊕ rb−1 = 2 であれば正しいパディングとなる。rb−1 を全てのワードで試すことで、xb−1 ⊕ rb−1 = 2 を見つけられるので、xb−1 を得られる。いま、xb−1 , xb がわかるようになったので、rb−1 := xb−1 ⊕ 3, rb := xb ⊕ 3と改めて定義し同じことを繰り返すことで、最終的に平文 m = (x1 , . . . , xb ) を全て求めることができる。その時、パディングオラクルに問い合わせる回数は高々 bW 回になる。
もし、暗号文が c = (iv, c1 , . . . , cN ) であれば、平文全てを求めるのに最大 N bW 回のパディングオラクルへのアクセスが必要となる。
問題 2

もし、IND-CCA ゲームであれば、敵は高々 W 回の復号オラクルへのアクセスでゲームに勝つだけでなく、ターゲットの平文を全て知ることができることを示せ。
注釈 3

平文を RFC2040 パディングのようにしたのち、余剰の１ブロックに平文のビット数を書き込む |m|

方法では、Vaudenay の攻撃は本質的に防げないことが知られている。
パディングをどうにかして CBC モード暗号を安全にするという試みは証明可能安全性という観点では恐らく成功していない。

4 CBC-MAC と EMAC
4.1 MAC の安全性モデル（再掲載）
メッセージ認証 MAC = (K, M, S, V) の (q, ϵ)-安全性は、次のようなゲームを通じて定義される。鍵の長さ（セキュリティパラメータ）を κ := log |K| と書くことにする。
■EUF-CMA ゲーム（MAC 版）

敵 (adversary) A とチャレンジャー C の間で行われるメッセージ認証方式 MAC の安全性を試すゲームである *1 。

1. C は鍵空間 K から一様ランダムに鍵 k を選ぶ。k ← K.
2. A は平文 m を S(k, ·) オラクルに送り、対応する認証子 τ ← S(k, m) を答えとしてもらう。平文 m の選び方は A の戦略による。A は最大 q 回まで質問 (query) をすることができる。A が、平文を質問しその答えとして認証子をもらう行為を、A の S(k, ·) オラクルへのアクセスと呼ぶ。S(k, ·) オラクルへのアクセス履歴を L = {(m1 , τ1 ), . . . , (mq , τq )} とし、アクセス平文の集合を特に L(m) = {m1 , . . . , mq }と書くことにする。

3. A は、平文と認証子の組 (m∗ , τ ∗ ) を出力する。
4. もし、m∗ が、S(k, ·) オラクルへ質問したことのない新しい平文であり (m∗ ̸∈ L(m)), V(k, m∗ , τ ∗ ) = 1を満たすのであれば、A の勝ちと定義する。

A が、メッセージ認証方式 MAC に対する EUF-CMA ゲームに勝つ確率を、A の MAC に対するアドバン*1 チェレンジャーは明示的には表現されないときもある。

3

!(#,⋅)'( , … , '*+( , . . , +*('∗ , + ∗ )図 3 MAC の EUF-CMA ゲーム

テージと呼び、∗ ∗S(k,·)
Adveuf-cma: V(k, m∗ , τ ∗ ) = 1 and m∗ ̸∈ L(m)].
A,MAC (q, κ) := Pr[k ← K; (m , τ ) ← A

定義 4（メッセージ認証の安全性） 最大 q 回の質問をする任意の敵 A のアドバンテージが、
Adveuf-cma
A,MAC (q, κ) ≤ϵ で あ る と き 、メ ッ セ ー ジ 認 証 方 式 MAC は (q, ϵ)-安 全 で あ る と い う 。特 に 、q = O(κ) の と き 、Adveuf-cma
A,MAC (κ) = negl(κ) であるならば、メッセージ認証方式 MAC は安全であるという。
注釈 5

q = 1 のとき、MAC は OT-安全ということにする。(1, ϵ)-安全 = ϵ-OT-安全.

4.2 モード型 MAC■CBC-MAC CBC-MAC の仕様。認証子作成は、平文 m ∈ {0, 1}∗ をブロック暗号の入力サイズ n によりt 個に分割 m = m1 | · · · |mt (mi ∈ {0, 1}n ) した後、図 4 のように秘密鍵 k を使って認証子 τ を生成する。
認証子の検証は、(m, τ ) を受け取った後、m から図 4 のように秘密鍵 k を使って認証子 τ ′ を作成し、τ = τ ′であれば受理し、τ ̸= τ ′ であれば否認する。

Input m.

$%$&⋯$'!"!" ⋯!"Output τ .
Parse m = m1 | · · · · · · |mt ;c0 := 0n ;For i = 1, . . . , t do
ci := E(k, ci−1 ⊕ mi );(return τ := ct .
図 4 CBC-MAC

CBC-MAC は平文の長さが固定長のときは安全性証明がつくことが知られているが [BKR00]、逆に可変長のときは安全性に問題があることが知られている。

44.2.1 CBC-MAC への攻撃
(1)

Ek (m1 ) := Ek (m1 ) とし、(t)(t−1)

Ek (m1 , . . . , mt ) := Ek (Ekと定義する。そのとき、m = m1 | · · · |mt(m1 , . . . , mt−1 ) ⊕ mt )where t ≥ 2.
(t)の CBC-MAC の認証子は τ = Ek (m1 , . . . , mt )となる。

敵は次のように CBC-MAC を攻撃できる。任意の m = m1 | · · · |mt （t ≥ 1）を MAC オラクルに質問し、認証子 τ をもらう。偽造の平文と認証子のペアーとして、

m′ := m1 | m2 | · · · | mt | (τ ⊕ m1 ) | m2 | · · · | mtと τ を出力する。
(t+1)

Ek(m1 , . . . , mt , τ ⊕ m1 ) = Ek (τ ⊕ (τ ⊕ m1 )) = Ek (m1 )に注意すると、τ が m′ の認証子になっていることがわかる。これは、RFC2040 のパディングをしても防げないことはすぐわかるが、実は後ろに m のビット長 |m| をブロックとして追加しても偽造が防げない。

E∗k (m1 , . . . , mt ) := Ek (Ek (m1 , . . . , mt ) ⊕ |m|)(t)と 定 義 す る 。後 ろ に |m| を パ デ ィ ン グ す る 方 式 を 採 用 し た 場 合 、m = m1 | · · · |mt の 認 証 子 は τ =E∗k (m1 , . . . , mt ) になる。今、敵は次のような３つの質問を MAC オラクルにし、認証子を受け取る。m1 , m2 ,m′ は 1 ブロック（= n ビット）とするが同じ長さなら何でも良い。
• τ1 = E∗k (m1 ) = Ek (m1 , n) = Ek (Ek (m1 ) ⊕ n)(2)

• τ2 = E∗k (m2 ) = Ek (m2 , n) = Ek (Ek (m2 ) ⊕ n)(2)

• τ ′ = E∗k (m1 , n, m′ ) = E∗k (Ek (m1 ) ⊕ n, m′ ) = E∗k (τ1 ⊕ m′ )= Ek (τ1 ⊕ m′ , 3n) = Ek (Ek (τ1 ⊕ m′ ) ⊕ 3n)(2)

上の３式から、3n ビットの平文 m3 := m2 |n|(τ1 ⊕ τ2 ⊕ m′ ) の認証子はE∗k (m2 , n, (τ1 ⊕ τ2 ⊕ m3 )) = E∗k ((Ek (m2 ) ⊕ n), (τ1 ⊕ τ2 ⊕ m′ ))= E∗k (τ2 ⊕ (τ1 ⊕ τ2 ⊕ m′ ))= E∗k (τ1 ⊕ m′ )よって、τ ′ = E∗k (m2 , n, (τ1 ⊕ τ2 ⊕ m3 )) なので、平文 m3 への認証子が偽造できた。
問題 6

CBC-MAC は RFC2040 のパディングをしても安全にならないことを示せ。

■EMAC CBC-MAC の最後の ct を認証子にする代わりに、独立の秘密鍵 k ′ で τ = E(k ′ , ct ) と ct を暗号化し、τ を認証子とする。EMAC は平文の長さがブロックの整数倍（すなわち、|m| = nℓ）で有る限り、可変長であっても「安全」になる。EMAC をさらに少し変形して、平文の長さが任意の可変長であっても安全にすることができる [BR05].

参考文献[BKR00] Mihir Bellare, Joe Kilian, and Phillip Rogaway. The security of the cipher block chaining
message authentication code. Journal of Computer and System Sciences, 61(3):362–399, 2000.
5Input m.

$%$&⋯$'!"!" ⋯!"Output τ .
Parse m = m1 | · · · · · · |mt ;c0 := 0n ;For i = 1, . . . , t do
ci := E(k, ci−1 ⊕ mi );!")τ := E(k ′ , ct );(return τ .
図 5 EMAC[BR05]

John Black and Phillip Rogaway. CBC MACs for arbitrary-length messages: The three-key
constructions. Journal of Cryptology, 18(2):111–131, April 2005.

[Vau02] Serge Vaudenay. Security flaws induced by CBC padding - applications to SSL, IPSEC,
WTLS... In Lars R. Knudsen, editor, EUROCRYPT 2002, volume 2332 of LNCS, pages
534–546. Springer, Heidelberg, April / May 2002.

6