CIPHERUNICORN-A に対する安全性について

2001 年 12 月 19 日

日本電信電話株式会社
神田 雅透

CIPHERUNICORN-A に対する安全性について
日本電信電話株式会社

December 19, 2001
CIPHERUNICORN-A

Abstract

本稿では，の差分特性確率について，設計者の立場から評価を実施した。その結果，差分解読法では，仕様である段について，高い確率で攻撃が成功することはないとの結論に達した。

1

16安全性検証に関する考え方

本稿では，CIPHERUNICORN-A の差分解読法に対する安全性を検証する。今回は設計者の立場より評価を行うものとし ，仕様である 16 段が攻撃可能かど うかについてのみ検討した。つまり，攻撃可能段数を検討したものではないことに注意されたい。
CIPHERUNICORN-A の検討すべき特徴点としては，

 本流部での Feistel 型構造の効果
 A3 関数の効果
 一時鍵生成部の効果が挙げられる。もしも攻撃可能段数を求めようとするならば ，これらの効果について厳密な調査を実施する必要がある。しかし，暗号仕様が安全であるか否かだけを検証するのであれば ，必ずしも厳密に評価する必要はなく，適切な考察の下での安全性上界を調べればよい。この方針の下，安全性評価上，有効だと考える以下のような考察を行った。なお，副鍵の 32 ビット加算については排他的論理和とみなす。
本流部のFeistel 型構造の効果

本流部は，A3 関数，定数乗算，T0 関数，定数乗算，7 段の固定 Feistel 構造，2 段の一時鍵依存関数，そして，最後に一時鍵の挿入が行われる。
まず，A3 関数後の定数乗算から固定 Feistel 構造までの特性を考える。CIPHERUNICORN-A
で利用する定数乗算は mod 232 での演算であるため，入力差分で差分の立っている最下位ビットと，それより上位のビットについてのみ差分波及が起こる。すなわち，差分の立っている最下位ビットが 31 ビット目（ LSB) であれば出力差分の全ビットが差分波及の対象となる。しかし，入力差分の 0 ビット目 (MSB) にしか差分が立っていない場合，出力差分の MSB にしか差分は波及しない。つまり，入力差分が 0x80000000 であれば確率 1 で出力差分が 0x800000000 になる。同様の考え方をすると，上位 8 ビットに差分が立っている，すなわち 0x**000000（ **はオールゼロではない）であるとすると，確率 1 で出力差分が 0x##000000 になる。以上のことは，定数乗算部については入力差分が上位に集まっているほど 高い確率での正確な見積もりが可能になることを示している。
例として，入力差分として，(0x80000000,0x8A2240A7) を考える。

1

SKa;;;
FKa

SKb

FKb

A3

T0

A

T0

T0

B

T0

T1

T0

T0

T1
T1
T2
T1
T2;;;
T3

T3

C

<<< 2Tk

Tk

Figure 1: CIPHERUNICORN-A のラウンド 関数
このとき，上述した理由によって，定数乗算を通過したところ (図 1 A の場所）での差分も確率 1 で同じ 0x80000000 となる。次に，T0 関数の差分特性を考慮すると，確率 2;7 で T0 関数の出力差分が 0x8A2240A7 となるものが存在する。このとき，定数乗算前のところ (図 1 B の場所)の差分はゼロとなる。そのあとは，すべての (固定)T 関数への入力差分はゼロであるので，同じ差分のまま伝播し ，図 1 C の場所での差分は (0x80000000, 0x00000000) となる。
同様に，入力差分を (0xE6000000 0xB581090C) とする。このとき，定数乗算での差分伝播がランダムに起こると仮定すると，上位 6 ビットがランダムな振舞いをする (7 ビット目は必ず 1 になる) ので，A のところで 0xE6000000 となるものが確率 2;6 で発生する。T0 関数では同様に確率 2;7 で B における差分をゼロとするものが存在するので，この場合，確率 2;13 で図 1 C の場所での差分は (0x80000000, 0x00000000) となると期待される。

A3 関数の効果

A3 関数は，64 ビット入力 x に対し ，(x)  (x <<< 23)  (x <<< 41) を出力する関数である。
なお，<<< はローテーションを表す。これを各ビットごとに詳し く書き表すと，表 1 のようになる。なお，x] は入力の第 x ビット目の値を表す。
2

