詳細評価報告書
Camellia 攻撃評価

平成 13 年 1 月 10 日

1 概要................................
概要 ................................................................
................................................................................................
................................................................................................
......................................................................
...................................... 1
1.1 評価結果概要.......................................................................................................................1
1.2 定義 .....................................................................................................................................1
2 差分解読、線形解読 ................................................................
................................................................................................
.............................................................................
............................................. 2
3 バイト多項式による解析 ................................................................
................................................................................................
......................................................................
...................................... 2
3.1 手法 1 ..................................................................................................................................3
3.2 手法 2 ..................................................................................................................................5
4 BOOMERANG 攻撃 ................................................................
................................................................................................
.............................................................................
............................................. 6
5 SQUARE 攻撃 ................................................................
................................................................................................
......................................................................................
...................................................... 8
6 丸め差分攻撃................................
丸め差分攻撃 ................................................................
................................................................................................
........................................................................................
........................................................ 9
7 高階差分攻撃................................
高階差分攻撃 ................................................................
................................................................................................
......................................................................................
...................................................... 108 補間攻撃................................
補間攻撃 ................................................................
................................................................................................
.............................................................................................
............................................................. 119 鍵生成部の特性 ................................................................
................................................................................................
..................................................................................
.................................................. 1210 弱鍵................................
弱鍵 ................................................................
................................................................................................
................................................................................................
..................................................................
.................................. 13
11 その他 ................................................................
................................................................................................
..............................................................................................
.............................................................. 13
12 まとめ ................................................................
................................................................................................
..............................................................................................
.............................................................. 14

i

1 概要
1.1 評価結果概要
Camellia に対して安全性評価を行った。
いくつかの攻撃を試行した範囲では、FL/FL-1 関数を除いた変形 Camellia 8 段が、秘密鍵
総当たりより少ない計算量で鍵を推定することが可能であろうという結果になった。
また秘密鍵 5 バイトと中間鍵 6 バイトから、不明な秘密鍵 1 バイトを計算できる場合が存在する。
我々が行った評価の限りでは、安全性に関する問題は見つからなかった。FL/FL-1 関数で使用される鍵値によっては、全体がバイト単位での処理のみになってしまうことからも、より詳細に byte-oriented な評価を続けた方がよいであろう。

1.2 定義本報告書では以下の記述を用いる。その他、特に注意書きのない限り Camellia の暗号技
術仕様書([CAMELLIA_s])の記述に従うものとする。
Δx: x からの差分値

Prob{a=b}: a=b の成立確率

1

2 差分解読、線形解読
Camellia の設計方針や、Camellia の明快な構造からも明らかなように、純粋な差分/線形
解読への耐性は十分あると予想できる。
そこで、差分/線形解読に対する評価は行わず、その他の評価を行った。

3 バイト多項式による解析
P 関数は実装効率性の観点から排他的論理和のみで構成され、また差分攻撃や線形攻撃に対する安全性の観点から分岐数が最良となるように設計されている。
P 関数は行列要素が 0 または 1 のみの 8 行 8 列の行列として表現できる。
z’8

0 1 1 1 1 0 0 1

z8

z’7

1 0 1 1 1 1 0 0

z7

z’6

1 1 0 1 0 1 1 0

z6

1 1 1 0 0 0 1 1

z5

0 1 1 1 1 1 1 0

z4

z’3

1 0 1 1 0 1 1 1

z3

z’2

1 1 0 1 1 0 1 1

z2

z’1

1 1 1 0 1 1 0 1

z1

z’5
z’4

＝

P 関数の逆行列も同様に表現できる。
z8

1 1 1 0 1 0 0 1

z’8

z7

0 1 1 1 1 1 0 0

z’7

z6

1 0 1 1 0 1 1 0

z’6

1 1 0 1 0 0 1 1

z’5

0 1 1 1 0 1 1 1

z’4

z3

1 0 1 1 1 0 1 1

z’3

z2

1 1 0 1 1 1 0 1

z’2

z1

1 1 1 0 1 1 1 0

z’1

z5
z4

＝

P 関数の逆行列より以下の式が成立する。
z1 = z’2 ⊕ z’3 ⊕ z’4 ⊕ z’6 ⊕ z’7 ⊕ z’8
z2 = z’1 ⊕ z’3 ⊕ z’4 ⊕ z’5 ⊕ z’7 ⊕ z’8
z3 = z’1 ⊕ z’2 ⊕ z’4 ⊕ z’5 ⊕ z’6 ⊕ z’82

