付録Ａ．CIPHERUNICORN-E の高階差分及び補間攻撃について
平成 12 年 1 月 12 日

はじめに

1

本資料は、電子政府事業に用いる暗号方式に関する応募資料 (暗号技術仕様書 CIPHERUNICORN-E 及び自己評価書 CIPHERUNICORN-E) に基づき詳細評価を行うために作成したものである。ア
ルゴリズムに関する記述は省略したので、関数名の仕様や変数名は、仕様書を参照して頂きたい。

CIPHERUNICORN-E のアルゴリズム

2

CIPHERUNICORN-E の全体構造は以下のとおりである。（図 1 参照)
ブロック長
秘密鍵長

64 ビット
128 ビット

段数

Feistel 型
16 段 (2 段ごとに 64 ビット幅関数 (L 関数) を使用)

鍵スケジューラ

秘密鍵を入力とする Feistel 構造

全体構造

段関数であるＦ関数は、32 ビット入出力の関数であり、段当たり拡大鍵 128 ビットが供給される。
Ｆ関数は本流部と一時鍵生成部からなり、前者はＴ関数１０層の従属接続と一時鍵加算部のＫ関数から構成される。Ｔ関数は４つのＳボックスで構成される。

3

高階差分解読 (Higher Order Diﬀerential Cryptanalysis)

3.1

自己評価書による評価

F 関数 (拡大鍵は全て 0 とする) の出力ビット全てについて, 代数次数 6 次までの項を調査した(表 1)。6 次の項数が十分あることから,F 関数あたりの代数次数は少なくとも 6 である。1 段目のF 関数への入力を 0 に固定した場合,3 段で 36 次となり, 解読に必要な平文を用意することは不可能になる。よって,5 段以上あれば解読は困難である。また,6 次の項数も十分であることから, 平文の一部のビットを 0 で固定して全体の代数次数を下げるような解読の適用も困難であると、自己評
価書には記載されている。

1

次数

表 1: F 関数ブール多項式項数平均
最大値 最小値 期待値

1次172411162次2472642252483次24782540

2408

2480

4次

17946

18156

17697

17980

5次100762

1011281003771006886次453003 453677 452218 453096
期待値:次数 d で取りうる項の種類 32 Cd の 1/23.2

形式的代数次数評価

3.2.1

Sbox の代数次数CIPHERUNICORN-E では、４種類のＳボックス Si (0 ≤ i ≤ 3) が使用される。各Ｓボックス入出力をブール多項式表現した。計算の結果を表 2 に示す。表の通り, 多項式の次数は全て 7 次であり, 項数はほぼ期待値である 128 を中心に分布し、全ての次数項が、各出力ビットで偏り無く使用されていると推測される。
表 2: Sbox ブール多項式次数
SBox 0 1 2 3 4 5 67S077777777S177777777S277777777S377777777

