CIPHERUNICORN-A に使われる関数の高階差分攻撃耐性評価

概要
この文書は、電子政府において利用可能な暗号技術のリスト作成のための詳細評
価の一環として、CIPHERUNICORN-A 暗号の高階差分攻撃耐性をその技術仕様書[2]、及び自己評価書 [3] をもとに評価したものである。

1

CIPHERUNICOEN-A の構造

CIPHERUNICORN-A はデータブロック長 128bit、鍵長 128、192、256bit のいずれかを利用できる DES 型暗号で、AES 互換暗号として位置づけられる。CIPHERUNICORN-A
データ撹拌部は DES 暗号などと同じ Feistel 構造を基本とし段数は 16 段構成である。初期/終期処理では、拡大鍵の加算/減算のみを行なう。また、鍵スケジューラは、与えられた秘密鍵から 72 個の拡大鍵を生成する。
全体構造の概略を図 1〜6 に示す。詳細は参考文献 [2] を参照頂きたい。

2

各関数の形式的な代数次数の評価

2.1

A3 関数64bit の入力データを指定したシフト数だけ巡回シフトした後、3 つのデータの排他的論理和を求め出力する。
Y = (X <<< const0 ) ⊕ (X <<< const1) ⊕ (X <<< const2)
const0 = 0, const1 = 23, const2 = 41
巡回シフトと排他的論理和によって構成されるこの関数はでは次数の上昇はなく 1 次であるが、3 つのシフトの排他的論理輪であるため各出力 bit の項数が最大で 3 倍に増える可能性が考えられる。64bit の上位 32bit に対して下位 32bit の全ての bit が影響し、また下位の 32bit に上位 32bit の全ての bit が影響することや、シフト回数が byte 単位ではないことなどから、出力後の各 bit の項は (次数は上昇しないが)64bit 幅で効果的に攪拌されるということが言える。

1

2.2

定数乗算関数

32bit 入力データに対して定数を乗算し、出力結果とする。
Y = X ⊗ constn, n = 0, 1
const0 = 0x7e167289, const1 = 0xf e21464b
const0 を 2 進数で表すと、const0 = 01111110000101100111001010001001
であり、下位 0〜3bit 目は次数が上昇がなく 1 次であるが、4bit 目は 2 次、5bit 目は 3 次、6bit 目は 4 次、7bit 目は 6 次、8bit 目以降は nbit 目で最大 n 次と次数が上昇する。(表 2上)同様に const1 を 2 進数で表すとconst1 = 11111110001000010100011001001011
であり、下位 0〜1bit 目は次数が上昇がなく 1 次であるが、2bit 目は 2 次、3bit 目は 3 次、4bit 目は 4 次、5bit 目で 5 次、nbit 目で最大 n 次と次数が上昇する。(表 1 下)

表 1: 定数乗算関数の代数次数
Y (const0 )出力 bit次数

出力 bit次数2.3y3131y3131・・・ yn・・・ y8・・・・・・n・・・ yn・・・ny76y64y53y42y3
1y2
1y1
1y01Y (const1 )・・・ y8 y7 y6・・・ 876y55y44y33y22y1
1y0
18Tn 関数 [図 1]32bit 入出力。入力を 1byte ごとに区切り、入力番号に対応する 1byte を換字テーブルの入力値とする。換字テーブルは 8bit 入力、8bit 出力であり、CIPHERUNICORN-E で使用した 4 種類を使用する。
Y = S0 (Xn )  S1 (Xn )  S2 (Xn )  S3 (Xn )Tn 関数の次数は Tn 関数の内部で使用される換字テーブルの次数より 7 次である。
(換字テーブルに関する調査は 3 節参照)
2

2.4

F 関数 [図 2]

F 関数は、本流と 1 次鍵生成部から構成される。本流では入力データ 64bit と拡大鍵を加算し、A3 関数、定数乗算、Tn 関数を実行する。1 次鍵生成部では、拡大鍵と入力デー
タ 64bit を加算し、乗算定数、Tn 関数を通過後、1 次鍵を取り出す。1 次鍵を本流のデータ攪拌に使用し、出力データ 64bit を生成する。本流、1 次鍵生成部、両方において Tn 関数の 3 段の通過により形式的次数は bit 幅より大きくなるため、64 次となる。