z4 = z’1 ⊕ z’2 ⊕ z’3 ⊕ z’5 ⊕ z’6 ⊕ z’7
z5 = z’1 ⊕ z’2 ⊕ z’5 ⊕ z’7 ⊕ z’8
z6 = z’2 ⊕ z’3 ⊕ z’5 ⊕ z’6 ⊕ z’8
z7 = z’3 ⊕ z’4 ⊕ z’5 ⊕ z’6 ⊕ z’7
z8 = z’1 ⊕ z’4 ⊕ z’6 ⊕ z’7 ⊕ z’8
これらの式より、ラウンド関数の出力 5〜6 バイトの排他的論理和はラウンド関数の入力 1
バイトと対応する副鍵 1 バイトで表現できるという性質がある(以降バイト多項式と呼ぶ)。
例えば入力 x1 の 1 バイトについてみると、
s1(x1 ⊕ k1) = z’2 ⊕ z’3 ⊕ z’4 ⊕ z’6 ⊕ z’7 ⊕ z’8となり、他の入力バイトについても同様に表現できる。
このバイト多項式を利用して、FL 関数と FL-1 関数を除いた変形 Camellia5 段について以下に示す 2 つの手法を適用する。
これらの手法は、バイト多項式を利用した最も単純な攻撃の例である。これを利用して解読に発展できる可能性がある。

3.1 手法1
手法1
バイト多項式は排他的論理和のみで構成されているため、差分についても同様なことがいえる。つまり、以下の式が成立する。
Δz1 = Δz’2 ⊕ Δz’3 ⊕ Δz’4 ⊕ Δz’6 ⊕ Δz’7 ⊕ Δz’8
Δz2 = Δz’1 ⊕ Δz’3 ⊕ Δz’4 ⊕ Δz’5 ⊕ Δz’7 ⊕ Δz’8
Δz3 = Δz’1 ⊕ Δz’2 ⊕ Δz’4 ⊕ Δz’5 ⊕ Δz’6 ⊕ Δz’8
Δz4 = Δz’1 ⊕ Δz’2 ⊕ Δz’3 ⊕ Δz’5 ⊕ Δz’6 ⊕ Δz’7
Δz5 = Δz’1 ⊕ Δz’2 ⊕ Δz’5 ⊕ Δz’7 ⊕ Δz’8
Δz6 = Δz’2 ⊕ Δz’3 ⊕ Δz’5 ⊕ Δz’6 ⊕ Δz’8
Δz7 = Δz’3 ⊕ Δz’4 ⊕ Δz’5 ⊕ Δz’6 ⊕ Δz’7
Δz8 = Δz’1 ⊕ Δz’4 ⊕ Δz’6 ⊕ Δz’7 ⊕ Δz’8
上記 8 つの式のうちどの式を利用しても良いが、攻撃例として最下位バイトの式(1)を使用することにする。
[攻撃に利用した式]
Δz8 = Δz’1 ⊕ Δz’4 ⊕ Δz’6 ⊕ Δz’7 ⊕ Δz’8

･････

(1)

攻撃概要図を図 3.1 に示す。
図 3.1 より、5 段で式(2)が確率 1 で成立する。
[5 段で成立する式](Δx09⊕Δx012⊕Δx014⊕Δx015⊕Δx016) ⊕ (Δz1’1⊕Δz1’4⊕Δz1’6⊕Δz1’7⊕Δz1’8)⊕ (Δz3’1⊕Δz3’4⊕Δz3’6⊕Δz3’7⊕Δz3’8) ⊕ (Δz5’1⊕Δz5’4⊕Δz5’6⊕Δz5’7⊕Δz5’8)= Δx59⊕Δx512⊕Δx514⊕Δx515⊕Δx516

3

･････

(2)

入力のバイト差分として(3)の差分を与える。
(Δx01,Δx02,Δx03,Δx04,Δx05,Δx06,Δx07,Δx08),(Δx09,Δx010,Δx011,Δx012,Δx013,Δx014,Δx015,Δx016)= (0,0,0,0,0,0,0,0),(0,1,1,0,0,0,0,1)

･････

(3)