Table 1: A3 関数の入出力ビット関係
出力ビット位置01
2345678910111213141516171819202122232425262728293031

関連入力ビット

出力ビット位置

0]  23]  41]
1]  24]  42]
2]  25]  43]
3]  26]  44]
4]  27]  45]
5]  28]  46]
6]  29]  47]
7]  30]  48]
8]  31]  49]
9]  32]  50]
10]  33]  51]
11]  34]  52]
12]  35]  53]
13]  36]  54]
14]  37]  55]
15]  38]  56]
16]  39]  57]
17]  40]  58]
18]  41]  59]
19]  42]  60]
20]  43]  61]
21]  44]  62]22]  45]  63]
23]  46]  0]
24]  47]  1]
25]  48]  2]
26]  49]  3]
27]  50]  4]
28]  51]  5]
29]  52]  6]
30]  53]  7]
31]  54]  8]

32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

関連入力ビット32]  55]  9]
33]  56]  10]34]  57]  11]35]  58]  12]36]  59]  13]
37]  60]  14]38]  61]  15]39]  62]  16]40]  63]  17]41]  0]  18]
42]  1]  19]43]  2]  20]
44]  3]  21]
45]  4]  22]
46]  5]  23]
47]  6]  24]
48]  7]  25]
49]  8]  26]
50]  9]  27]
51]  10]  28]
52]  11]  29]
53]  12]  30]
54]  13]  31]
55]  14]  32]
56]  15]  33]
57]  16]  34]
58]  17]  35]
59]  18]  36]
60]  19]  37]
61]  20]  38]62]  21]  39]63]  22]  40]

したがって，左半分のうち上位 8 ビットに出力差分を集めるような入力差分，すなわち，出力差分の 8 ビット目から 31 ビット目までをゼロとするようなを入力差分となるための条件を表 1から求めると，以下のようになる。

49] = 54] = 8]  31] = 3]  26] = 13]  36]
50] = 9]  32] = 4]  27]
51] = 10]  33] = 5]  28]
52] = 11]  34] = 6]  29]
53] = 12]  35] = 7]  30]

3

Table 2: 出力差分の 8-31 ビットがゼロとなるときの A3 関数の入出力ビット関係
出力ビット位置

0
12
34
56
7
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

関連入力ビット41]  46]42]  47]
43]  48]
44]  49]45]  50]
46]  51]47]  52]
48]  53]
50]  55]
51]  56]
52]  57]
53]  58]
54]  59]55]  60]
56]  61]57]  62]58]  63]59]  0]
60]  1]
61]  2]
62]  3]
63]  4]
0]  5]
1]  6]

出力ビット位置関連入力ビット

48
4950
51
5253
5455
56
57
58
59
60
6162
63

2]  7]
3]  8]
4]  9]
5]  10]
6]  11]
7]  12]
8]  13]32]  37]
33]  38]
34]  39]35]  40]
36]  41]
37]  42]38]  43]39]  44]40]  45]

0]  23]  46] = 0 1]  24]  47] = 0 2]  25]  48] = 0
14]  37]  55] = 0 15]  38]  56] = 0 16]  39]  57] = 0
17]  40]  58] = 0 18]  41]  59] = 0 19]  42]  60] = 0
20]  43]  61] = 0 21]  44]  62] = 0 22]  45]  63] = 0