2.5

MT 関数 [図 3]

入力データ 64bit の上位 32bit (X0 ) と定数 const との乗算後、T0 関数の入力とする。T0関数の出力を入力データの下位 32bit(X1 ) と排他的論理和し、出力とする。

Y= Y0  Y1

Y0 = (X0 ⊗ const)
Y1 = X1 ⊕ T0 (Y0 )const = 0x01010101= 00000001000000010000000100000001(binary)
出力データ Y の上位 32bit の次数は定数 const を乗算するため、定数乗算後の出力 Y0 は、下位 0〜8bit 目までは 1 次であり、9bit 目が 2 次、10bit 目が 3 次、11bit 目が 4 次、12bit目が 6 次、13bit 目が 8 次、14bit 目が 10 次、・・・、と次数が上昇する。下位 32bitY1 は定数乗算後 T0 関数を通過するため Y0 に T 関数の 7 次を乗算した分の次数が上昇することになるとなる。各 bit の次数を表 2 に示す。
表 2: MT 関数出力の代数次数

出力 bit次数
出力 bit次数

出力 bit次数出力 bit
次数y1512y1410y31
31y1532y31
32

y138y126y114Y0y9 y8
2
1y103・・・

y1332

y1232

y6
1ynn・・・y14
32

y7
1y1128Y1
y9 y8
14 7y1021yn
32・・・・・・

3y5
1y4
1y3
1・・・・・・

y7
7y6
7y5
7y4
7・・・・・
・

y3
7y2
1y1
1y0
1

y18
18

y17
16

y16
14y2
7y1
7y0
7y18
32

y17
32

y1632

2.6

各関数の形式的な代数次数の評価のまとめ

F 関数は、A3 関数で各 byte にまたがって攪拌された後、T 関数 (換字テーブル) を 9 回〜10 回通過するため１段でも 64 次に近い十分大きな次数と推定され、16 段で構成される
CIPHERUNICORN-A は十分な代数的強度が期待される。

3

換字テーブルについての諸評価

CIPHERUNICOEN-A で使用される換字テーブルは 8bit 入力、8bit 出力であり、
CIPHERUNICORN-E で使用した 4 種類と同じものが使用される。この換字テーブル (S0〜S7 ) について諸評価を行なった。

3.1

最大差分確率 DP

換字テーブルの最大差分確率は、S0 〜S3 のいずれについても 2−6 であった。また、任意の入力差分 ∆x0 に対しても最大差分確率は 2−6 であり、逆に任意の出力差分 ∆y0 に対しても最大差分確率は 2−6 であった。このことは、最大差分確率を与える入力差分と出力差分の組み合わせに偏りがなく、差分攻撃に対する耐性が高いということを示している。

3.2

最大線形確率 LP

換字テーブルの最大線形確率は、S0 〜S3 のいずれについても 2−6 であった。差分確率の場合と同様に、任意の入力マスク Γx0 に対しての最大差分確率も 2−6 であり、逆に任意の出力マスク Γy0 に対しても最大差分確率は 2−6 であった。このことは、最大線形確率を与える入力マスクと出力マスクの組み合わせに偏りがなく、線形攻撃に対する耐性が高いということを示している。

3.3

代数次数及び項数

換字テーブル S3 〜S0 の入出力 8bit について、出力の各 bit に対するブール多項式を求め、その代数次数及び項数を求めた。その結果、代数次数は換字テーブルの全 4 種類の全ての bit について 7 次であり。その項数は、108〜141 項であり、平均的な項数が現れており、代数的攻撃に対しても高い耐性が期待される。表 3 にその結果を示す。

4

表 3: 換字テーブルのブール多項式の代数次数と項数S0
出力 bit次数項数
出力 bit次数項数
出力 bit次数項数
出力 bit次数項数3.4S077116
S177119
S277124
S377125

