ＣＲＹＰＴＲＥＣ応募暗号の高階差分及び補間攻撃耐性について（Ver.1）

平成１３年１月

１．

はじめに

これは、電子政府用暗号として、応募された６４ビット／１２８ビットブロック暗号に対する高階差分及び補間攻撃の立場の検証評価である。対象暗号は６４ビットブロック暗号として、CIPHERUNICORN-E、MISTY1、FEAL-NX、Hierocrypt-L1 の４暗号、１２８ビットブロック暗号として CIPHERUNICORN-A、Camellia、RC6、SC2000、MARS、Hierocrypt-3 の６暗号である。ここでは、自己評価書及び、関連論文の調査並びに計算機探索により、高階差分及び補間攻撃耐性に関し、各暗号に対し考察を行った。

２．

評価項目

多くの暗号は、その構成部品として、S-box、F 関数を持つ。暗号に非線形特性を与える最小の構成部品を S-box と呼ぶ。平文は、暗号化関数を通る間に、非線形処理と線形処理の繰り返しを受けるが、S-box より大きなブロック単位で、繰り返し構造の基本単位を構成する部分をＦ関数と呼ぶ。各暗号の S-box 及び F 関数相当部品に対する以下の評価を基に、暗号の高階差分及び補間攻撃耐性を考察する。
（１）S-box S(X)の評価（１−１）ブール多項式次数、項数S(X)をブール多項式で表現し、その次数及び項数を評価する。
（１−２）拡大体上の補間多項式表現の項数テーブルとして与えられる S(X)について、全ての拡大体 GF(2m）上で補間多項式表現し、その項数を評価する。ここで m=|X|。
（２）Ｆ関数 F(X)の評価（２−１）S-box 以外の F 関数構成要素のブール多項式項数、次数（２−２）F(X)のブール多項式次数F(X)のブール多項式表現を（１−１）及び（２−１）の結果を用い F(X)のブール多項式表現を求め次数評価を行う。計算量的に不可能な場合は、形式的代数次数評価で代用。
（２−３）F(X)ブール多項式における低次項の出現頻度の評価
関数 F(X)の低次項係数で非零の個数を評価する。これは、（２−１）が形式的代数次数評価で行われた場合の補足データ。
（３） 高階差分攻撃及び補間攻撃の評価
ここでは主として、暗号化関数のコアに着目し段数に対する強度評価を行う。
（３−１）代数次数評価
適切な高階差分を選び、段数に対する暗号系の形式的代数次数の上昇を評価する。
（３−２）１−８高階差分特性の評価
平文８ビット以下を選ぶ任意の組み合わせに対し、１−８階差分値を計算し、段数に対する高階差分攻撃可能性を調査する。

2

（３−３）３１及び３２階高階差分特性の評価
平文ブロック３２ビットを選び、３１階及び３２階差分値を計算し、段数に対する高階差分攻撃可能性を調査する。
（３−４）ＳＱＵＡＲＥ型攻撃評価

Ｆ関数構成部品の１対１写像性を利用した高階差分攻撃の可能性を、段数に対し評価する。
（３−５）線形和攻撃耐性の評価
線形和攻撃の観点から、補間多項式の項数を調査し、段数に対する線形和攻撃耐性を評価する。
（３−６）
以上の評価をもとに、高階差分攻撃又は線形和攻撃（補間攻撃）耐性の評価を行う。

３．

高階差分攻撃３．１ 高階差分E(X；K)を、入力 X=(x1,x2,…,xn)∈GF(2)n と鍵 K∈GF(2)s から、Y=(y1,y2,…,ym)∈GF(2)mを出力する暗号化関数とする。高階差分攻撃は、ブール関数の高階差分特性[L94]を利用した攻撃である。
定義１．高階差分｛a1,a2,…,ai｝を GF(2)n 上で 1 次独立な i 個のベクトル、これらによって張られるGF(2)ｎの部分空間を V(i)で表し、入力差分と呼ぶ。関数 E(X；K)の V(i)に関する i 階差分 ∆(i ) E（X；K）は次式で定義される。

∆(Vi )( i ) E ( X ; K ) = ⊕( i ) E ( X ⊕ A; K )(3.1)

A∈Vこの下付添え字 V(i)は、誤解のおそれが無い省略する。高階差分は、次の性質を持つ。
性質１．
関数 E(X；K)の X に関するブール代数次数が N ならば、X と K に依存せず、次式が成立する。

∆( N +1) E ( X ⊕ A; K ) = 0(3.2)

この性質１を使用した高階差分攻撃が基本的高階差分攻撃である[JK97]。その攻撃能力は、以下の性質でさらに改良する事が可能である。
性質２．
関数 E(X；K)の X に関するブール代数次数が N で且つ、Ｎ次項の係数にＫが含まれていないならば、Ｎ階差分は、X と K に依存せず、関数Ｅ固有の定数となる。
(3.3)∆( N ) E ( X ⊕ A; K ) = const
ｎビットの入力｛x1,x2,…,xn｝から取り出したｋビット｛ｘi1,xi2,…,xik｝組の積であるｋ3

次項ｘi1xi2…xik を考える。このｋビットを含むｋ’（≧ｋ）ビットのビット組のｋ’次項にｋ次項ｘi1xi2…xik は含まれるというとする。このとき、次の性質が成り立つ。
性質３．
関数 E(X；K)のブール展開式にｋ次項ｘi1xi2…xik が含まれていないならば、｛ｘi1,xi2,…,xik｝に対応するｋ個の単位ベクトルの組｛ei1,ei2,…,eik｝で張られるｋ次元空間

Ｖ(k)(ei1,ei2,…,eik)に関するｋ階差分は、X と K に依存せず、次式が成立する。

∆V E ( X ⊕ A; K ) = 0
(k )

(k )

(3.4)

性質２及び３は、高階差分攻撃で必要な差分階数をＮ＋１から減らす性質であり、改良型高階差分攻撃で使用される[SMK97][MSK98]。さらに、関数 E(X；K)の入力Ｘを線形変換したもの Z = T ( X ) で置き換え、変数Ｚに関し、高階差分を取る事で高階差分攻撃の効率を上げる事も可能であり、これは定義１における、GF(2)ｎの部分空間 V(i)の選択のしかたに内包されている。また、E(X；K)が全単射関数の場合、次の性質が成り立つ。
性質４．

E(X；K)が全単射関数の場合、ブール代数次数はｎ−１であり、次式が成立する。

∆( n ) E ( X ⊕ A; K ) = 0(3.5)

この性質と、高階差分の線形性
性質５．
高階差分は ⊕ 演算に関し、線形性を持つ。

∆( i ) ( E ( X ; K ) ⊕ F ( X ; K ' )) = ∆(i ) E ( X ; K ) ⊕ ∆( i ) F ( X ; K ' )(3.6)

を使い、高階差分攻撃を行う手法がある。ＳＰＮ構造の暗号に対する SQUARE 攻撃は、多くの場合 S-box の全単射性と性質４，５を使用して行われる[DKR97]。
３．２

攻撃方程式

図１に繰り返し型暗号の模式図を示す。F(X)は段関数であり、入力 X を段鍵 Ki の制御のもと変換し、次段に出力する。高階差分攻撃では、暗号系の中間段の変数 H に関し、線形空間 V(N)に関するＮ階差分が０(又は const)となる H 及び V(N)を何らかの方法で求める。その V(N)の元を選択平文 P として入力するならば、H のＮ階差分が０(又は const)であることが保証されている。H を暗号文 C 側から、計算する関数を G(C;K)とするならば、次の攻撃方程式が成立する。

0 = ∆( N ) H =⊕C ← P∈V ( N )G (C ; K )(3.7)

この方程式を K に対し解くことで解読は行われる。この方程式に係わる鍵 K は、C から Hを計算する時に関係する段鍵 Ki の全部又は一部である。この方程式は、高次代数方程式であり、解析的に解くことは困難である。以下、代表的な解法を３つ示す。
＜攻撃方程式総当たり攻撃＞変数 H 及び K の未知ビット数をそれぞれ|H|及び|K|と表すな

4

P

K1

F(x)

K2F(x)

KR-1

F(x)

HF(x)

KＲC
図１.暗号系模式図
ら ば 、 一 つ の 偽 鍵 K に 対 し 式 (3.7) が 成 立 す る 確 率 は 2-|H| で あ る こ と か ら 組1の高階差分に対し、式(3.7)をふるい式として検査する事により、
M 1 = (| K | +1)| H |

真の鍵 K が定まる。この計算量 T1 は、K を総当たりするならば、
M 1 −1T1 = 2| K |2 N ∑ 2 −| H |i ≤ 2 N + | K | +1(3.8)

i =0回の G 関数計算である。必要な選択平文の最大組数は、M1 組の線形部分空間 V(N)を共通部分無く取る場合であり、 M 1 2 組である。部分空間 V(N)の取り方に自由度があり、共通部
N N1 
 通りあり、N

分が許される場合は、線形部分空間 V(N1)から V(N)を取り出す組み合わせは  N1  ≥ M 1 を満たす最小の N1 に対し 2 N1 組となる。
N 

必要な選択平文の最小組数は、 ＜線形化攻撃＞

攻撃方程式(3.7)は、連立高次代数方程式であるが、それを K に関し、ブール多項式展開し、K の各ビットの積である高次項も一つの未知数と考えて線形化し、逆行列計算で、真の鍵 K を求める手法が効果的である[SMK97]。その時の独立な未知項の個数をＬとするならば、必要な N 階差分組数は、 M 2 =  L

 であり、計算量は、逆行列計 | H |

偽鍵がふるい落とされるためには、生き残り偽鍵数の期待値（2|K|-1）*2-|H|M1 が十分小さい事が必要である。ここでは、その値が１未満となる組数 M1 を採用した。

15

算の計算量2を無視すれば、

T2 = 2 N M 2 L(3.9)

 N2  ≥ M 2 を満たす
N
 であり、必要な選択平文は最大 M 2 2 組、最小 2 2 組（ただし N2 は NN最小値）となる。
＜線形化＋総当たり攻撃＞

一部の鍵を総当たりしながら、残りを線形化して解くことも可能であり、総当たり部分の鍵ビット数を|K3|残り鍵部分に関し、ブール多項式展開したときの項数を L3 とする。|K3|ビット仮定し、L3 個の未知項に対し、L3+ｍ本（ｍ≧１）の線形方程を解けば、その方程式が不能か否かで仮定ビットの当否が判断できる。偽鍵に対( ) と見積もる事ができ、 2 2し、線形方程式が不能にならない確率は 2− L3 m|K3 |− L3 m<< 1 なるL3+ｍ本の線形方程式を用意すれば偽鍵は、全て排除されるであろう。 m = | K3 | としL3 

L +mて、そのような線形方程式を用意するのに必要な、高階差分組数は M 3 =  3

で| H |ある。この時、計算量はT3 ≤ 2 N + | K 3 | ( L3 + 1)

L| H | 3(3.10)となる。ここで総当たり部分の鍵|K1|ビットは、線形方程式が不能か否かで、ふるいにかけられる。そのため、高階差分組の及び計算量の見積もりにおいて、L3→L3+1 と評価した。

 N3  ≥ M 3 を満たす最小値）とN 

必要な選択平文は最大 M 3 2 組、最小 2 3 組（ただし N3 は NNなる。
３．３

高階差分攻撃に係わる評価量

前節で述べたように、高階差分攻撃は、線形空間 V(N) や中間段の変数 H を何らかの方法で求めることから始まる。最適な V(N)を求めることは、例え 64 ビットブロック暗号であっても計算量的に不可能である。通常は、暗号系の構成部品に対し、ブール多項式次数や項数などの高階差分攻撃の立場の評価量を求め、それを基に暗号系の高階差分攻撃耐性を推定していく。
２節の評価(1)及び(2)では構成部品の次数及び項数を評価し、それをもとに、評価(3)で高階差分攻撃耐性を評価した。
部品の評価及びその過程で得られた特徴をもとに(3-1)では、適切な V(N)を選び、代数次数の評価を行う。真の次数評価は、通常、計算量的に困難である為、多くの場合、形式的逆行列計算の計算量は、O(L3)である。L が大きい場合は無視できなくなる。この方法で、求めた計算量が鍵の総当たりに近い場合は、さらなる考察が必要である。

26代数次数評価でそれを代用した。即ち、次数は積で上昇し、関係する変数ビット数を超えないとの条件で次数評価を行った。
評価(3-2)では、入力平文ビットから、8 ビット以下を変数として選ぶ高階差分の範囲で、計算機により最適な V(N)の取り方を探索した。また、多くの暗号が 32 ビットを一つの小ブロックとして処理する構造を持つため、その小ブロック単位の 32 階及び 31 階差分に関し最適な V(N)の取り方を計算機探索した。
評価(3-3)では、１対１写像性を持つ暗号の部分ブロックに着目し、１対１性が保証される段数を求め、SQUARE 型の高階差分攻撃耐性を評価した。
(3-6)では、(3-1)から(3-5)の結果をもとに、高階差分攻撃又は線形和攻撃耐性の評価を行った。平文ブロック長を | P | 、秘密鍵のビット数を | K | として、解読に必要な選択平文組

2 |P| 未満、かつ計算量が 2 |K | 回の段関数計算以下の場合、解読が可能と考えその段数数がを求めた。各暗号についてこれら評価量データは、付録 A−Ｉに示す。

４．

補間攻撃

補間攻撃[JK97]は、広い範囲の概念を含むが、その中で実際的なものは、１変数型補間攻撃であろう。そこでは、暗号系の部分関数をガロア体 GF(q)上の１変数多項式で表す。

GF(q)の元 x から平文Ｐへの写像 p(x)を適切に選び、中間段の変数 H もガロア体 GF(q)の元と考える。平文 p(x)の暗号化過程を変数 H まで考えると、x から H への写像は、ガロア体GF(q)上の多項式関数
q −1

H = f K ( x) = ∑ a ( K )i x i(4.1)

i =0と表すことができる。i 次項係数 a ( K ) i は、秘密鍵Ｋの関数3であり、未知である。しかし、暗号系の解析により未知係数項数がＮ個と判っているならば、平文と H の対 N 組に対し、Lagrange 補間により、その未知係数 a ( K ) i を推定できる。途中の段鍵を仮定し暗号文 C から逆算した値 H の正当性（即ち、仮定した段鍵の真偽）は、N+1 組の(x,H)対で判断できる。
従って、平文Ｐ＝p(x)および対応する暗号文 C が N+1 組与えられれば、段鍵が推定できる事になる。ガロア体 GF(q)の元の個数はｑ種類であり、N<q ならば、この攻撃に必要な平文・暗号文組が用意できる。
未知係数 a ( K ) i の間に、秘密鍵 K に依存しない線形従属性がある場合、推定すべき未知係数の個数は減りＮ’個となる。この N’個の未知係数を推定する攻撃法として、1 変数型補間攻撃を拡張したのが線形和攻撃である[A00]。この場合 N’+1 組の平文・暗号文組を使用する。H を暗号文 C 側から、計算する関数を G(C;K)とし、ラグランジェ補間の計算量を無視するならば、解読計算量は

TL = 2 |H | ( N '+1)

3(4.2)

正確には、平文から H までの暗号化過程で影響を持つ段鍵 Kj{j=1,2,…}の関数
7

回の G 関数計算量である。
最適な、ガロア体 GF(q)及び写像 p(x)を選び出すことは、計算量的に困難である。ここでは、平文 P を 8 ビット単位の小ブロック 8 個（64 ビット暗号）又は 16 個(128 ビット暗号)に区切り、その小ブロックをガロア体 GF(28)の多項式基底で表現された元と見なして、線形和攻撃耐性を文献[A00]の手法で調査した。結果を付録Ｊに示す。

５．
高階差分／補間攻撃耐性
５．１ 64 ビットブロック暗号
CIPHERUNICORN-E、MISTY1、FEAL-NX、Hierocrypt-L1 の４暗号について調査し、結果は付録Ａ、Ｂ、Ｃ、Ｄ及びＪに示した。提案暗号に関し、高階差分／補間攻撃の立場
で、問題のある暗号は、存在しない。各暗号に対し、高階差分／補間攻撃の立場で、必要平文組数が 264 未満、計算量が 2128 未満で攻撃可能な最高段数及び仕様段数を表１に示す。
攻撃可能段数は、実際に存在する高階差分特性に基ずく判断である。しかし、264 以上の計算量は、現在の計算機の能力からかけ離れたものであり、暗号の使用上問題が発生するものではない。
暗号名
CIPHERUNICORN-E
MISTY1(FL 無)MISTY1
FEAL-NX
Hierocrypt-L1

攻撃可能段数−６段
5段
9段
3.5 段（=7 層）

必要選択平文数−
211237238237段関数計算量−2932752114
2117 *

仕様段数
16−8326（=12 層）*付録 D では 2137 の計算量であるが、部分総和法を使った場合、2117 と見積もれる。これは、文献[OSMMK]の結果を本報告書の計算量に換算したものである。

表１． 64 ビットブロック暗号の高階差分耐性

５．２

128 ビットブロック暗号

CIPHERUNICORN-A、Camellia、RC6、SC2000、MARS、Hierocrypt-3 の６暗号について調査し、結果は付録Ｅ、Ｆ、Ｇ、Ｈ、Ｉ、Ｄ及びＪに示した。提案暗号に関し、高階差分／補間攻撃の立場で問題のある暗号は、存在しない。256 ビット鍵を想定し、各暗号に対し、高階差分／補間攻撃の立場で、必要平文組数が 264 未満、計算量が 2256 未満で攻撃可能な最高段数及び仕様段数を表２に示す。攻撃可能段数は、実際に存在する高階差分特性に基ずく判断である。しかし、264 以上の計算量は、現在の計算機の能力からかけ離れたものであり、暗号の使用上問題が発生するものではない。

8暗号名
CIPHERUNICORN-A
Camellia(FL 無)
Camellia
RC6
SC2000MARS(core 部のみ)
Hierocrypt-3

攻撃可能段数−
8段6 段+FL
7段
8段8段
3.5 段（=7 層）

必要選択平文数−21425129227210237

段関数計算量
−2214
2255
2226
22252199
2200 *

仕様段数
16−2420221610（=20 層）[L94] X.Lay,”Higher Order Derivatives and Differential Cryptanalysis,”Communications
and Cryptography,pp.227-233,(1994)[JK97] T.Jakobsen and L.R.Kunudsen,"The Interpolation Attack on Block

Cipher.",FSE'97,LNCS 1267, pp.28-40,(1997)[SMK97]T.Shimoyama,

S.Moriai,

T.Kaneko

andS.Tsujii:"Improved

HigherOrder

Differential Attack and Its Application to Nyberg-Knudsen's Designed Block
Cipher",IEICE Trans.Vol.E82-A,No.9,pp.1971-1980,(1999)[MSK98] S.Moriai, T.Shimoyama and T.Kaneko,”Higher Order Differential Attack of a

CAST cipher,” FSE’98, LNCS 1372, pp.17-31 (1998)[DKR97] J.Daemen, L.R.Knudsen and V.Rijmen, ”The block cipher Square”, FSE97, LNCS

1267, pp.149-165, (1997)[A00] K.Aoki, "Practical Evaluation of Security against Generalized Interpolation

Attack.", IEICE Trans.Vol. E83-A, No. 1, pp.33-38,(2000)
大熊健司、佐野文彦、村谷博文、本山雅彦、川村信一 ブロック暗号 Hierocrypt-3
および Hierocrypt-L1 の安全性について ,SCIS2001,11A-4,(2001)[OSMMK]

9