

I240 暗号理論 2019
モード型共通鍵暗号
2019/10/18 講師 藤崎

1 はじめに理想論でなく実際に使われる共通鍵暗号についてすこし触れる。実際に使われる共通鍵暗号は、固定長の平文 m ∈ {0, 1}n を置換により暗号化するブロック暗号と呼ばれるものを部品とし、モード (mode ofoperation) と呼ばれる技術により、可変長の平文 m ∈ {0, 1}∗ を暗号文に変換している。ブロック暗号そのものも共通鍵暗号である。
ブロック暗号は理想としてランダム置換であって欲しいが、現実的にはそのようなものを n の多項式時間のアルゴリズムで作ることは不可能である。しかし、モード型の共通鍵暗号、MAC では便宜上ブロック暗号をランダム置換として考え、安全性を議論することが通例である。

2 ブロック暗号 (Block cipher)
ブロック暗号 SKE = (K, M, E, D) は、K = {0, 1}ℓ , M = {0, 1}n として、E, D が、

E :{0, 1}ℓ × {0, 1}n → {0, 1}n
D :{0, 1}ℓ × {0, 1}n → {0, 1}nD(k, E(k, m)) = m を満たすような（k を固定した時）{0, 1}n 上の置換と逆置換になっているようなものである。理想のブロック暗号は、秘密鍵 k をランダムに選んだ時 E(k, ·) がランダム置換 (random permutation)になっていることであるが、実際にそれを実現することは効率的なアルゴリズムでは不可能である。しかし、後述のモードで述べるように、モードを使った共通鍵暗号や MAC の安全性を考える時、ブロック暗号をランダム置換と考えて扱う。

AES (Adavanced Encryption Standard) は、NIST 標準の有名なブロック暗号であり、128 ビットの平文を暗号化出来る（すなわち n = 128）。一方、鍵は 128, 192, 256 ビットのサイズを選ぶことができ（すなわちℓ = 128, 192, 256）、それぞれ AES-128, AES-192, AES-256 と呼ばれる。
問題 1{0, 1}n 上起こりうる置換 (permutation) π : {0, 1}n → {0, 1}n の個数を求めよ。

2.1 モード型共通鍵暗号
以下、いくつかのモード型共通鍵暗号を紹介する。モード型共通鍵暗号は、可変長の平文 m ∈ {0, 1}∗ を暗号化することができる。
■ECB モード暗号 大きな欠点があり秘匿が十分でないので現在はほとんど使われていない。図 1 のように、
平文 m ∈ {0, 1}∗ をブロック暗号の入力サイズ n により t 個に分割 m = m1 | · · · |mt (mi ∈ {0, 1}n ) した後、c1 = E(k, m1 ), . . . , ct = E(k, mt )1

を計算し暗号文を c = c1 | · · · |ct とする単純な暗号方式である。復号は自明なので省略。
!"! = !" | ⋯ |!'⋯!(⋯ !')* ⋯ )* ⋯ )*# = #" | ⋯ |#'#" ⋯#(⋯#'

図 1 ECB モード■CBC モード暗号

現在もよく使われているが、平文の長さを可変長にすると問題があることがすでに 2002

年から知られている [Vau02]. 実際、最新バージョンの TLS (Transport Layer Security) *1 より前の TLS は

CBC モードの共通鍵暗号をサポートしている（例えば、AES-256 と組み合わせて、AES-256-CBC のように使われる）が、多くの TLS の新しい攻撃を生み出す元凶となっている。一方、平文の長さを固定長に限定し、IV を一様ランダムにとり、部品であるブロック暗号がランダム置換であると仮定すると安全性が証明できる
ことが知られている [BDJR97]。

E, D をそれぞれブロック暗号の暗号化アルゴリズム、復号アルゴリズムとする。平文 m ∈ {0, 1}∗ をブ
ロック暗号の入力サイズ n により t 個に分割 m = m1 | · · · |mt (mi ∈ {0, 1}n ) した後、図 2 のように暗号化、復号を行う。

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 .