S06
7126

S05
7127

S04
7108

S03
7123

S02
7121

S01
7126

S00
7136

S167131S0
S15 S1477128 138

S13
7131

S127114

S117132

S107118

S267114

S2S25 S24
77139 118

S23
7121

S22
7138

S21
7141

S20
7125

S367118

S3S35 S34
77138 134

S33
7118

S32
7129

S31
7121

S30
7143

高階差分特性S3 〜S0 の換字テーブルについて高階差分値を求めた。S3 〜S0 の 4 つの全ての換字テー
ブルについて、１〜8 階差分値を計算し、常に定数となる出力ビットを探索した。その結果、5 階差分、6 階差分の一部について、あるビットが定数となった。その結果を表 4、表5 に示す。各行の左端に示されたビットを変数とする高階差分を計算したとき、表中 x は変化する出力ビット、0 または 1 は定数となる出力ビットを表す。、7 階差分値は全ての bitが入力値によらない定数値であり、さらに 8 階差分は all zero となる。これは、代数次数が７である事を表している。結果を表 6、表 7 に示す。

5

変数

x1 ,x2 ,x3 ,x4 ,x5
x1 ,x2 ,x3 ,x5 ,x7
x0 ,x3 ,x4 ,x5 ,x7
x1 ,x3 ,x4 ,x5 ,x7
x0 ,x1 ,x3 ,x6 ,x7
x0 ,x1 ,x4 ,x6 ,x7
x0 ,x1 ,x5 ,x6 ,x7
x3 ,x4 ,x5 ,x6 ,x73.5

表 4: 換字テーブルの 5 階差分値
S0
S1
S2xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxx1
xxxxxx1x
xxxxxxxx
xxxxx1xx

xxxxxxxx
x1xxxxxx
x1xxxxxx
x1xxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx

xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxx1xx
xx1xx0xx
xxxxxxxx

S3xxxxx1xx
xxxxxxxx
xxxxxxxx
xxxxxxx1xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx

補間攻撃

補間攻撃は、暗号文のある n ビットブロックを GF (2n ) の元と見なし、平文に関するGF (2n ) 上の多項式で表現したとき、その多項式 (鍵を係数とする多項式) の、未知係数の数が N であれば、N 組の平文・暗号文から、高い確率でこの多項式で復元でき,N+1 組あれば、その復元が正しいか否か高い確率で判別できることを利用して解読するものである。
換字テーブルを GF (28 ) 上の多項式で表現した時の項数を調べた結果を表 8 に示す。既約多項式について、GF (28 ) 上の多項式で表現した結果、項の数はどの原始多項式に対しても 252 以上であった。CIPHERUNICOEN-A の自己評価書 [3] では、最大項数は 255 としているが、252 は十分に大きい値であり、補間攻撃に対して安全であると期待できる。

3.6

換字テーブルについての諸評価のまとめ

換字テーブルの最大差分確率、最大線形確率は共に単射の 8bit 入出力関数としては最良の値 2−6 であり、代数次数も 7 次と、8bit 入出力の関数としては最良であり、項数も 108以上であり、この観点からは、最良の 8bit 入出力換字テーブルであると言える。

64

F 関数に対する高階差分F 関数は 64 ビット入出力であるが、計算量の関係で、について 32 階差分、31 階差分特性の調査を行なった。

4.1

31 階差分F 関数の入力 Xl (32bit) を all zero とし、Xr (32bit) 側で 全ての変数のとり方 (bit orientedで 32 通り) に対して 31 階差分を求めた。はじめに鍵スケジューラには all zero の鍵を入力し、１段目 F 関数出力の３１階差分を求めた。鍵を変えて同じく３１階差分を求めたが、固定値となるものは、見いだせなかった。

4.2

32 階差分同様に F 関数の入力 Xl (32bit) を all zero とし、Xr (32bit) 側で変数を取り 32 階差分を求めた。結果として、特徴は見いだせなかった。

4.3