この条件をもとに，その他の出力差分の各ビットについて入力差分との関係をみると表 2 のようになる。A3 関数は線形変換であるため，上記の条件を満たす限りにおいて，表 2 は確率 1で成立する。
これらの情報をもとに，図 1 B のところの全ビットがゼロ差分になるものがあるかど うかを調査した。
その結果，128 通りの入力差分について，A3 関数の出力差分の上位 8 ビットが 0x80 となり，確率 2;7 で図 1 B のところの全ビットがゼロ差分になるものが見つかった。このうち，もっとも入力ハミング重みが最小となる入力差分は，(0x04A65520 0x028A5388) のときのハミング重み20 である。このとき，A3 関数を通過した出力差分は (0x80000000 0x8A2240A7) となる。
また，上位 8 ビットが非ゼロとなるという条件に緩めると，32640 通りの入力差分について，定数乗算の結果が同じ出力差分になるという仮定のもと，T0 関数の確率が 2;7 で図 1 B のところの全ビットがゼロ差分になるものが見つかった。このうち，もっとも入力ハミング重みが最小となる入力差分は，(0x0200C 984 0x04130160) のときのハミング重み 14 である。このとき，A3関数を通過した出力差分は (0xE 6000000 0xB 581090C ) となる。

48000010000400000

T0T0

T1

T1

T2

T2

T3

T3

Figure 2: active s-box が 3 個の例
一方，入力差分として，(0x80000000 0x00000000) を考えた場合，A3 関数を通ることによって，(0x80000100 0x00400000) となる。図 1 B の直前の定数乗算の特性を考慮すると，下位ビットに差分が経つことは，B における差分予測を困難な（ 確率が小さくなる）方向へ作用するはずであるから，A における上位 8 ビットには差分がたたないほうが全体として差分特性確率を高いまま維持できるものと期待される。その仮定のもと，truncated vector での探索的な考え方をすると，図 2 のような active s-box が 3 個になるものが見つかる。このときの出力差分として，必ずしも (0x04A65520 0x028A5388) となるものが存在するとはいえないが，少なくとも truncatedvector の意味で一致することから，定数乗算部での確率低下を除き，確率 (2;7 )3 = 2;21 と見積もることとする。
以上の考察から，A3 関数での効果は，入力差分のハミング重みが少ないときには比較的効果的に入力差分を散らばらせ，定数乗算の影響を増す一方，逆にハミング重みが多いときにはハミング重みを減少させ，定数乗算の影響を減じてしまう可能性がある。

5

(0x04A65520, 0x028A5388)(0x80000000,0x00000000)(0x04A65520, 0x028A5388)

F-(0x80000000,0x00000000)(0x00000000,0x00000000)

F-(0x00000000,0x00000000)(0x04A65520, 0x028A5388)

F-(0x80000000,0x00000000)

Pr < -72(0x80000000,0x00000000)

F-(0x04A65520, 0x028A5388)

Pr < -212(0x00000000,0x00000000)

F-(0x00000000,0x00000000)(0x80000000,0x00000000)

F-(0x04A65520, 0x028A5388)(0x04A65520, 0x028A5388)

Pr < -72

Pr = 1Pr = 1

Pr < -212(0x80000000,0x00000000)