以下に一例として S0 の最下位ビットを示す。
S00=x1 x2 x3 x4 x5 x6 x7 + x0 x1 x2 x4 x5 x6 x7 + x2 x3 x4 x5 x6 x7 +x0 x3 x4 x5 x6 x7 + x1 x2 x3 x5 x6 x7 + x0 x2 x3 x5 x6 x7 + x0 x1 x2 x5 x6 x7 +x1 x2 x3 x4 x6 x7 + x0 x2 x3 x4 x5 x7 + x0 x1 x3 x4 x5 x7 + x0 x1 x2 x4 x5 x7 +x0 x1 x2 x3 x4 x7 + x1 x2 x3 x4 x5 x6 + x0 x2 x3 x4 x5 x6 + x0 x1 x3 x4 x5 x6 +x0 x1 x2 x3 x5 x6 + x0 x1 x2 x3 x4 x5 + x3 x4 x5 x6 x7 + x2 x4 x5 x6 x7 +x1 x4 x5 x6 x7 + x2 x3 x5 x6 x7 + x1 x3 x5 x6 x7 + x0 x3 x5 x6 x7 +x1 x2 x4 x6 x7 + x0 x1 x3 x6 x7 + x0 x1 x2 x6 x7 + x0 x3 x4 x5 x7 +x0 x1 x4 x5 x7 + x0 x1 x3 x5 x7 + x0 x1 x2 x5 x7 + x0 x2 x3 x4 x7 +x0 x2 x4 x5 x6 + x1 x2 x3 x5 x6 + x0 x2 x3 x5 x6 + x0 x1 x2 x5 x6 +x0 x1 x2 x4 x6 + x0 x1 x2 x3 x6 + x1 x2 x3 x4 x5 + x0 x1 x2 x3 x4 + x1 x5 x6 x7 +x2 x4 x6 x7 + x1 x4 x6 x7 + x1 x3 x6 x7 + x0 x3 x6 x7 + x1 x2 x6 x7 +x0 x2 x6 x7 + x2 x4 x5 x7 + x2 x3 x5 x7 + x1 x3 x5 x7 + x0 x3 x5 x7 +x1 x2 x5 x7 + x0 x2 x5 x7 + x2 x3 x4 x7 + x0 x3 x4 x7 + x0 x2 x4 x7 +x0 x1 x4 x7 + x0 x1 x2 x7 + x3 x4 x5 x6 + x2 x4 x5 x6 + x1 x4 x5 x6 +x0 x4 x5 x6 + x1 x2 x5 x6 + x0 x2 x3 x6 + x0 x1 x2 x6 + x1 x2 x4 x5 +x0 x2 x4 x5 + x1 x2 x3 x5 + x0 x1 x3 x5 + x0 x1 x2 x5 + x0 x2 x3 x4 +x0 x1 x3 x4 + x3 x6 x7 + x0 x6 x7 + x3 x5 x7 + x2 x5 x7 + x1 x5 x7 + x0 x5 x7 +x3 x4 x7 + x2 x4 x7 + x1 x4 x7 + x2 x3 x7 + x0 x1 x7 + x3 x5 x6 + x2 x5 x6 +x1 x5 x6 + x3 x4 x6 + x0 x3 x6 + x1 x2 x6 + x0 x1 x6 + x3 x4 x5 + x1 x4 x5 +x1 x3 x5 + x0 x2 x5 + x0 x1 x5 + x2 x3 x4 + x1 x2 x4 + x0 x2 x4 + x1 x2 x3 +x0 x2 x3 + x4 x7 + x3 x7 + x0 x7 + x5 x6 + x3 x6 + x2 x6 + x1 x6 + x2 x5 +x1 x5 + x2 x4 + x1 x3 + x0 x3 + x1 x2 + x7 + x5 + x3 + 12

3.2.2L 関数

L 関数は 128 ビット入力 64 ビット出力の関数で入力が X = XL ||XR (64 ビット) 及び拡大鍵
LK = LKL||LKR (64 ビット) である。また, 出力は,Z = ZL ||ZR (64 ビット) である。
L 関数では以下の演算が行われる。
ZL = XL ⊕ (XR ∧ LKR ) ⊕ (XL ∧ LKL ∧ LKR )ZR = XR ⊕ (XL ∧ LKL) ⊕ (XR ∧ LKL ∧ LKR )となる。各ビットごとの入出力に注目してみると, 鍵によって XL ,XR ,XL ⊕ XR の 3 通りであり、入力に対する次数は 1 次である。

3.2.3T 関数

F 関数内に使用されている T 関数は、32 ビット入出力の関数であり、4 種類ある。各Ｔ関数には、４種類のＳボックス Si (0 ≤ i ≤ 3) が使用されている。32 ビット入力中の定められた 8 ビットが、これらＳボックスに入り、他の 24 ビットと排他的論理和される構造を持つ。T 関数の次数はＳボックスの次数で定まり、全て 7 次である。

3.2.4

K 関数

K 関数は入力番号 n と入力データ X = X0 ||X1 ||X2 ||X3 (32 ビット) 及び一時鍵 wk を入力とし出力データ Z(32 ビット) とする関数である。それぞれ,K(0, wk) = (X0 ⊕ wk)||X1 ||X2 ||X3
K(1, wk) = X0 ||(X1 ⊕ wk)||X2 ||X3
K(2, wk) = X0 ||X1 ||(X2 ⊕ wk)||X3K(3, wk) = X0 ||X1 ||X2 ||(X3 ⊕ wk)となっており, 全て 1 次である。

3.2.5

F 関数

F 関数の主流部に着目すると, 最初に拡大鍵が算術和され, その後 T 関数を 4 回, 再び拡大鍵を算術和し, T 関数を 4 回使用し最後に K 関数 T 関数の組み合わせを 2 回行っている。最初に T 関数を 4 回通るまでの次数の追跡を図 2 に示す。次数の追跡においては、単純な代数次数だけでなく、係わりを持つ入力ビット数による制限（次数≦入力ビット数）も併用した。

F 関数としてみた場合の次数を図 3 に示す。入力から５層目の T 関数出力において,32 次に達すると考えられる。