Δx010,Δx011,Δx016 のうち少なくとも 1 バイトに差分があれば良い。
このようなバイト差分を与えると 1 段目ラウンド関数のΔz1’8 は 0 となる。さらに式(4)より z22,z23,z28 に差分を与えても、2 段目ラウンド関数出力Δz2’8 は 0 となるため、3 段目の入力差分Δx38 を 0 とすることができる。
Δz2’8 =Δz21 ⊕ Δz24 ⊕ Δz25 ⊕ Δz26 ⊕ Δz27

･････

(4)

このことから、5 段で成立する式(2)は式(5)のように変形できる。
[手法 1 の式]
Δs1(Δx58) = (Δx09⊕Δx012⊕Δx014⊕Δx015⊕Δx016)⊕ (Δx59⊕Δx512⊕Δx514⊕Δx515⊕Δx516)

成立確率 1･････(5)

式(5)において、置換表 s1 の入力差分と出力差分が既知となり、s1 のすべての入出力差分とそのときの入力対の表(差分表)を用いて、5 段目の副鍵 1 バイト k58 を 2 組の選択平文でほぼ 100%の確率で求めることができる(Δx58=0 の場合は 3 組必要)。

Δx01,…,Δx08=(0,…,0)Δ=0Δz2’8=0

Δx38=0Δx09,…,Δx016=(0,1,1,0,0,0,0,1) ←バイト差分
バイト差分
いずれのバイト差分でもよい
Δ=0

Δz1’1 Δz1’4 Δz1’6= Δs1(Δx18) = 0

F1

Δz1’7

Δz1’8

Δz3’8

Δ= (0,1,1,0,0,0,0,1)
F2

F3

z3’

Δz3’1 Δz3’4 Δz3’6=Δs1(Δx38) = 0

Δz3’7

z5’

Δz5’1 Δz5’4
=Δ
Δs1(Δ
Δx58)

Δz5’7

F4

x5

Δx51,…, Δx58

F5

Δz5’6

Δz5’8

Δx59,…, Δx516

図 3.1 FL 関数と FL-1 関数を除いた変形 Camellia5 段への手法 1 の適用

4

3.2 手法2
手法2
8 つのバイト多項式のうちどの式を利用しても良いが、攻撃例として最下位バイトの式(6)を使用することにする。
[攻撃に利用した式]
z8 = z’1 ⊕ z’4 ⊕ z’6 ⊕ z’7 ⊕ z’8

･････

(6)

攻撃概要図を図 3.2 に示す。
図 3.2 より 1,3,5 段目のラウンド関数において、以下の式(7)が確率 1 で成立する。
s1(x18 ⊕ k18) = z1’1 ⊕ z1’4 ⊕ z1’6 ⊕ z1’7 ⊕ z1’8
s1(x38 ⊕ k38) = z3’1 ⊕ z3’4 ⊕ z3’6 ⊕ z3’7 ⊕ z3’8

･････

(7)

s1(x58 ⊕ k58) = z5’1 ⊕ z5’4 ⊕ z5’6 ⊕ z5’7 ⊕ z5’8
5 段で成立する式(8)に(7)を代入すると、式(9)となる。
[5 段で成立する式](x09 ⊕ x012 ⊕ x014 ⊕ x015 ⊕ x016) ⊕ (z1’1 ⊕ z1’4 ⊕ z1’6 ⊕ z1’7 ⊕ z1’8)⊕ (z3’1 ⊕ z3’4 ⊕ z3’6 ⊕ z3’7 ⊕ z3’8) ⊕ (z5’1 ⊕ z5’4 ⊕ z5’6 ⊕ z5’7 ⊕ z5’8)= x59 ⊕ x512 ⊕ x514 ⊕ x515 ⊕ x516

･････

(8)

(x09 ⊕ x012 ⊕ x014 ⊕ x015 ⊕ x016) ⊕ s1(x18 ⊕ k18) ⊕ s1(x38 ⊕ k38) ⊕ s1(x58 ⊕ k58)
= x59 ⊕ x512 ⊕ x514 ⊕ x515 ⊕ x516

･････

(9)

ここで、「x18 , x38 = 定数」となるように平文を与えれば、s1(x18 ⊕ k18) ⊕ s1(x38 ⊕ k38)が定数となり式(10)となる。
[手法 2 の式]
s1(x58 ⊕ k58) = (x09 ⊕ x012 ⊕ x014 ⊕ x015 ⊕ x016)⊕ (x59 ⊕ x512 ⊕ x514 ⊕ x515 ⊕ x516) ⊕ 定数