Figure 3: 一時鍵生成部を除いたラウンド 関数での繰り返し表現の例
本流部のみによる考察のまとめ
一時鍵生成部を除いた部分 (図 1 の C より上部) だけを考えた場合，CIPHERUNICORN-A は全（ 存在したならば ）単射関数となっている。そこで，繰り返し表現を考えると，図 3 に示すものが，かなり高確率な差分特性経路といえるであろう。
この結果を用いると，仕様と同じ 16 段で差分特性確率の上界値が 2;128 を下回ることがわかる。4 段目と 6 段目の定数乗算での影響を無視しているので，実際にはこの見積もりよりは安全であると期待される。ただし，今回の検討結果では必ずしも最良のものを見つけたというわけではないので，ここで検討したような本流部だけのラウンド 関数であるとしたら，確実に差分解読法に対して安全であるとの確証は，今回の検討結果からだけではもてない。その意味において，
CIPHERUNICORN-A の一時鍵生成部は重要な役割を果たしているものと期待される。
一時鍵生成部の効果
一時鍵生成部における効果としては二つ有り，一つは T 関数の構造を変える効果，もう一つが本流部に差し込まれる \副鍵" としての効果である。
このうち，T 関数の構造を変える効果について，もともと関連するビットが合計 4 ビットと少6ない上，Feistel 構造のラウンド 関数をデータによって変えることになるため，その効果が設計者にとって必ず有利になる (望ましい) かど うかは即断できない。例えば，固定の全単射関数であれ
ば ，非ゼロ差分が入力されたとき，当然，非ゼロ差分が出力される。逆に，ゼロ差分が入力されれば ，ゼロ差分が出力される。しかしながら，データによって構造を変えるということは，たとえ個々の関数としてみれば全単射であったとしても，非ゼロ差分の入力に対しゼロ差分が出力されたり，ゼロ差分の入力にもかからわず非ゼロ差分が出力されるといった状況が起こりうる。こういった，通常の全単射関数では起こらないような状況を発生させることは，そのこと自体が確かに予測困難にしており，全体としてみれば安全性の向上に寄与しているとも言えなくはない。
だが，一方で，こういった通常では起こらない特徴を利用して，逆に攻撃に利用させる懸念もある。そういった意味において，一時鍵生成部により T 関数の構造を変えるという効果については過大評価も過小評価もできないというのが現状であろうと考える。
これに対し ，もう一方の \副鍵" としての効果はかなり効果が高いものと期待する。
つまり，本流部では，入力ハミング重みが多いとき，(一時鍵生成部の影響を除くと) 高い確率で存在する差分特性経路が存在する場合が少なからずあることは上述したとおりである。それに対し，一時鍵生成部は 4 つの定数乗算を利用するため，入力ハミング重みが多いときほど ，逆によりランダム関数に近づくと期待してよかろう。つまり，\副鍵" として差し込まれる値の予測がかなり難しくなることを意味する。一方，入力ハミング重みが少ないとき，一時鍵生成部の特性はもしかすると高い確率で予測できるかもしれない。しかし，そのときには，A3 関数の効果によって，本流部だけでランダム化の影響が大きく出ていると期待される。このように，本流部のA3 関数の効果と一時鍵生成部での \副鍵" の効果では，入力データのハミング重みの大小に関連して，本流部での攻撃者に有利となる特性を少なからず互いに打ち消しあう効果があり，有用なものであると判断する。

2

本検討の最終結論

本稿では，CIPHERUNICORN-A の差分解読法に対する安全性について検証を実施した。その結果，一時鍵生成を完全に除いた，本流部（ 固定構造の部分のみ）だけでの安全性を見た場合には，16 段における差分特性確率の上界値が 2;128 を下回るであろうとの傍証を導いた。ただし，この検討結果は，一部の定数乗算の影響を無視しているという設計者に不利な要素（ 厳しい評価）と，最良のものを探索した結果ではないという設計者に有利な要素（ 甘い評価）とが混在しているため，これをもって，安全であるか否かの結論が直接導かれるわけではない。
一方，一時鍵生成部の存在は，ラウンド 関数での安全性を向上させる方向へ作用することはおそらく間違いないと考えられる。特に，入力データのハミング重みの大小に関連して，本流部での攻撃者に有利となる特性を少なからず打ち消す効果があり，有用なものであると判断する。
したがって，本流部だけの安全性評価結果と一時鍵生成部での特に \副鍵" の効果を考え合わせれば，最終的に CIPHERUNICORN-A の仕様である 16 段について，高い確率で差分解読法によって攻撃が成功することはなく，安全であると考える。
以上

7