return m := x1 | · · · |xt .
図 2 CBC-Encryption* = *& | ⋯ |*(! = #$ |!& | ⋯ |!(#$#$*&*)⋯*(+,+, ⋯+,!)!(!&図 3 CBC モード*1 2019 年１０月現在の最新バージョンは TLS 1.3.

2⋯

■CTR モード暗号

安全性が証明されているステートがある (stateful) 共通鍵暗号。暗号化アルゴリズムはカウンター ctr を持っている。暗号化は、図 4 のように平文 m ∈ {0, 1}∗ をブロック暗号の入力サイズ n に
より t 個に分割 m = m1 | · · · |mt (mi ∈ {0, 1}n ) した後、

c1 = m1 ⊕ E(k, ctr), . . . , ct = mt ⊕ E(k, ctr + t)とし、暗号文を c := ctr|c1 | · · · |ct とする。最後に暗号化アルゴリズムはカウンターを ctr := ctr + t と更新する。
* = *& | ⋯ |*( ⋯ ⋯ +, ⋯ +, ⋯ +,*&! = !#$|!& | ⋯ |!(!& ⋯*(*)!)⋯!(

図 4 CTR モード

一方復号は、暗号文 c := ctr|c1 | · · · |ct を受け取った後、m1 = c1 ⊕ E(k, ctr), . . . , mt = ct ⊕ E(k, ctr + t)を計算し、m := m1 | · · · |mt を出力する。

2.2 モード型共通鍵暗号の安全性モデル
モード型共通鍵暗号の安全性モデルを定義しておく [BDJR97]。
■CPA かつ CCA 攻撃ゲーム

敵 (adversary) A とチャレンジャー C の間で行われるモード型共通鍵暗号

SKE = (K, M, E, D) の安全性を試すゲームである。ここで、SKE はモード型暗号のため、M = {0, 1}∗ とし、E, D はモード型暗号の暗号化アルゴリズム、復号アルゴリズムである（ブロック暗号の暗号化アルゴリ
ズム、復号アルゴリズムでは無いので注意）。今、K = {0, 1}κ としておく。

1. C は鍵空間 K から一様ランダムに鍵 k を選ぶ。k ← K.
2. C は一様ランダムにビット b∗ ← {0, 1} を選ぶ。
∗3.（チャレンジ）A は、自分の戦略に従って二つの平文の組 (m0 , m1 ) を暗号化オラクル Eb (k, ·) に送り、暗号化オラクルから暗号文 c∗ = E(k, mb∗ ) を受け取る。A は d 回までこの質問を暗号化オラクルにすることができる。ただし d = O(κ) である。

4.（選択平文攻撃 (chosen-plaintext attack (CPA))）A は平文 m を暗号化オラクルに送り、暗号文c = E(k, m) を答えとしてもらう。平文 m の選び方は A の戦略による。A は合計 qe 回まで質問(query) を送ることができる。記述を簡単にするため、暗号化オラクルをチャレンジの暗号化オラクル∗Eb (k, ·) で代用することとする。選択平文攻撃をしたいときは、A は、同じ平文の組 (m, m) を暗号∗化オラクルに質問すれば良い。よって、qe < d となる。A の Eb (k, ·) オラクルへのアクセス履歴をL = {(m10 , m11 , c∗1 ), . . . , (md0 , md1 , c∗d )} とし、特に L(c) = {c∗1 , . . . , c∗d } と書くことにする。
3

5.（選択暗号文攻撃 (chosen-ciphertext attack (CCA))）A は暗号文 c を復号オラクル D(k, ·) に送り、m = D(k, c) をもらうことができる。ただし、すでに L(c) に入っている暗号文は復号オラクルに質問できない。暗号文 c の選び方は A の戦略による。A は合計 q = O(κ) 回まで質問 (query) を送ることができる。

6. A は、ビット b を出力する。
7. もし、b = b∗ であれば、A の勝ちと定義する。
d, q = O(κ) であれば、回数はあらかじめ決まっていなくて良い。A が、SKE に対する CPA&CCA ゲームに勝つ確率の 1/2 からの差を正規化したものを、A の C に対するアドバンテージと呼び、
κ∗E
Advcpa,cca
A,SKE (κ) := 2 Pr[k ← {0, 1} ; b ← {0, 1} : Ab∗(k,·),D(k,·)= b∗ ] − 1.と定義する。

!(#,⋅)'( , … , '*(+(., +((), … , (+./ , +(/ )'(∗ , … '7∗ , … , '/∗+( , . . , +*+8 = !(#, '8 )∗0 1 (#,⋅)
3 = 1, … , 6'7∗ = 0(#, +17 ∗ )図5

共通鍵暗号の攻撃モデル

cpa,cca

定義 2（モード型共通鍵暗号の安全性） 任意の敵 A に対して、AdvA,SKE (κ) = negl(κ) であるとき、モード型暗号 SKE は CPA かつ CCA 安全と呼ぶ。negl(κ) := κ−ω(1) である。
注釈 3

CTR モード暗号のようなステートがある暗号の場合、A は暗号化オラクルが暗号化に利用した ctrの値が含まれる暗号文を復号オラクルに質問として送ることはできないと定義する。

参考文献[BDJR97] Mihir Bellare, Anand Desai, Eric Jokipii, and Phillip Rogaway. A concrete security treatmentof symmetric encryption. In 38th FOCS, pages 394–403. IEEE Computer Society Press,October 1997.
[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.

4