F 関数に対する高階差分のまとめ

31 階差分、32 階差分により得られた値は、byte 単位でみても、= 0 でいずれも異なる値であり、法則性を見つけるにはいたらなかった。F 関数のはじめの A3 関数により byte単位でも攪拌されており、64bit の入出力である F 関数に単純に 32 階差分を適用しても解読に有利な情報は得られないと言える。

5

まとめ

CIPHERUNICORN-A で使用される各関数についての強度評価の結果、各関数に特に目立った弱点は発見できなかった。特に F 関数は、データ攪拌部に一時鍵を足しこむ形になっている上、F 関数自身が換字テーブルを使った 6 段 (一時鍵生成部)、10 段 (データ攪拌部) の Feistel 構造になっており、非常に強い関数であると考える。
今回は F 関数内部や鍵スケジューラで使われる関数を個別に調査するにとどまったが、アルゴリズム全体を評価するにあたり、F 関数全体とそれを数段組み合わせたもの、アルゴリズム全体についてなど、もう少し詳しい調査が必要である。また、CIPHERUNICORN-Aの難点といわれている、実装した際の暗号化（復号）の速度についても調査が必要であろう。

参考文献[1] Yukiyasu Tsunoo,Hiroyasu Kubo,Hiroshi Miyauchi,Katsuhiro Nakamura 「A New128-bit Block Cipher CIPHERUNICORN-A」SCIS2000-A18, 2000.
7

[2] 日本電気株式会社「暗号技術仕様書 CIPHERUNICORN-A」IPA 提出資料, 2000.
[3] 日本電気株式会社「自己評価書 CIPHERUNICORN-A」IPA 提出資料, 2000.

8図 1: Tn 関数

図 2: F 関数

9図 3: MT 関数

図 4: データ攪拌部 (暗号化)10図 5: 鍵スケジューラダミーループ (秘密鍵 128bit)

図 6: 鍵スケジューラ拡大鍵取り出し (秘密鍵 128bit)

11

変数

表 5: 換字テーブルの 6 階差分値
S0S1S2x0 ,x1 ,x2 ,x3 ,x4 ,x5
x0 ,x1 ,x2 ,x3 ,x4 ,x6
x0 ,x1 ,x2 ,x3 ,x5 ,x6
x0 ,x1 ,x2 ,x4 ,x5 ,x6
x0 ,x1 ,x3 ,x4 ,x5 ,x6
x0 ,x2 ,x3 ,x4 ,x5 ,x6
x1 ,x2 ,x3 ,x4 ,x5 ,x6
x0 ,x1 ,x2 ,x3 ,x4 ,x7
x0 ,x1 ,x2 ,x3 ,x5 ,x7
x0 ,x1 ,x2 ,x4 ,x5 ,x7
x0 ,x2 ,x3 ,x4 ,x5 ,x7
x1 ,x2 ,x3 ,x4 ,x5 ,x7
x0 ,x1 ,x2 ,x3 ,x6 ,x7
x0 ,x1 ,x2 ,x4 ,x6 ,x7
x0 ,x1 ,x3 ,x4 ,x6 ,x7
x0 ,x2 ,x3 ,x4 ,x6 ,x7
x1 ,x2 ,x3 ,x4 ,x6 ,x7
x0 ,x1 ,x2 ,x5 ,x6 ,x7
x0 ,x1 ,x3 ,x5 ,x6 ,x7
x0 ,x2 ,x3 ,x5 ,x6 ,x7
x1 ,x2 ,x3 ,x5 ,x6 ,x7
x0 ,x1 ,x4 ,x5 ,x6 ,x7
x0 ,x2 ,x4 ,x5 ,x6 ,x7
x0 ,x3 ,x4 ,x5 ,x6 ,x7
x1 ,x2 ,x4 ,x5 ,x6 ,x7
x0 ,x3 ,x4 ,x5 ,x6 ,x7
x1 ,x3 ,x4 ,x5 ,x6 ,x7
x2 ,x3 ,x4 ,x5 ,x6 ,x7