成立確率 1･････(10)

平文に式(11)のようなバイト差分を与えた時に「x18 , x38 = 定数」となる。
(Δx01,Δx02,Δx03,Δx04,Δx05,Δx06,Δx07,Δx08),(Δx09,Δx010,Δx011,Δx012,Δx013,Δx014,Δx015,Δx016)= (0,0,0,0,0,0,0,0),(0,1,1,0,0,0,0,1)

･････

(11)

Δx010,Δx011,Δx016 のうち少なくとも 1 バイトに差分があれば良い。
手法 2 の式(10)を使って、1 文目で定数と鍵 k58 の組が 256 組求まり、2 文目でその 256組に対して手法 2 の式(10)が成立するかを確認する。成立したときの鍵 k58 が求めたい鍵である。
これより、5 段目の副鍵 1 バイト k58 は選択平文 2 文で求めることが可能である(鍵を 1 つに絞り込めないこともあるため、
もう 1 文で確認するとほぼ 100％の確率で鍵 k58 が求まる)。

5

3.1 節の手法 1 では、1 組の選択平文対(2 文)では 1 バイトの鍵を 1 つに絞り込むことはできないが、手法 2 では選択平文 2 文で鍵を 1 つに絞り込めることがある。よって、手法 2 のほうが若干ではあるが効率が良い。

x01,…,x08

x09,…,x016

F1

定数z1’6 z1’7
z1’1 z1’4= s1(x18+k18) = 定数

z1’8

z3’

z3’1 z3’4 z3’6 z3’7
=s1(x38+k38) = 定数

z3’8

z5’

z5’1 z5’4 z5’6
=s1(x58+k58)

z5’8

z2’8=定数F2x38=定数

F3

F4

x5

F5

x51,…, x58

z5’7

x59,…, x516

図 3.2 FL 関数と FL-1 関数を除いた変形 Camellia5 段への手法 2 の適用

4 BOOMERANG 攻撃
Camellia に Boomerang 攻撃が適用できるかどうかを検討した。以下に FL 関数と FL-1関数を除いた変形 Camellia6 段解読のステップを示す。以下の解読法は、k2(F 関数の入力
x2 に排他的論理和する鍵)を推定する例である。差分を変えることにより、k1 から k8 まで推定することが出来る。
<step.0>まず図 4.1 のように入力する選択平文を P,P'とし、それらに対応する暗号文をC,C'とする。また選択暗号文 D,D'に対応する平文を Q,Q'とする。
<step.1> P と P'の差分ΔP0 = 0a000000 0xxxxx00 となるような入力を選ぶ。このとき暗号化の過程で、ラウンド関数 3 段通過後の差分ΔP3 = 0sssss00 0a000000 がある
確率で成立する。ここで a はある任意の値を意味する。また x はラウンド関数 1
段通過後の差分ΔP1 = 00000000 0a000000 となるような値を選ぶ。s は置換表
s2 で入力差分 a を入れた時に、取り得る差分の一つである。
<step.2> C との差分ΔC0 が 0A000000 0XXXXX00 となるような D、また C’との差分Δ
C’0 が 0A000000 0YYYYY00 となるような D’を選ぶ。ここで X と Y は 6 段目の

6