F 関数は全単射でない 32bit 入出力関数であるので,32 次となりうる。後述の実験結果のように、Ｆ関数 32 階差分は、鍵に依存する非零値であり確かに、32 次であることがわかった。
従って、L 関数の影響を無視して、平文左半分を変数にとる 32 階差分攻撃を考えても、
図 4 の様に 3 段目通過時点で暗号全体の形式的代数次数は, それぞれ 32 次以上となり, 攻撃に必要な平文が平文の全数を超えてしまい, 高階差分攻撃が適用できない。

33.3

SBox の高階差分特性

S3 〜S0 の SBox について高階差分値を求めた。S3 〜S0 の 4 つの全ての SBox について、１〜8階差分値を計算し、定数となる bit を探索した。その結果、5 階差分、6 階差分の一部について、ある bit が定数となった。その結果を表 3、表 4 に示す。
表 3: SBox の 5 階差分値

変数x1 ,x2 ,x3 ,x4 ,x5
x1 ,x2 ,x3 ,x5 ,x7x0 ,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 ,x7

S0xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxx1
xxxxxx1x
xxxxxxxx
xxxxx1xx

S1xxxxxxxx
x1xxxxxx
x1xxxxxx
x1xxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx

S2xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxx1xx
xx1xx0xx
xxxxxxxx

S3xxxxx1xx
xxxxxxxx
xxxxxxxx
xxxxxxx1
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx

また、7 階差分値は全ての bit が入力値によらない定数値となり、さらに 8 階差分は all zero となった。この結果は SBox が全単射関数であることに起因する。その様子を表 5、表 6 に示す。表中の x は、固定値の選び方により高階差分の値が変化する bit を表し、1 または 0 は固定値によらない値、すなわち定数となるということを示している。

3.4

F 関数の 32 階差分F 関数の出力ビット全てについて,32 階差分を計算した。結果, 全てのビットについて鍵によって値の違う差分が出力されていることがわかった。
このことから F 関数は鍵によって変わるが,32 次とみなせると言える。

3.5

SQUARE 型攻撃評価

４種類のＳボックスは、全て全単射関数である。従って、F 関数の最右端１バイトのみを変数とし、256 通りの入力を考えれば、４回の Ｔ 関数通過後図 2 の T (3) 出力４バイトは、各々256 通り全ての値をとり、８階差分が０である。しかし、５層目の出力においては、本文性質５より８階差分が０となるが、256 通りのパターンが出現している訳ではなく、これ以上の層を通過後の８階差分は確定できない。2.2 節の形式的代数次数解析より１回分多い T 関数通過後まで、８階差分攻撃が可能となるが、依然として、F 関数全体の高階差分特性で、多段の F 関数を攻撃できるものは、見つかっておらず、L 関数を無視したとしても 3 段の F 関数で、高階差分攻撃は適用できない。

4

補間攻撃 (Interpolation Attack)

4.1

自己評価書による評価

補間攻撃は, 暗号文のある n ビットを, 平文に関する GF (q) 上の多項式で表現したとき, その多項式 (鍵の多項式) の, 未知の係数の数が N であれば,N 組の暗号文と平文から, 高い確率でこの多4表 4: SBox の 6 階差分値

変数

x0 ,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

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

S1
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

S20xx1xxxx
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

S3
1xxxx011
011x1xxx
11xx11xx
1xxxx1xx
111xx1x1xxxxxxxx
0x1x0010
1xxxxxxx
1xxxx1xx
1xxxx1xx
xxx1xx10
0xx1x000
10xx1xxx
1xxxxxxx
110xxxxx
xxxxxxxx
1x0x1xxx
xxxxxxxx
10xxx1xx
xxxx1xxx
0xxx10xx
0xxxx1xx
xxxxxxxx
xxxxxxxx
1xxxx1xxxx11xxx1
1x00x1x0xx101x11

項式を復元できることを利用して解読するものである。この多項式が復元されれば, 任意の暗号文に対する平文が計算できるため,N < q ならば意味のある攻撃となる。また,N は小さいほど攻撃は容易になる。ここで,q は素数または素数のべきとする。しかし, 暗号器全体に対して上記を保証することは困難であることから, 広い意味での補間攻撃に対する強度を保証することは困難であると思われる。過去の解読報告から考えると,CIPHERUNICORN-E で使用している 4 種の SBox をGF (28 ) 上の多項式で表現したとき, その多項式の項数が十分に大きい値ならば, 暗号全体として補間攻撃に対して十分に安全であると期待できる。SBox を GF (28 ) 上の多項式で表現したときの項数調査結果を表 7 に示す。SBox の生成に使用した既約多項式について,GF (28 ) 上の多項式で表現した結果, 項の数は 252 以上であった。最大項数は 255 なので, 項の数 252 は十分大きい値であり,補間攻撃に対して十分安全であると期待できる。