xxxxxxx1
xxxxxxxx
xxxx0xx1
1xxx1xxx
xxxx0xx1
0xxx0xx1
1xxx1xxx
xxxxx1x1xxxxxxxx
xxxxx1x1
xxxxx1x1
xxxxx1xx
xx0xx1x0
x01xxx0x
xxxxx000x1xxx110x1xxx11xxx1x1xxx
xxx011x0
xxx111x1
xxxx10xx
xxxx1x0x
11xx1x1x
xxx11001
10xx1x0x
xxxxxxxx
xxxxxxxx
00xx101x

11x1xxx0
xxxxxxxx
xxxxxxxx
xxx1xxx1
x1xxxxxx
00x1xxxx
10xxxxx0
xx001xxx
x011x1xx
xx11x1x0
101000xx
00xx1xx0
xx01xxxx
xx10xxxx
xxxxxxxx
xx011xxx
xxxx1xxx
xx11x1xx
x1xxx01x
x100x0xx
xxxxxxxx
xxxxx1xxxx00x1xx
x0xxx1xx
xxxxxxxx
x0xxx1xx
xxxxxxxx
01xx1xxx

120xx1xxxx
01xxxxxx
xxxxxxxx
xxxxxxxx
x01xxxxx
x111xxxx
xxxxxxxx
1xxxxxx0
xxxxxxxx
1xxxxxxx
xxxxxxxx
xxxxxxxx
xxxxx10x1xxxx00xx1xx00xx
x1xx0xx0
xxxxxxxx
xx0xx01x
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xx1xxxxx
x01x0xxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx

S31xxxx011
011x1xxx
11xx11xx
1xxxx1xx
111xx1x1
xxxxxxxx
0x1x0010
1xxxxxxx
1xxxx1xx
1xxxx1xx
xxx1xx10
0xx1x000
10xx1xxx
1xxxxxxx
110xxxxx
xxxxxxxx
1x0x1xxx
xxxxxxxx
10xxx1xx
xxxx1xxx
0xxx10xx
0xxxx1xx
xxxxxxxx
xxxxxxxx
1xxxx1xx
xx11xxx1
1x00x1x0
xx101x11

変数

表 6: 換字テーブルの 7 階差分値
S0
S1
S2

x0 x1 ,x2 ,x3 ,x4 ,x5 ,x6x0 x1 ,x2 ,x3 ,x4 ,x5 ,x7x0 x1 ,x2 ,x3 ,x4 ,x6 ,x7x0 x1 ,x2 ,x3 ,x5 ,x6 ,x7x0 x1 ,x2 ,x4 ,x5 ,x6 ,x7x0 x1 ,x3 ,x4 ,x5 ,x6 ,x7x0 x2 ,x3 ,x4 ,x5 ,x6 ,x7x1 x2 ,x3 ,x4 ,x5 ,x6 ,x7

変数0111011011111010
10011000
11000010
00010101
11100000
00100000
00110001

0010111000000010
11000111
10001001
11001010
10111001
00000011
0011011000001111
0110111000110000
11011001
01011001
10010011
1000011011111111

表 7: 換字テーブルの 8 階差分値
S0
S1
S2x0 ,x1 ,x2 ,x3 ,x4 ,x5 ,x6 ,x700000000

00000000

00000000

表 8: 換字テーブルの GF (28 ) 上の多項式項数
原始多項式項数

0x11d0x12b0x12d0x14d0x15f0x163
0x165
0x169
0x1710x187
0x18d
0x1a9
0x1c3
0x1cf
0x1e7
0x1f5

S0

S1

S2

S3

254
252
255
254
255
252
255
253
255
254
255
255
254
252
245
253

254
255
253
254
255
254
254
255
253
255
254
253
254
255
255
254

254
254
252
252
253
254
254
254
255
253
255
254
253
255
255
255

254
255
253
255
255
255
253
254
255
255
252
254
253
255
255
252

13

S3
00010000
01101000
00010111
00110011
01111011
00001010
11000100
01000000

S300000000