F 関数の k2 を仮定し、ΔC1 = ΔC'1 = 0A000000 00000000 となるような値を選ぶ。また A はΔP で与える入力差分 a が置換表 s2 を通過した時に出力差分として取り得るものとし、その中で出現確率が高いものを選ぶことによってBoomerang 攻撃が成立する確率が大きくなる。このとき復号過程で、ラウンド関数 3 段通過後の差分ΔC3 = 0A000000 0SSSSS00、ΔC’3 = 0A000000
0TTTTT00 がそれぞれある確率で成立する。S と T は置換表 s2 に入力差分 A を入れた時に取りうる差分の一つである。
<step.3>Q と Q'の差分ΔQ を調べる。ΔQ0= 0a000000 0yyyyy00 となっていれば、高い確率で、図 4.1 のような状態になっていると考えられる。ここで y はラウンド関
数 1 段通過後の差分ΔQ1 = 00000000 0a000000 となるような値である。このよ
うな状態の成立確率 Pb は
Pb = Prob{ΔP1 = 00000000 0a000000}
×Prob{ΔC1 = ΔC’1 = 0a000000 00000000}
×Prob{ΔC3 ⊕ ΔC’3 ⊕ ΔP3 = 0sssss00 0a000000}
×Prob{ΔQ3→ΔQ1｜ΔQ3 = 0sssss00 0a000000,
ΔQ1 = 00000000 0a000000}= 2-7 × 2-7 × 2-1 × 2-6 × 2-7 = 2-28
この値は、偶然にΔQ0 = 0a000000 0yyyyy00 となる場合に比べて非常に大きい
ので、区別可能である。
<step.4>1 段目と 6 段目について、その入力値がわかり置換表 s2 について入力差分と出力差分がわかるので、その置換表とセットになっている鍵 8 ビットずつは 2 つの候補に絞れる。残った候補について、ΔP0 の a を代えて同じことを繰り返せば鍵は１つずつに絞ることが出来る。
以上により選択平文/選択暗号文 230 程度で、FL 関数と FL-1 関数を除いた変形 Camellia6段に対して Boomerang 攻撃による鍵の推定が可能である。
次に、6 段の Boomerang 攻撃を用いて、8 段に拡張する場合を検討した。1 段暗号化後の差分が 0a000000 0xxxxx00 となるように、1 段目の鍵 5 バイトを仮定し、差分が 0xxxxx00
efghijkl であるような、平文 P と P'を与える。また、暗号文側も同様に 8 段目の鍵 5 バイトを仮定し、1 段復号後の C,C’の差分がそれぞれ 0A000000 0XXXXX00,0A000000 0YYYYY00となるように暗号文 D と D'を選ぶ。
この時、攻撃が成立する確率は、2-108( = 2-40 × 2-40 × 2-28) である。つまり、データ量
2110 程度で、1 段目の鍵 5 バイト、2 段目の鍵 1 バイト、7 段目の鍵 1 バイト、8 段目の鍵 5
バイトを推定することが可能であると考えられる。
9 段以上については、Boomerang 攻撃による有効な方法は見つからなかった。

7

ΔQ0

Q’
バイト差分値

P’

Q

F1

ΔP0

F1

F1

F2

F2

P

F3

F1

③

ΔQ3

F3

①
F2

F2
F4

F3

F4

ΔC’3

F3

ΔC3

F5

F4

ΔP3

F5

F6

F5

②
F6

F4

F6

D’

F5

D

ΔC’0

F6

ΔC0

C

C’

図 4.1 FL 関数と FL-1 関数を除いた変形 Camellia6 段への Boomerang 攻撃の適用

5 SQUARE 攻撃
Camellia のラウンド関数は全単射関数である。全単射な関数は、入力が全通り与えられると、出力の総和は 0 になる(バランスしている)。このことから図 5.1 のような Feistel 型暗号について、次のステップを行うことで 6 段程度の場合、鍵の推定が可能になることを示す。
1.

x が取りうる全ての値となるように、PR を総当たりする。PL は固定する。x をすべて排他的論理和すると 0 になる。つまり、バランスしている。

2.

全単射な関数 F2 の出力である y の値は全ての値を取る。

3.

y'も同様に全ての値を取るので、z も全ての値となっている。

4.

x と z はそれぞれに全ての値を取っているので、z'はバランスしている。

5.

ここで、F5 と F6 の鍵を仮定し a を求める。

6.

鍵の仮定が正しければ a と CR を排他的論理和した値もバランスしているはずである。
バランスしていなければ、仮定した鍵は棄却できる。

以上により全単射なラウンド関数を持つ Feistel 型暗号は 6 段で鍵の推定が可能であることがわかる。しかし、ステップ 5 での鍵の仮定量が秘密鍵長よりも大きければ有効な解読手法とは言えない。

8

ここで Camellia のラウンド関数を考えてみる。Camellia のラウンド関数の場合、P 関数の仕様によりステップ 1 の総当りをあるバイトについてのみ行う。つまり、256 通りの値を与える。ステップ 2 で影響が波及するバイトは 5〜6 バイトしかない。ステップ 3 で初めて全バイトに影響が波及することになるが、各バイトにおいてはそれぞれバランスしている。
ステップ 6 でチェックを 1 バイトについてのみ行うとすれば、ステップ 5 で仮定が必要になる鍵量は最小の場合 13 バイトである。
これは Camellia の秘密鍵長 128 ビットよりも短いため、この解析手法は Camellia のラウンド関数に置き換えても有効であると言えるだろう。
この場合、鍵候補として残る数を約 1/28 と見積もると、鍵の推定のためには 2104 程度の平文対が必要になるため、FL 関数と FL-1 関数を除いた変形 Camellia6 段は選択平文 2104、
計算量 2112 程度で副鍵の一部が推定可能となるだろう。