4.1.1

GF (28 ) における Sbox の多項式表現

SBox を GF (28 ) 上の多項式で表現した時の項数調査結果を表 8 に示す。項の数は 8 次の全ての原始多項式に対しても 252 以上であった。CIPHERUNICOEN-E の自己評価書の項数評価を裏付ける結果であり、補間攻撃に対する安全性が期待できる。

5表 5: 換字テーブルの 7 階差分値
変数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

S00111011011111010
10011000
11000010
00010101
11100000
00100000
00110001

S100101110
00000010
11000111
10001001
11001010
10111001
00000011
00110110

S200001111
0110111000110000
1101100101011001
10010011
1000011011111111

表 6: 換字テーブルの 8 階差分値
変数x0 ,x1 ,x2 ,x3 ,x4 ,x5 ,x6 ,x75

S000000000

S100000000

S200000000

S300010000
01101000
00010111
00110011
01111011
00001010
11000100
01000000

S300000000

まとめCIPHERUNICORN-E について高階差分攻撃や補間攻撃の点から評価を行った。Ｓボックス等の構成部品の特性を基に、高階差分探索の努力は行ったが結果として, ２段でも適切な高階差分が発見できなかった。また、Ｆ関数に入る拡大鍵ビット数が 128 ビットである事、次数が３２次であり、その項数も、（６次までの探索に基づく予想ではあるが）十分多い事から１段消去型の攻撃も難しい。以上のように、3 段以上の段数においては高階差分攻撃及び補間攻撃の適用可能性は、見いだせなかった。

参考文献[Nec] 日本電気, ”暗号技術仕様書 CIPHERUNICORN-E ／自己評価書 CIPHERUNICORN-E”,IPA 提出資料6

表 7: SBox の GF (28 ) 上の多項式項数
既約多項式
S0S1S2
S30x11d0x14d0x165

254254254254

254

254252

255255254

253

2540x171255
253
255 255 それぞれの SBox を構成する時に使用した既約多項式。

表 8: S-Box の GF (28 ) 上の多項式項数
原始多項式

項数

S0S1

S2

S30x11d

254

254

254

254

0x12b252

255

254

2550x12d255

253

252

2530x14d254

254

252

2550x15f

255

255

253

2550x163

252

254

254

2550x165

255

254

254

2530x169

253

255

254

2540x171255253255

2550x187254

255

253

255

0x18d255

254

255

252

0x1a9255

253

254

254

0x1c3254

254

253

253

0x1cf

252255255

255

0x1e7245

255

255

255

0x1f5253

254

255

252

7

P
LK{0}
{0}

L

FK{0},SK{0}
F{0}
{1}

{1}

FK ,SK
F

{1}

LK{1}
L{1}
{2}

{2}

FK ,SKF{2}

FK{3},SK{3}F{3}FK{15},SK{15}
F{15}
LK{8}
L{8}

C
図 1: CIPHERUNICORN-E の構造

8

1

X1

X0

X

X
X2X31111S3S0

S1S2777X1X0

X2777

S2

S3S0S11313713ZT(0)

T(1)

X

X 2113X2X313131313S1S2S3S0212121211314ZX1X377X07X0X1X2X321212121S0S12921S2S3292929Z

Z

T(2)

T(3)

図 2: F 関数内の最初の 4 つの T 関数の形式的代数次数

929

X

32bitsmain
stream

FK[0]

1
T(0)

temporary

7

SK[0]

key

T(1)

13

Y(3,8,16)

generation

T(2)

T(0)

mechanism

21

SK[1]

T(3)

29

Y(7,9,13)

FK[1]

T(0)

T(sh[wk0][0])32T(sh[wk0][1])T(1)32wk0T(sh[wk0][2])>>2832
T(sh[wk0][3])

0xff

32
wk1

K(sh[wk0][0])<80xffT(sh[wk0][0])32
wk2

K(sh[wk0][1])T(sh[wk0][1])<8>>83232
Z
図 3: F 関数の形式的代数次数

10

P

10
LK {0}{0}

L

1

FK{0},SK{0}

0

0

F{0}

FK{1},SK{1}

0 32

1F{1}

32

1

LK {1}

L{1}

1 32

32

32

F{2}

…

FK{2},SK{2}32図 4: 形式的代数次数の解析

11