図 5.1 Feistel 型暗号

6 丸め差分攻撃
丸め差分攻撃はバイト単位で処理する暗号に適用される攻撃法である。Camellia は E2 と同様にラウンド関数はバイト単位で処理されている。E2 は[MT99]で 7 段のバイト差分特性が発見されている。Camellia は E2 からの改善を図っていると思われるが、変更点の 1 つである置換表に対する「4 つの異なる置換表を作ることによって、丸め差分攻撃[MT99]に対する安全性が多少改善される」という自己評価書 2.3 節の記述に関して検討した。
[MT99]では以下の特性確率 P(Δx,Δy)において、P(Δx,Δy) = Prob{ s(x) ⊕ s(x ⊕ Δx) = s(y) ⊕ s(y ⊕ Δy) }9Δx≠Δy の場合には、平均 2-8 となるが、Δx=Δy の場合には、大きな値になるという特性を用いている。s1 と s4 は入力を巡回シフトしている関係にあるので、本特性はΔx=(Δy<<<1)の場合に成立する。このことにより、s4 は丸め差分攻撃[MT99]に対する安全性改善には寄与していないことになる。s2 および s3 は、s1 の出力を 1 ビット左および右巡回シフトした関係にある。これは、[MT99]の第 4 節で用いられている事実(Δx=Δy の条件のもとでは、 P(Δ
丸め差分攻撃に対する安全性改善に寄与していx,Δy)は 2-8 よりも大きくなる)には該当せず、ると言える。
丸め差分解読に対する強度は P 層に依存するが、もし丸め差分解読に対する安全性改善を
置換表のみに頼るのであれば、s4 の代わりに s1(x)<<<2 を用いることも選択肢の一つであろう。

7 高階差分攻撃
高階差分攻撃は暗号器を平文全ビットのブール式で表現した場合、代数次数が低い場合やブール式の項が疎な場合、解読が可能になることがある。
Camellia のラウンド関数において、代数次数を上げる働きをするものは置換表のみである。
そこで、置換表 s1 について、ブール式で表現したときの次数と項数の調査を実施した。結果を表 7.1 に示す。
また、置換表 s2,s3 は s1 の出力を単純に 1 ビット巡回シフトしたものであり、また、置換
表 s4 は s1 の入力を 1 ビット巡回シフトしたものであるため、ブール式としての次数と項数は同じである。
表 7.1 より、4 種の置換表の最高次数は全出力ビット 7 次であり、項数も取り得る項数の半分程度存在する(疎ではない)ことが確認できた。
さらに、次数や項数は置換表を通過するたびにはじめは急激に増加すると期待できる。例
3 回通過すると次数は 73 になる。
よって、
Camellia
えば、
2 回の置換表を通過すると次数は 72、は高階差分攻撃に対して安全であると期待できる。
表 7.1 置換表 s1 の次数と項数
ビット番号

1次

2次

3次

4次

5次

6次

7次

8次

1

6

11

23

38

27

18

4

0

2

7

16

24

39

28

9

8

0

3

3

17

28

35

28

11

3

0

4

7

13

27

39

33

11

4

0

5

3

17

26

36

32

12

3

0

6

3

14

36

34

26

15

5

0

7

6

14

29

36

23

14

7

0

8

3

15

31

36

23

15

3

0

10

取り得る項数を表 7.2 に示す。
表 7.2 取り得る項数
1次

2次

3次

4次

5次

6次

7次

8次

8

28

56

70

56

28

8

0

8 補間攻撃補間攻撃はラウンド関数などの暗号化関数が適当な代数系の上で単純な式で表現できるときに有効な攻撃法である。Camellia のラウンド関数は副鍵の排他的論理和と置換表を利用した S 関数、排他的論理和のみの P 関数により構成されている。また、ラウンド関数はバイト単位でのみ処理されている。
そこで、まず適当な代数系としてガロア体 GF(28)を選択し、置換表が単純な式で表現できるか検討した。
すべての 8 次の既約多項式(30 式)から構成したガロア体 GF(28)上で、4 種の置換表の項数と最高次数を調査した。結果を表 8.1 に示す。取り得る最大項数は 255、最大次数は 254 である。
補間攻撃が可能になるには、置換表の最高次数が低い場合や項数が少ない場合である。表8.1 から明らかなように Camellia の置換表はガロア体 GF(28)上での式が複雑であり、ガロ
ア体 GF(28)上での補間攻撃に対しては安全であると思われる。
表 8.1 置換表の GF(28)上での多項式表現
置換表

項数

最高次数

s1

250〜255

すべて 254s2

251〜255

すべて 254s3

252〜255

すべて 254s4

252〜255

すべて 254

置換表はハードウェアの小型設計が可能となるように GF(28)上の要素は部分体 GF(24)上の多項式としても表現可能なように設計されている。そこで次に部分体 GF(24)上でも検討した。部分体 GF(24)を構成するための既約多項式は、g 関数で使用している x4+x＋1 を使用した。置換表 s1 は以下の式になる。
s1(x) = h( g( f( 0xc5 ⊕ x ) ) ) ⊕ 0x6e[f 関数] Y = f(X)X = x0‖x1, Y= y0‖y1 とすると、
y0 = b・x0 ⊕ 7・x02 ⊕ c・x08 ⊕ a・x1 ⊕ c・x12 ⊕ f・x14 ⊕ a・x18
y1 = 7・x0 ⊕ e・x02 ⊕ 9・x04 ⊕ 9・x08 ⊕ x1 ⊕ 2・x12 ⊕ 6・x14 ⊕ 7・x18 (係数は 16 進)

11[g 関数] Y = g(X)X = x0‖x1, Y= y0‖y1 とすると、
y0 = (x0 ⊕ f1・x1) / (x0(x0 ⊕ f1・x1) ⊕ f0・x12)
y1 = (x1) / (x0(x0 ⊕ f1・x1) ⊕ f0・x12)(ここで f0=9, f1=1)[h 関数] Y = h(X)X = x0‖x1, Y= y0‖y1 とすると、
y0 = 8・x0 ⊕ 8・x02 ⊕ b・x04 ⊕ 9・x08 ⊕ 2・x1 ⊕ 6・x12 ⊕ b・x14 ⊕ e・x18
y1 = 4・x0 ⊕ e・x02 ⊕ d・x04 ⊕ 7・x08 ⊕ 4・x1 ⊕ c・x12 ⊕ 2・x14 ⊕ e・x18 (係数は 16 進)
これより、g 関数の y0, y1 の分母が同じ式をしていることがわかる。有理式による補間攻撃を考えた場合、分母が共通であることがやや気にはなるが、2 回のアフィン変換を g 関数の前後で実行することにより、部分体 GF(24)上での有理式が複雑になり、部分体 GF(24)上での有理式を用いた補間攻撃に対しては安全になっていると思われる。
また、入出力を GF(24)の元 2 個とみなし、出力が入力のどのような多項式として表されるかを調査した。結果を表 8.2 に示す。
すべての 4 次の既約多項式(3 式)から構成したガロア体 GF(24)上での 4 種の置換表の項数は以下の通りである。取り得る最大項数は 255 である。出力=y0‖y1 とする。
表 8.2 より明らかなように Camellia の置換表は部分体 GF(24)上での式が複雑であり、部分体 GF(24)上での補間攻撃に対しては安全であると思われる。
表 8.2 置換表の部分体 GF(24)上での多項式表現
置換表

y0 の項数y1 の項数s1

237〜245238〜245s2

234〜236238〜245s3

237〜238232〜246s4

241〜243

235〜2429 鍵生成部の特性
Camellia の鍵生成部には以下のような特性がある。第 3 章で述べたように、ラウンド関
数の入出力間には
s1(x8 ⊕ k8) = z1 ⊕ z4 ⊕ z6 ⊕ z7 ⊕ z8という関係式が成り立つ。鍵生成部の場合、ラウンド関数での副鍵の挿入に相当するものとして定数Σが挿入されているので、上記関係式は
s1(x8) = z1 ⊕ z4 ⊕ z6 ⊕ z7 ⊕ z8と書き換えられる。
また秘密鍵 128 ビットの場合の鍵生成部は図 9.1 のように等価変形可能である。そこで、
KAR の 8 バイト目と KAL の 1,4,6,7,8 バイト目が求まっているとすると、F4 の出力５バイトの排他的論理和( z1 ⊕ z4 ⊕ z6 ⊕ z7 ⊕ z8 )が求まる。よって、F2 の入力 1 バイトも求まる。
12

さらに、
KLL の 5 バイトが求まっていると、
1 段目の F の出力 1 バイトを計算できるので、KLR の 1 バイトが求まる。
これはラウンド関数の入力バイトいずれに対しても言える特性である。すなわち、KA の６,７バイトと KLL の５,６バイトから KLR の１バイトを求めることができる。しかし、この特性は Camellia の鍵生成部を解読可能にするような特性ではないだろう。

図 9.1 Camellia 鍵生成部(秘密鍵長 128 ビット)等価変換

10 弱鍵
Camellia に弱鍵が存在するかどうかを検討してみた。鍵生成部の構造上、秘密鍵を副鍵としてそのまま使用している段があるため全ての段が同じ鍵となるような等価鍵は明らかに存在しない。また副鍵に使用する場合のローテイト数も各段で異なるため、スライド攻撃や鍵関連攻撃に利用できるような繰り返す鍵も存在しないであろう。

11 その他
S 関数において、(s1,s2,s3,s4,s2,s3,s4,s1)という置換表の並びを選択した基準が不明である。

13

12 まとめ
今回 Camellia を評価した範囲では、安全性に関して特に問題はみつからなかった。
いくつかの攻撃を試行した範囲では、FL/FL-1 関数を除いた変形 Camellia 8 段が、秘密鍵
総当たりより少ない計算量で鍵を推定することが可能であろうという結果になった。仕様通りの Camellia では、18 段(鍵長 128 ビット)もしくは 24 段(鍵長 192/256 ビット)なので、直接脅威となることはないと考えられる。また鍵生成部の構造より、秘密鍵 5 バイトと中間鍵
6 バイトから、不明な秘密鍵 1 バイトを計算できる場合が存在する。
ラウンド関数がバイト単位の処理のみで構成されており、FL/FL-1 関数で使用される鍵によっては、全体がバイト単位での処理のみになってしまうところが少々気になる。構造的に、より詳細に byte-oriented な評価を続けた方がよいであろう。
ラウンド関数が簡単な構造なので、ラウンド関数を推定する際に必要な鍵量が少ない点が解読者には有利である。
全体的には、評価した範囲では Camellia は安全であるという結論に達した。

14

A 参考文献[CAMELLIA_s] http://info.isl.ntt.co.jp/camellia/index-j.html 暗号技術仕様書[和文].
[CAMELLIA_e] http://info.isl.ntt.co.jp/camellia/index-j.html 自己評価書[和文].
[A00] K.Aoki, "Practical Evaluation of Security against Generalized Interpolation
Attack," IEICE Vol.E83-A,No1,pp.33-38, 2000.
[BW00]

A.Biryukov,D.Wagner,"Advanced

Slide

Attacks,"

EUROCRYPT2000,

LNCS1807, pp.589-606, Springer-Verlag, 2000.
[CV95] F. Chabaud and S. Vaudenay, "Links Between Differential and Linear
Cryptanalysis," EUROCRYPT'94, LNCS950, pp.356-365, Springer-Verlag, 1995.
[DKR97] J.Daemen, L.Knudsen, V.Rijmen, "The Block Cipher SQUARE," FSE'97,
LNCS 1267, pp.149-165, 1997.
[K00] http://info.isl.ntt.co.jp/camellia/index-j.html Knudsen の評価報告書 (Analysis ofCamellia).
[M94] M.Matsui, "On Correlation Between the Order of S-boxes and the Strength of
DES," EUROCRYPT'94, LNCS950, pp.366-375, 1994.
[MSAK99] S.Moriai,M.Sugita,K.Aoki,M.Kanda, "Security of E2 against TruncatedDifferential Cryptanalysis," SAC'99 pp.106-117, 2000.
[MT99] M.Matsui,T.Tokita, "Cryptanalysis of a Reduced Version of the Block Cipher
E2," FSE'99 LNCS 1636,pp.71-80.
[W99] D.Wagner, "The Boomerang Attack," FSE'99, LNCS 1636, pp.156-170, 1999.
[Y00] http://info.isl.ntt.co.jp/camellia/index-j.html Yiqun の評価報告書 (A Note on the
Block Cipher Camellia).

15