KCipher-2 の安全性に関する評価

白石善明
名古屋工業大学

2011 年 1 月 31 日

目次
1

はじめに

2

2

KCipher-2
2.1 構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 初期化処理 . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
6

3

KCipher-2 の安全性
7
3.1 周期と線形複雑度 . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.1 DFSR の出力の表現 . . . . . . . . . . . . . . . . . 7
3.1.2 Interleaved sequence . . . . . . . . . . . . . . . . . 8
3.1.3 DFSR の出力の周期と線形複雑度の上限 . . . . . . 9
3.2 識別攻撃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2.1 Coppersmith らの識別攻撃 . . . . . . . . . . . . . . 9
3.2.2 渡辺らの識別攻撃 . . . . . . . . . . . . . . . . . . . 10
3.2.3 渡辺らの識別攻撃の KCipher-2 への適用 . . . . . . 11
3.3 相関攻撃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3.1 Siegenthaler の相関攻撃 . . . . . . . . . . . . . . . 14
3.3.2 Chepyzhov らの相関攻撃 . . . . . . . . . . . . . . . 15
3.3.3 Chepyzhov らの相関攻撃の KCipher-2 への適用 . . 17
3.4 TMTO 攻撃 . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4.1 Babbage, Golic の TMTO 攻撃 . . . . . . . . . . . . 18
3.4.2 Biryukov らの TMTO 攻撃 . . . . . . . . . . . . . . 19
3.4.3 Biryukov らの TMTO 攻撃の KCipher-2 への適用 . 20
3.5 代数攻撃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.5.1 Courtois らの代数攻撃 . . . . . . . . . . . . . . . . 20
3.5.2 Courtois の一般化した代数攻撃の KCipher-2 への適用 21
3.5.3 Billet らの代数攻撃の KCipher-2 への適用 . . . . . 22
3.6 GD 攻撃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.6.1 提案者らの一般化した GD 攻撃の KCipher-2 への適用 24
3.6.2 提案者らの GD 攻撃の KCipher-2 への適用 . . . . . 25
3.7 関連鍵/選択 IV 攻撃 . . . . . . . . . . . . . . . . . . . . . 25
3.8 統計的性質 . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4

まとめ

27

1

1

はじめに

KCipher-2 は，SASC2007 において K2 という名前（商標上の理由でKCipher-2 に変更）で最初のバージョン [1] が示され，後に，SECRYPT2007
において K2 v2.0 という名前で初期化処理等を修正したバージョン [2] が示されている．32 ビットワードの FSR（feedback shift register）のフィー
ドバック関数に対して DFC（dynamic feedback control）を行うというソ
フトウェア実装を想定した同期式ストリーム暗号である．IV サイズは 128
ビット，鍵サイズは 128 ビット，192 ビット，256 ビットの中から選択することができ，キーストリームとして 1 サイクルあたり 32 ビットワード
を 2 つ出力する．
KCipher-2 は，32 ビットワード単位の演算と FSR に対するフィードバッ
ク関数の DFC 機構により，キーストリーム出力を効率化するとともに，
キーストリーム出力の線形関係を特定困難にしている．さらに，ストリー
ム暗号 SNOW2.0[23] の FSM（ﬁnite state machine）を 2 つ結合した構造の非線形関数を有しており，キーストリーム出力の代数次数を増加させている．
KCipher-2 の安全性の議論は，KCipher-2 の提案論文 [1, 2] および第三者評価書 [3, 4] によるものが主であるが，現在，脆弱性は発見されていな
い．本報告では，提案論文および第三者評価書の内容をもとに，DFC 機
構により制御される FSR の出力の周期と線形複雑度，KCipher-2 の識別
攻撃，相関攻撃，代数攻撃，タイムメモリトレードオフ（TMTO）攻撃，
推測決定（GD）攻撃，関連鍵/選択 IV 攻撃，KCipher-2 の出力の統計的性質について確認したことをまとめる．
なお，ストリーム暗号では攻撃者が意図したキーストリームを選択的に観測することが一般に困難であり，ブロック暗号の選択平文攻撃の一つである差分攻撃をそのまま適用できないため，これに類似する攻撃として関連鍵/選択 IV 攻撃を位置づけている．
以降，KCipher-2 に関する議論は，K2 v2.0[2] を想定する．

2

KCipher-2

2.1

構造

KCipher-2 は，図 1 のように，2 個の FSR（FSR-A ,FSR-B）と，4 個の内部レジスタ（R1, R2, L1, L2）を有する非線形関数と，DFC から構成
2

図 1: KCipher-2 の構造されている．FSR-A は 5 段のレジスタを，FSR-B は 11 段のレジスタを持ち，各レジスタのサイズは 32 ビットである．R1, R2, L1, L2 のレジス
タのサイズはそれぞれ 32 ビットである．FSR-A は固定のフィードバッ
ク関数により状態遷移し，FSR-B は FSR-A の出力を受ける DFC によりフィードバック関数が制御される．非線形関数は，FSR-A の At , At+4 と，
FSR-B の Bt , Bt+4 , Bt+9 , Bt+10 を入力し，キーストリームとして ztL , ztH を出力する．
FSR-A のフィードバック関数 fA (x) と FSR-B のフィードバック関数
fB (x) は，それぞれ次のように書かれる．

fA (x) = α0 x5 + x2 + 1,
fB (x) = (α1cl1t + α21−cl1t − 1)x11 + x10 + x5 + α3cl2t x3 + 1.
cl1t , cl2t は，DFC の出力であり，次のような値である．ただし，Ax [y] は，3

図 2: 非線形関数

FSR-A の x 番目のレジスタの y 番目のビット値とする．
cl1t = At+2 [30], cl2t = At+2 [31].
α0 , α1 , α2 , α3 は，それぞれ次の多項式の根とする．
x4 + β 24 x3 + β 3 x2 + β 12 x + β 71 ∈ GF (28 )[x],x4 + γ 230 x3 + γ 156 x2 + γ 93 x + γ 29 ∈ GF (28 )[x],x4 + δ 34 x3 + δ 16 x2 + δ 199 x + δ 248 ∈ GF (28 )[x],x4 + ζ 157 x3 + ζ 253 x2 + ζ 56 x + ζ 16 ∈ GF (28 )[x].
β, γ, δ, ζ は，それぞれ次の多項式の根とする．
x8 + x7 + x6 + x + 1 ∈ GF (2)[x],x8 + x5 + x3 + x2 + 1 ∈ GF (2)[x],x8 + x6 + x3 + x2 + 1 ∈ GF (2)[x],x8 + x6 + x5 + x2 + 1 ∈ GF (2)[x].
4図 3: Sub() の構造

ここで，演算単位の 4 バイト（32 ビット）の値は，Yi ∈ GF (28 ), i =0, 1, 2, 3 により，次のように表す．ただし，Y3 を上位バイトとする．

Y = Y3 α03 + Y2 α02 + Y1 α0 + Y0 .
1 バイトの値は，yi ∈ GF (2), i = 0, 1, · · · , 7 により，次のように表す．ただし，y7 を上位ビットとする．
y = y7 β 7 + y6 β 6 + · · · + y1 β + y0 .
非線形関数は，図 2 のように，キーストリームを計算する部分と，内部レジスタを更新する部分から成る．キーストリーム Zt = (ztH , ztL ) は，次のように計算される．

ztL = Bt + R2t + R1t + At+4 ,ztH = Bt+10 + L2t + L1t + At .
内部レジスタ R1, R2, L1, L2 は，次のように更新される．

R1t+1 = Sub(L2t + Bt+9 ),R2t+1 = Sub(R1t ),L1t+1 = Sub(R2t + Bt+4 ),L2t+1 = Sub(L1t ).
5

Sub() は，図 3 のように，8 ビット入力-8 ビット出力の S-box と，32 ビッ
ト入力-32 ビット出力の Mix Column から成る．これらは，ブロック暗号
AES[24] の S-box と Mix Column と同じものである．

2.2

初期化処理

KCipher-2 の初期化処理は，key loading step と internal state initialization step の 2 つに分けられる．
key loading step では，key scheduling algorithm により，128/ 192/256
ビット初期化鍵と，128 ビットの初期化ベクトル (IV) から，内部初期状態を生成する．key scheduling algorithm は，ブロック暗号 AES[24] のround key generation function と同じであり，128/192/256 ビットの初期化鍵を 384 ビットに拡張する．例えば，128 ビットの初期化鍵 IK =(IK0 , IK1 , IK2 , IK3 ) に対しては，次のようになる．ただし，0 ≤ i ≤ 11とする．
Ki = IKi , 0 ≤ i ≤ 3,
Ki = Ki−4 ⊕ Ki−1 , i ̸= 4n,
Ki = Ki−4 ⊕ Sub((Ki−1 << 8) ⊕ (Ki−1 >> 24))
⊕Rcon(i/4 − 1), i = 4n,
Rcon[i] = (ximod x8 + x4 + x3 + x + 1,

0x00, 0x00, 0x00), x = 0x02.
internal state initialization step では，Ki , i = 0, 1, · · · , 11 と IV =(IV0 , IV1 , IV2 , IV3 ) により，次のように内部状態を初期化する．
Am = K4−m , m = 0, 1, · · · , 4, B0 = K10 , B1 = K11 ,B2 = IV0 , B3 = IV1 , B4 = K8 , B5 = K9 , B6 = IV2 ,B7 = IV3 , B8 = K7 , B9 = K5 , B10 = K6 .
そして R1, R2, L1, L2 を 0x00 に設定して，24 サイクル動かして，内部状態を更新する．ただし，Aj+4 , Bj+10 は次のように更新する．
L,
Aj+4 = α0 Aj−1 ⊕ Aj+2 ⊕ zj−1cl1

1−cl1j−1− 1)Bj−1 ⊕ Bj
cl2j−1H⊕Bj+5 ⊕ α3.
Bj+7 ⊕ zj−1

Bj+10 = (α1 j−1 + α2

6

キーストリームを 264 ビット（258 サイクル）出力すると，再初期化として，上記の処理が実行される．

3

KCipher-2 の安全性

3.1

周期と線形複雑度

第三者評価書 [3] では，DFC によりフィードバック関数が制御される
FSR（DFSR）の出力の周期と線形複雑度について，以下のように議論されている．
まず，DFSR の出力を定式化し（3.1.1 節），次に，interleaved sequenceの定義とこれに関する補題を示し（3.1.2 節），そして，DFSR の出力をinterleaved sequence と見なして周期と線形複雑度の上限を明らかにしている（3.1.3 節）．

3.1.1

DFSR の出力の表現

DFC によりフィードバック関数が制御される FSR-B の出力 si (t) は，次のように書ける．ただし，時刻 t の FSR-B の出力を b(t)，FSR-A の周期
を lA ，FSR-A の段数を nA とおく．
si (t) = b(lA t + i),lA = 232nA − 1, t ≥ 0, i = 0, 1, · · · , lA − 1.
FSR-B の出力を b(lA t + i) から b(lA (t + 1) + i) に変化させる遷移行列
Mi は，次のように書ける．ただし，FSR-B の状態を 1 つ進める遷移行列
を B00 , B01 , B10 , B11 ，FSR-B の段数を nB ，GF (232 ) 上の nB 次正方行列の集合を MnB (GF (232 )) とする．
Mi =

lA
∏

(i)

Bk ∈ MnB (GF (232 )),k=1(i)
Bk ∈ {B00 , B01 , B10 , B11 }.

ここで，si (t) は，次のように書き直すことができる．ただし，FSR-Bの出力を得るための線形関数を Π()，時刻 t の FSR-B の状態を B(t) =7

{b(t), b(t + 1), ..., b(t + nB − 1)} とする．
si (t) = b(lA t + i) = Π(B(lA t + i))= Π(Mit B(i)) = ΠMit B(i).
FSR-A の出力により FSR-B のフィードバック関数が制御されることから，si (t), i = 0, 1, · · · , lA −1 における状態遷移と，si (t+1), i = 0, 1, · · · , lA −1 における状態遷移は同じであり，次の関係が成り立つ．
Mi+1 = (B1 )−1 Mi B1 .
(i)

(i)

∑
Mi の特性多項式を ci (x) = nk=0 ck xk とおくと，次のような関係が成り立つ．すなわち，Mi は全て同じ特性多項式である．
ci (x) = cj (x), 0 ≤ {i, j} ≤ lA − 1.
また，si (t), t = 0, 1, · · · について，次のような式が成り立つ．c(x) の次数が n であることから linear span は n となる．
n∑

ck si (t + k) =

k=0

=

n
∑
k=0
n
∑

ck Π(B((t + k)lA + i))
ck ΠMit+k B(i)

k=0

3.1.2

n
∑

ck Mik B(i)

=

ΠMit

=

k=0
t
ΠMi c(Mi )B(i) = 0.

Interleaved sequencel を正整数とし，次数 n の GF (q) 上の多項式を f (x), f (0) ̸= 0，GF (q)上の系列を u = {u(t)}, t = i l + j, i = 0, 1, · · · , j = 0, 1, · · · , l − 1 とする．j = 0, 1, · · · , l − 1 について，uj = {u(i l + j)}i>=0 が f (x) で生成されるとき，u を GF (q) 上の interleaved sequence，uj を u の component
sequence と呼び，次の補題が示されている．
補題 1[5]：u は f (x) と l で作られる GF (q) 上の interleaved sequence とし，h(x) は GF (q) 上の u の最小多項式とする．このとき，1)linear span

8

が高だか n l であるためには，h(x) は f (xl ) を割り切る，2)u の系列の周期は ord(f )l を割り切る．
この補題は，interleaved sequence すなわち si (t) の周期と線形複雑度の上限（周期の上限は ord(f ) l，線形複雑度の上限は n l）を示している．

3.1.3

DFSR の出力の周期と線形複雑度の上限

si (t) は，GF (232 ) 上の interleaved sequence であり，l = lA , f (x) = c(x)（f (x) の次数は最大 352）であることから，周期の上限は (2352 −1)(2160 −1)
また線形複雑度の上限は 352(2160 − 1) となる．
以上のように，第三者評価書 [3] において，DFC によりフィードバッ
ク関数が制御される FSR-B の出力の周期と線形複雑度の上限が示されている．下限については現在明らかにされておらず，第三者評価書 [4] において，実験により短い周期，小さな線形複雑度が存在しないことが述べられている．また，FSR-A の出力の周期が 2160 − 1 であることから，
KCipher-2 のキーストリームは，再初期化を実施する 264 ビットよりも十分長い周期が得られることが期待できると述べられている．

3.2

識別攻撃

KCipher-2 の提案論文 [2] では，キーストリームを真の乱数と区別する
識別攻撃について，以下のように議論されている．
識別攻撃の基本的なアイデアは Coppersmith らの攻撃 [6] （3.2.1 節）に基づいている．SNOW 2.0 に対する識別攻撃として渡辺らの攻撃 [7, 8]（3.2.2 節）が挙げられており，これを KCipher-2 に適用した結果（3.2.3
節）が述べられている．

3.2.1

Coppersmith らの識別攻撃

提案論文 [2] で記されている識別攻撃の基本的なアイデアは，ブロック暗号に対する線形解読法における distinguisher の構成法を利用した Coppersmith らの識別攻撃 [6] に基づいている．

9

アルゴリズムを線形パートと非線形パートに分割して，線形パートの関係式を次のように書く．
⊕
ϕ(s, t) =cj st+j = 0.
(1)j

非線形パートについては，最良近似を探索して，そこで得られた近似式を次のように書く．ただし，左辺を f (s, t)，右辺を g(z, t) とおく．
⊕⊕
Γi st+i =Γ′t zt .
(2)
ti

ここで，式 (1),(2) から，次のようなキーストリームからなる線形近似を構成できる．
⊕0 =Γi ϕ(s, t + i)i=⊕

cj f (s, t + j)

j

=

⊕

cj g(z, t + j).

(3)j

式 (3) を distinguisher として用いると，識別攻撃を実施できるというもの
である．

3.2.2

渡辺らの識別攻撃

前節の改良版として，SNOW 2.0 を想定した渡辺らの識別攻撃 [7, 8] が示されており，提案論文 [2] では，KCipher-2 に対してこれが適用されている．
FSM の線形近似が次のような式で与えられていると仮定する．
⊕⊕(4)
Γi st+i =Γ′j zt+j .
ij

一方，LFSR の内部状態 s は，任意のマスク値 Γ において，次のような関係式を満たす．
⊕Γ(
cj st+j ) = 0.
j10

これは，次のような式で書き直すことができる．
⊕(Γcj )st+j = 0.

(5)j

ここで，マスク値 Γci について，式 (4) が大きな偏差で成り立つならば，
式 (5) も大きな偏差を持つ．このとき，式 (4),(5) から，distinguisher として，次のような式が得られる．ただし，式 (4) の右辺を g ′ (z, t) とおく．
⊕
cj g ′ (z, t + j) = 0.
(6)j

式 (4) の偏差は piling up lemma より次のような式で書くことができる．
ただし，ϵi は FSM 内の線形近似の偏差とする．

ϵFSM (Γ) = 2n−1

n
∏

ϵi .

i=1

式 (6) は式 (4) から成り，その偏差は次のような式で書くことができる．

ϵ = 2m−1

m∏ϵFSM (Γ′′i ).

i=1

3.2.3

渡辺らの識別攻撃の KCipher-2 への適用

前節で示した渡辺らの識別攻撃 [7, 8] を KCipher-2 に適用した結果が提案論文 [2] では示されている．
ここでは，議論を簡単にするために，DFC の出力ビットを cl1t = cl2t =
0 と固定した場合を想定している．
FSR-A のフィードバック関数と FSR-B のフィードバック関数から，内部状態に関する関係式は，次のように書ける．
⊕
ϕ1 (A, t) =c1j At+ii= α0 At ⊕ At+3 ⊕ At+5 = 0,⊕
ϕ2 (B, t) =c2j Bt+jj= α2 Bt ⊕ Bt+1 ⊕ Bt+6 ⊕ Bt+8 ⊕ Bt+11 = 0.

11

この 2 つの式を組み合わせると，任意のマスク値 Γ において，次のような関係式が得られる．
⊕
Γϕ(s, t) =
Γc1j ϕ2 (s, t + j)j=⊕

Γcj st+jj= Γα0 α2 st ⊕ Γα2 (st+3 ⊕ st+5 )⊕Γα0 (st+1 ⊕ st+6 ⊕ st+8 ⊕ st+11 )⊕st+4 ⊕ st+6 ⊕ st+9 ⊕ st+13 ⊕ st+14 ⊕ st+16 = 0.

(7)

KCipher-2 の FSM の 2 ラウンド出力の線形マスクは図 4 のようになり，
線形近似式は次のように書ける．
⊕⊕
Γi st+i =Γ′j zt+jijHL= ΓztH ⊕ ΛztL ⊕ Φzt+1⊕ Ψzt+1.

(8)

ここで，マスク値 Γcj について，式 (8) が大きな偏差で成り立つならば，式 (7) も大きな偏差を持つ．よって，式 (7),(8) を組み合わせると，
distinguisher として，次のような式が得られる．ただし，式 (8) の右辺を
g ′ (z, t) とおく.
⊕
H
H
H
H
H
cj g ′ (z, t + j) = Γ{α0 α2 ztH ⊕ α2 (zt+3⊕ zt+5) ⊕ α0 (zt+1⊕ zt+6⊕ zt+8
j
H
H
H
H
H
H
H
⊕zt+11) ⊕ zt+4⊕ zt+6⊕ zt+9⊕ zt+13⊕ zt+14⊕ zt+16}
L
L
L
L
L⊕Λ{α0 α2 ztL ⊕ α2 (zt+3⊕ zt+5) ⊕ α0 (zt+1⊕ zt+6⊕ zt+8
L
L
L
L
L
L
L
⊕zt+11) ⊕ zt+4⊕ zt+6⊕ zt+9⊕ zt+13⊕ zt+14⊕ zt+16
}
H
H
H
H
H
H
⊕Φ{α0 α2 zt+1
⊕ α2 (zt+4⊕ zt+6) ⊕ α0 (zt+2⊕ zt+7⊕ zt+9
H
H
H
H
H
H
H
}
⊕ zt+17⊕ zt+15⊕ zt+14⊕ zt+10⊕ zt+7) ⊕ zt+5⊕zt+12
L
L
L
L
L
L⊕Ψ{α0 α2 zt+1
⊕ α2 (zt+4⊕ zt+6) ⊕ α0 (zt+2⊕ zt+7⊕ zt+9
L
L
L
L
L
L
L
⊕zt+12) ⊕ zt+5⊕ zt+7⊕ zt+10⊕ zt+14⊕ zt+15⊕ zt+17} = 0.

式 (8) がマスク値 Γcj について大きな偏差で成り立つものが発見された場
合，上記の distinguisher により識別攻撃が実施できるが，現在，そのようなマスク値は見つかっていない．

12

図 4: KCipher-2 の 2 ラウンド出力の線形マスク

以上のように，DFC の出力ビットを cl1t = cl2t = 0 のように固定した場合において，渡辺らの攻撃 [7, 8] の成立は困難であると提案論文 [2] では述べられている．また，cl1t = cl2t = 0 のような条件は，確率 2−30 で成立するため，このことから，DFC の効果として，識別攻撃の計算量を260 倍にすることが述べられている．

3.3

相関攻撃

KCipher-2 の提案論文 [2] では，キーストリームを観測して，遷移する
内部状態とキーストリームの相関関係から，内部状態を推定する相関攻撃について，以下のように議論されている．
相関攻撃の基本的なアイデアは Siegenthaler の攻撃 [9] （3.3.1 節）に基づいている．代表的な相関攻撃の一つである Chepyzhov らの攻撃 [11]（3.3.2 節）が挙げられており，これを KCipher-2 に適用した結果（3.3.3節）が示されている．

13

図 5: 相関攻撃のモデル

3.3.1

Siegenthaler の相関攻撃

提案論文 [2] で記されている相関攻撃の基本的なアイデアは，Siegenthaler の相関攻撃 [9] に基づいている．
図 5 のように，LFSR の出力列は 2 元線形 [N, L] 符号の符号語，非線形関数の出力列は誤り確率 p = 1/2 + ϵ の BSC に符号語を入力したときの出力と見なす．ただし，N を LFSR の出力列の長さ，L を LFSR のフィードバック関数の次数とする．
非線形関数の出力列から LFSR の出力列（LFSR の内部状態）を求める
問題は，線形符号の復号問題として扱うことができる．ここでは，復号アル
ゴリズムの中で復号誤り確率が良好とされる ML(max-imum likelihood)decoding を適用する．
2 元線形 [N, L] 符号の符号語の集合を C，BSC に入力される送信語を
x̄，送信語に対する受信語を z とおくと，ML-decoding は次のように定義
される．
def

x¯0 = minx∈C dist(x, z), dist(x, z) =N∑

x i ⊕ zi .

i=1

また，この復号誤り確率は，次のように定義される．
def

Pe (p) = P r(x¯0 ̸= x̄).
BSC の容量を C = 1 − H(p) とすると，符号化レート R = L/N が
R < C を満たすとき，次の式が成立する [9, 10]．ただし，Pe (p) の期待値
を E[Pe (p)]，ランダムコーディング指数を τ (R) > 0 とする．
E[Pe (p)] < 2−τ (R)N , τ (R) = τ (R, p).
14

ML-decoding の復号誤り確率が 0 に近づく，すなわち攻撃が成立するための条件は，次のように書ける．
N > n0 , n0 = ⌈L/C(p)⌉, C(p) ≈ ϵ2 2/(ln2).
ML-decoding を利用した相関攻撃の計算量は，LFSR の初期値を全数探索することから，O(2L L/C(p)) に従う．
3.3.2

Chepyzhov らの相関攻撃

前節の改良版として，計算量のオーダを O(2L L/C(p)) から O(2αL L/C(p)), α <1 へ減少させる Chepyzhov らの相関攻撃 [11] が示されており，提案論文[2] ではこれを KCipher-2 に適用している．
LFSR の出力列 x = {xi }N
i=1 とおくと，次のような式が書ける．ただし，
LFSR のフィードバック関数を g(D) = c0 + c1 D + · · · cL DL (c0 = cL = 1)とする．

cL x1 + cL−1 x2 + · · · + c1 xL + c0 xL+1 = 0,cL x2 + cL−1 x3 + · · · + c1 xL+1 + c0 xL+2 = 0,..
.
cL xN −L + cL−1 xN −L+1 + · · · + c1 xN −1 + c0 xN = 0.
次のような (N − L) × N のパリティ検査行列を定義すると，全ての符号語 x に関して，H(x1 , x2 , · · · , xN )T = 0 が明らかに成り立つ．

cL cL−1 cL−2 · · ·c00 ··· 0
0cL cL−1 · · ·c1c0 · · · 0 


H=
.
... ... ... ... ...
0
0
0

0

0

...

cL

cL−1 · · ·c1c0

さらに，次のような式が書ける．

xL+1 = h1L+1 x1 + h2L+1 x2 + · · · + hLL+1 xL ,xL+2 = h1L+2 x1 + h2L+2 x2 + · · · + hLL+2 xL ,..
.
xi = h1i x1 + h2i x2 + · · · + hLi xL ,..
.
xN = h1N x1 + h2N x2 + · · · + hLN xL .
15

hi (D) = h1i + h2i D + · · · hLi DL−1 とおくと，次のような式が明らかに成り立つ．
hi (D) = Di−1 mod g(D), i = 1, 2, · · · N.
符号 C の L × N 生成行列は次のように書くことができ，左側から (x1 , x2 , · · · , xL )を掛けることで，符号 C の符号語 x が得られる．
 1
h1 h12 · · · h1N
 h2 h2 · · · h2 
2
N
 1
G= .
.
.

 .
···

hL1 hL2 . . . hLN
ここで，次のような関係を満たす i，j を探索する．ただし K < L と
する．

hk+1
= hk+1, hk+2= hk+2, · · · , hLi = hLj , 1 ≥ i ̸= j ≥ N.
ijij
探索した i，j から，次のような関係が得られる．
K
xi + xj = (h1i + h1j )x1 + (h2i + h2j )x2 + · · · + (hKi + hj ).

ペア (i，j) の集合が得られたとき，次のような [N2 , K] 符号 C2 の符号
語 x2 を定義する．

(X1 , X2 , · · · , XN2 ) = (xi1 + xj1 , xi2 + xj2 , · · · , xiN2 + xjN2 ).
符号 C2 の K × N2 生成行列は，次のように書くことができ，左側から(x1 , x2 , · · · , xK ) を掛けることで，符号語 x2 が得られる．

h1i1 + h1j1 h1i2 + h1j2 · · · h1iN + h1jN
2
2
 2

 hi1 + h2j1 h2i2 + h2j2 · · · h2iN2 + h2jN2 .
G2 = 
..


.
···


K
K
K
K
K
K
hi1 + hj1 hi2 + hj2 · · · hiN + hjN22

また，符号語 x2 に対して，次のような受信語 z2 を定義する．

(Z1 , Z2 , · · · , ZN2 ) = (zi1 + zj1 , zi2 + zj2 , · · · , ziN2 + zjN2 ).
符号 C の誤り系列を (e1 , e2 , · · · , eN ) とすると，符号 C2 の誤り系列は次のように書ける．

(E1 , E2 , · · · , EN2 ) = (ei1 + ej1 , ei2 + ej2 , · · · , eiN2 + ejN2 ),P r(Em = 1) = P r(eim + ejm = 1) = p2 = 1/2 − 2ϵ2 .
16

このとき，2K 通りの (x1 , x2 , · · · , xK ) のパターンに関して，符号語 x2 を構成して，受信語 z2 とのハミング距離を計算することで，O(2K K/C(p2 ))で相関攻撃を適用できる．
LFSR の初期値のうち K ビットを推定して，残りの L − K ビットは既存の他の復号アルゴリズムにより求める場合，攻撃が成立するための N2の条件は次の式で書ける．

N2 > ⌈K/C(p2 )⌉, C(p2 ) ≈ 4ϵ4 2/ln2.
m
この攻撃は hmi = hj , K ≥ m ≥ L, 1 ≥ i ̸= j ≥ N を満たす 2 個のパリティ検査式を探索するものであるが，さらに H 個のパリティ検査式を探索するように一般化したものが示されている．このとき，パリティ
検査式を探索する前処理の計算量は N ⌈(H−1)/2⌉ ，パリティ検査式の個数は
N H 2K−L /H!，主処理の計算量は 2K · N H 2K−L /H!，攻撃が成立するための出力列の長さは N ≈ 1/4(2KH!ln2)1/H ϵ−2 2(L−K)/H となる．

3.3.3

Chepyzhov らの相関攻撃の KCipher-2 への適用

前節で示した Chepyzhov らの相関攻撃 [11] を KCipher-2 に適用した結果が提案論文 [2] では示されている．
KCipher-2 は，FSR-A の出力により FSR-B のフィードバック関数が制御されていることから，FSR-B の出力に関するフィードバック関数を特定することが難しい．そこで，cl1t ，cl2t を一定の値で固定して，常時クロックを与える FSR-B の初期値を求める相関攻撃を想定し，また GF (232 ) 上の演
算を GF (2) 上の演算と見なして攻撃を適用する．N = 264 ，H = 9, K = 26
，L = 11 · 32 = 352 とした場合，前処理の計算量は 2256 ，パリティ検査式の個数は 2240 ，主処理の計算量は 2266 である．常時クロックする FSR-Bの出力列と非線形関数の出力列の相関確率は p = 1/2 + 2−13 という値が得られており [2]，攻撃が成立するための出力列の長さは N ≈ 262 である．
以上のように，FSR-B のフィードバック関数を固定して，GF (2) 上の演算を仮定したとしても，Chepyzhov らの攻撃の計算量は鍵空間の全数探索よりも大きくなり，攻撃が困難であると提案論文 [2] では述べられている．また，FSR-B のフィードバック関数の DFC と GF (232 ) 上の演算を想定する場合は，相関値の計算量や復号アルゴリズムの計算量が増大し，相関攻撃に用いる線形式を特定できず，さらに攻撃は困難になることが述べられている．

17

3.4

TMTO 攻撃

KCipher-2 の提案論文 [2] では，キーストリームの部分系列と内部状態の対応表に基づき，キーストリームを観測して内部状態を推定するタイ
ムメモリトレードオフ（TMTO）攻撃について，以下のように議論されている．
TMTO 攻撃の基本的なアイデアは Babbage，Golic の攻撃 [12, 13]（3.4.1
節）に基づいている．代表的な TMTO 攻撃の一つである Biryukov らの攻撃 [14, 15]（3.4.2 節）が挙げられており，これを KCipher-2 に適用した結果（3.4.3 節）が示されている．

3.4.1

Babbage, Golic の TMTO 攻撃提案論文 [2] で記されている TMTO 攻撃の基本的なアイデアは，Babbage, Golic の攻撃 [12, 13] に基づいている．
内部状態の組み合わせを N ，観測したキーストリーム列の個数を D，必要とするメモリの容量を M ，前処理の時刻複雑度を P ，主処理の時刻複雑度を T とする．
log N ビットの内部状態を log N ビットのキーストリームに置き換える
関数 f を次のように定義する．

f : log N bit state− > log N bit keystream, M = N/D.
ランダムに内部状態 s を選択して，内部状態とキーストリームのペア(s, f (s)) から成るテーブルを作る．テーブルは，ペア (s, f (s)) のうち f (s)によりソートしておくものとする．
キーストリーム列を D 個だけ観測したとき，それぞれにおいて，ペア(s, f (s)) のうち f (s) に一致するものを探す．このとき，バースデイパラ
ドクスより，高い確率で該当のエントリーを見つけることができる．もしも一致するものが見つかった場合，対応する s が攻撃者が求める内部状態となる．
ここで，テーブルのエントリーの個数 M については M = N/D という関係が得られており，テーブルを探索する回数は多くとも D 回であることから時刻複雑度 T については T = D の関係が得られる．したがって，
時刻とメモリのトレードオフの式は次のようになる．

T M = N, P = M, 1 ≤ T ≤ D.
18

3.4.2

Biryukov らの TMTO 攻撃

前節の改良版として，ブロック暗号に対する攻撃 [16] をストリーム暗号に適用した Biryukov らの攻撃 [14, 15] が示されており，提案論文 [2] ではこれを KCipher-2 に適用している．
log N ビットの内部状態を log N ビットのキーストリームに置き換える関数 f, h を定義する．

f, h : log N bit state− > log N bit keystream, N = mt2 .
内部状態 si,0 を選択して，次の式を t 回繰り返し，si,t を計算して，ペア (si,0 , si,t ) を得る．

si,j+1 = g(si,j ), g = h ◦ f.
関数 h を t 通りランダムに選択し，内部状態 si,0 を m 通りランダムに選択して，ペア (si,0 , si,t ) のテーブルを t/D 個作成する．それぞれのテー
ブルは，ペア (si,0 , si,t ) について si,t でソートしておくものとする．
D 個の出力列 rl , l = 0, 1, ..., D − 1 が得られたとき，t/D 個のテーブルの中にあるペア (si,0 , si,t ) から，次の関係を満たすものを探す．

g x (h(ri )) = (g ◦ · · · ◦ g)(h(ri ))= si,t .
バースデイパラドクスより，高い確率で該当のエントリーを見つけることができる．この関係が見つかった場合，次のように，出力列 ri に対する内部状態 g t−x−1 (si,0 ) が得られる．

(g x ◦ h)(ri ) = g x (h(ri ))= si,t= (g x ◦ h)(si,0 )= (g x ◦ g ◦ g t−x−1 )(si.0 )= (g x ◦ h)(f (g t−x−1 (si,0 ))).
t/D 個のテーブルを用いており，それぞれのテーブルは m 個のエントリーを持つことから，M = mt/D が得られる．D 個の出力列に一致する
内部状態を探索する際，t/D 個のテーブルにそれぞれ t 回の繰り返し処理を行うので，T = D(t/D)t = t2 が得られる．したがって，時刻とメモリのトレードオフの式は次のようになる．
T M 2 D2 = N 2 , P = N/D, 1 ≤ D2 ≤ T.
19

3.4.3

Biryukov らの TMTO 攻撃の KCipher-2 への適用

前節で示した Biryukov らの TMTO 攻撃 [14, 15] を KCipher-2 に適用した結果が提案論文 [2] では示されている．
内部状態のサイズを s = 512 とおくと，N = 2s = 2512 ，D = 2s/4 = 2128
，P = 23s/4 = 2384 ，T = M = 2s/2 = 2256 のような関係が得られる．
以上のように，鍵サイズを k = 128，IV サイズを v = 128 とおくと，内部状態サイズ s は s = 512 ≥ 2(k + v) = 512 を満足しており，十分な空間を有していると提案論文 [2] では述べられている．また，攻撃の計算量
は T = 2256 であることから，鍵空間の全数探索よりも大きく，攻撃は困難であると述べられている．

3.5

代数攻撃

KCipher-2 の提案論文 [2] では，内部状態とキーストリームに関する関係式を構成し，観測したキーストリームを代入し，これを解くことで内部状態を再構成する代数攻撃について，以下のように議論されている．
代数攻撃の基本的なアイデアは Courtois らの攻撃 [17, 18]（3.5.1 節）に基づいている．一般化した代数攻撃として Courtois の攻撃 [20] とこれをKCipher-2 に適用した結果（3.5.2 節）が示され，また SNOW 2.0 に対する代数攻撃として Billet らの攻撃 [21] とこれを KCipher-2 に適用した結果（3.5.3 節）が示されている．

3.5.1

Courtois らの代数攻撃

提案論文 [2] で記されている代数攻撃の基本的なアイデアは，Courtois
らの攻撃 [17, 18] に基づいている．
内部状態を s0 , s1 , · · · , sn−1 ，キーストリームを y 0 , y 1 , · · · , y M −1 とおい
たとき，次のような内部状態とキーストリームの次数 d の関係式 Q が得られる場合を考える．

Q(s0 , s1 , · · · , sn−1 , y 0 , y 1 , · · · , y M −1 ) = 0.
ここで，内部状態の線形遷移関数を L，内部状態の初期値を K とおくと，連続する M 個の内部状態について，次のような関係式が成り立つ．

Q(Lt (K)0 , Lt (K)1 , · · · , Lt (K)n−1 , y t , y t+1 , · · · , y t+M −1 ) = 0.
20

キーストリーム y t , y t+1 , · · · , y t+M −1 を観測して，これらを上記の式に代入すると，内部状態の初期値に関する多次多変数の連立方程式が得られる．連立方程式の解を得る方法としては，Buchberger アルゴリズム，XL[17]，Linearization[18] などが挙げられる．
例えば Linearization では，n ビットの内部状態を想定すると，それぞ( )れの方程式には次数 d 以下の T ≈ nd , d ≤ n/2 個の単一項が存在し，こ( )れらを変数と見なす．約 nd + M ビットのキーストリームが得られると，( )連続する M ビットから R = nd , R > T 個の方程式が得られ，これにガウスの消去法を適用すると，計算量 T ω , ω ≤ 2.376[19] で解が得られる．

3.5.2

Courtois の一般化した代数攻撃の KCipher-2 への適用

内部状態の線形遷移関数とメモリ付きコンバイナを有するストリーム暗号を想定した代数攻撃として，Courtois の攻撃 [20] が示されており，提案論文 [2] ではこれを KCipher-2 に適用した結果が述べられている．
線形の内部状態の遷移関数を L とおくとき，時刻 t の内部状態 st0 , st1 , · · · , stn−1
は，次のような式で書ける．

{st0 , st1 , · · · , stn−1 } = Lt ({s00 , s01 , · · · , s0n−1 }).
時刻 t の内部状態から k ビットを選択して，これらを xt0 , xt1 , · · · , xtk−1
とおくとき，コンバイナ F = (F1 , F2 ) を次のように書く．
t−1
t
t−1
(y0t , y1t , · · · , ym−1
) = F1 (xt0 , xt1 , · · · , xtk−1 , at−1
0 , a1 , · · · , al−1 ),t−1
t−1(at0 , at1 , · · · , atl−1 ) = F2 (xt0 , xt1 , · · · , xtk−1 , at−1
0 , a1 , · · · , al−1 ).
t−1
t−1
F1 に xt0 , xt1 , · · · , xtk−1 と内部メモリ at−1
0 , a1 , · · · , al−1 を入力することtで，キーストリーム y0t , y1t , · · · , ym−1が得られる．F2 に xt0 , xt1 , · · · , xtk−1 とt−1
a0t−1 , at−1
1 , · · · , al−1 を入力して，その出力を次の時刻の内部メモリの値とする．
このような構造に対し，次のような定理 1,2 が示されており，内部状態の初期値を得るための連立方程式の構成，Linearization による解の導出，
各手続きの計算量，パラメータ選択について議論されている．

定理 1[20]：F は K ビットの入力，l ビットのメモリ，m ビットの出力のコンバイナとする．d と M は次の不等式を満たす整数とする．
)
d (
∑
Mk
Mm
2
> 2M k+l .
i
i=0

21

このとき，M 個の連続する手続き/状態 (t, t + 1, · · · , t + M − 1) を考えると，xt に関する次数 d の方程式 R が存在する．
t+M −1−1
R(xt0 , · · · , xtk−1 , · · · , xt+M
, · · · , xk−1,0tt+M −1y0t , · · · , ym−1
, · · · , y0t+M −1 , · · · , ym−1
) = 0.

定理 2[20]：F は K ビットの入力，l ビットのメモリ，m ビットの出力のコンバイナとする．このとき，M = ⌈(l +1)/m⌉ 個の連続する手続き/状態(t, t+1, · · · , t+M −1) を考えると，これら手続き/状態について xt と y t のみを含む式が存在し，これは xt に関して次数 ⌈kM/2⌉ = ⌈k⌈(l +1)/m⌉/2⌉を持つ．
連立方程式の構成に要する計算量は，大まかに 2ω(M k+l) と見積もられて( )おり，T = nd ビットのキーストリームが与えられたとき，Linearization
により連立方程式を解く計算量は，T ω ≈ 2ωd log n と見積もられている．
これを KCipher-2 に対して適用すると，n = 5 · 32 + 11 · 32 = 512, l =4 · 32 = 128, k = 6 · 32 = 192, m = 2 · 32 = 64 であり，また定理 2 より，
M = ⌈(128 + 1)/64⌉ = 3, d = ⌈kM/2⌉ = 288 が得られ，連立方程式を構成する計算量と Linearization の計算量は鍵の全数探索の計算量よりも大
きくなる．

3.5.3

Billet らの代数攻撃の KCipher-2 への適用

KCipher-2 は FSR や非線形関数（FSM）の構造が SNOW 2.0[23] に近く，SNOW 2.0 の代数攻撃 [21] と同じアプローチを KCipher-2 に適用することが提案論文 [2] では試みられている．
DFC の出力ビット cl1t ，cl2t を一定の値で固定して FSR-B に常時クロッ
クを与え，GF (232 ) 上の加算を XOR で置換えた簡単化した KCipher-2 を想定している．
簡単化した KCipher-2 の構造から，次のような式が得られる．
R2t = R1t ⊕ At+4 ⊕ Bt ⊕ ztL , R1t−1 = Sub(R2t−2 ⊕ Bt+2 ),H).
R1t = Sub(L1t−1 ⊕ At−1 ⊕ Bt+8 ⊕ Bt+9 ⊕ zt−1

上記の式から Sub() を削除できると仮定した場合，次のような線形再22帰が得られる．

R2t = R2t−2 ⊕ At−1 ⊕ At+4 ⊕ Bt ⊕ Bt+2 ⊕ Bt+8
H
⊕ Bt+9 ⊕ zt−1
⊕ ztL ,

R1t = R2t−2 ⊕ At−1 ⊕ At+2 ⊕ Bt−2 ⊕ Bt+2 ⊕ Bt+8
HL
⊕ Bt+9 ⊕ zt−1
⊕ zt−2.

このとき，任意の時刻 t について，キーストリーム，FSR-A および FSRB のレジスタ，非線形関数の内部メモリを含む，次のような式を定義できる．

R2t = R20

R1t = R10t⊕

ϵit ziH

t
4
1
⊕
⊕
⊕
j L
k
ϵ t zjϵ t Ak0l=0 ϵlt Bl ,

i=0

j=0

t
⊕

t
⊕

i=0

ϵit ziH

k=0

ϵjt zjL

j=0

4⊕

ϵkt Ak1⊕0l=0 ϵlt Bl ,k=0

R2t = Sub(R1t−1 ) の関係を用いることで 2 次方程式を構成することができるが，上記のような Sub() の削除を仮定しなければ，このような式が得られないので，ここで想定する KCipher-2 への攻撃適用は困難である．
フルバージョンの KCipher-2 では，攻撃者はさらに各サイクルにおいて cl1t ，cl2t を推測する必要があり，M を連立方程式の中の非定数の単一項の個数，N を 1 サイクルの出力毎に得られる式の個数とすると，攻撃の計算量が 22 (⌈M/N ⌉ − 1) 倍になる．
以上のように，Courtois の代数攻撃 [20] の適用は，計算量の観点から
鍵の全数探索よりも困難であり，また Billet らの代数攻撃 [21] の適用は，KCipher-2 の非線形関数の構造から適用が困難であると提案論文 [2] では述べられている．

3.6

GD 攻撃

KCipher-2 の提案論文 [2] では，キーストリームを観測して，内部状態の推測と決定を繰り返し，再構成する推測決定（GD）攻撃について，以下のように議論されている．
提案者らが示す一般化した GD 攻撃とこれを KCipher-2 に適用した結果（3.6.1 節），および提案者らが示す KCipher-2 の構造に注目した GD
攻撃とこれを KCipher-2 に適用した結果（3.6.2 節）が示されている．
23

3.6.1

提案者らの一般化した GD 攻撃の KCipher-2 への適用

提案論文 [2] では，提案者らの一般化した GD 攻撃とこれを KCipher-2へ適用した結果が示されている．
ここでは，l ビットの内部状態から m ビットを抽出し，これをもとに n
ビットをキーストリームとして出力するストリーム暗号を想定している．
キーストリームの n ビットから内部状態の m − n ビットを推測してその他の n ビットを決定し，また内部状態の未推測，未決定の部分の値について，推測と決定を繰り返していく．
内部状態から一意に m ビットを選択，抽出できることを仮定して，上記の手続きを j 回繰り返したとき，推測または決定したビット数を vj とすると，推測すべき内部状態のサイズは (1 − ⌈vj /l⌉) となる．
攻撃における x 回目の手続きにおいて，既に推測または決定されたビット数を y(x) とおくと，次のような式が得られる．ただし，y(0) = 0 とする．
y(x) = (n2 − mn + lm)(1 − e−(m−n)x/l )/(m − n).
このとき，y(η) = l とすると，推測と決定に要する計算量 C は，次のよ
うな式で書くことができる．c は定数とする．ただし，推測と決定を繰り返して得られた内部状態は，そこから生成したキーストリームが，観測したキーストリームと一致するかどうかにより正当性を確認するが，この計算量は除いている．

C ≈ c · 2l−nη ,η ≈ 1/(m − n)lnm/n.
このような攻撃を KCipher-2 に適用すると，l = 5 · 32 + 11 · 32 + 4 · 32 =640, m = 6 · 32 + 2 · 32 = 256, n = 2 · 32 = 64 であることから，その計算量のオーダは O(2344 ) となる．
以上のように，提案者らが示した一般化した GD 攻撃を KCipher-2 に適用する場合，計算量のオーダは鍵の全数探索よりも大きくなることから，攻撃は成立しないことが提案論文 [2] では述べられている．また，KCipher2 に対する単純な GD 攻撃として，FSR-A のレジスタと NLF の内部レジ
スタを全て推測して，FSR-B のレジスタを全て決定するという攻撃があるが，計算量のオーダは O(2288 ) となり，攻撃が成立しないことも述べら
れている．

24

3.6.2

提案者らの GD 攻撃の KCipher-2 への適用

提案論文 [2] では，さらに，単純化した KCipher-2 を想定してた GD 攻
撃とこれを KCipher-2 へ適用した結果が示されている．
単純化した KCipher-2 は，各フィードバック関数の αi , i = 0, 1, 2, 3 を除いて，GF (232 ) 上の加算を排他的論理和で置き換えたものを想定している．
NLF の構造に注目すると，次のような式が得られる．
H
ztL ⊕ zt+4
= (Bt ⊕ Sub(R1t−1 )) ⊕ R1t⊕(Bt+14 ⊕ Sub(L1t+3 )) ⊕ L1t+4 .
上記の式の 5 つの要素を推測すると，例えば，Bt+14 や At+4 の値を決定できる．時刻 t を変化させ，少なくとも 10 個の要素を推測することで，O(2320 ) の計算量のオーダで，FSR の全ての要素を決定することができる．
また，NLF の 4 つのレジスタ R1, R2, L1, L2 の関係に注目すると，次のような式が得られる．

R2t+1 = Sub(R1t ), L1t+2 = Sub(R2t+1 ⊕ Bt+5 ),L2t+3 = Sub(L1t+2 ), R1t+4 = Sub(L2t+3 ⊕ Bt+12 ).
上記の式の R1t , Bt+5 , Bt+12 を推測すると，R2t+1 , L1t+2 , L2t+3 , R1t+4を決定できる．単純化した KCipher-2 から FSR-A を除いた場合，それぞれのサイクルにおいて，ztH ⊕ At と ztL ⊕ At+4 が得られる．このとき，6個の要素 R1t+1 , R1t+2 , L1t , L1t+1 , Bt+6 , Bt+7 を推測することで，計算量のオーダ O(2192 ) で，FSR-B の全ての要素を決定できる．
以上のように，単純化した KCipher-2 に対して，NLF の構造に注目した GD 攻撃では計算量のオーダが O(2320 ) となり，鍵の全数探索よりも大きくなるので攻撃が成立しないことが提案論文 [2] では述べられている．
また，NLF の 4 つのレジスタの関係に注目した GD 攻撃では，計算量のオーダが O(2192 ) となるが，フルバージョンの KCipher-2 では FSR-A の要素の他に DFC からの 2 ビットを推測する必要があり，GD 攻撃の適用は困難であると述べられている．

3.7

関連鍵/選択 IV 攻撃

KCipher-2 の提案論文 [2] では，一部だけ異なるような鍵/IV を用いてキーストリームを生成したときの内部状態の差分に基づいて鍵を推定す
25

る関連鍵/選択 IV 攻撃について，以下のように議論されている．
KCipher-2 では，初期化処理において，AES の鍵スケジューリングア
ルゴリズムを用いてラウンド鍵を作成して，これと IV を内部状態に設定
し，24 サイクルだけ内部状態を更新してラウンド鍵と IV を含む内部状態を撹拌している．
13 サイクル更新すると，ラウンド鍵と IV が内部状態全体に広がり，さらに 11 サイクル更新されると，ラウンド鍵と IV が攪拌され，鍵や IV に関する差分を観測できないため，関連鍵/選択 IV 攻撃に対して脆弱でな
いと述べられている．
鍵または IV の差分パスを探索するとき，攻撃者はキーストリームを計算する任意のラウンドにおいて内部状態の差分を観測できる必要がある
が，以上のように，初期化処理が十分に実施された場合，内部状態の差分の観測が困難になるため攻撃を適用できないことが主張されている．

3.8

統計的性質

KCipher-2 の提案論文 [2] および第三者評価書 [3] では，キーストリー
ムの統計的性質について，NIST 乱数検定（SP800-22）[22] を適用した結果が述べられている．
NIST 乱数検定では，任意の長さのビット列の乱数性を確認するための次のような項目の検定が含まれている．
• The Frequency Test
• Frequency Test Within a Block• The Runs Test
• Test for the Longest-Run-of-Ones in a Block• The Binary Matrix Rank Test
• The Discrete Fourier Transform (Spectral) Test
• The Non-overlapping Template Matching Test
• The Overlapping Template Matching Test
• Maurer’s Universal Statistical Test
26• The Lempel-Ziv Compression Test
• The Linear Complexity Test
• The Serial Test
• The Approximate Entropy Test
• The Cumulative Sums Test
• The Random Excursions Test
• The Random Excursions Variant Tests
KCipher-2 の最大 232 ビットのキーストリームに対して，NIST 乱数検定の全項目の検定をパスしたことが述べられている．
2008 年 12 月の改訂版で，The Lempel-Ziv Compression Test の除外，
The Discrete Fourier Transform (Spectral) Test の閾値の変更，評価ソフ
トおよび評価方法の変更があったが，これについては言及されていない．

4

まとめ

本報告では，KCipher-2 の安全性について，KCipher-2 の提案論文 [2]および第三者評価書 [3, 4] をもとに，DFC 機構により制御される FSR の
出力の周期，線形複雑度と，KCipher-2 の識別攻撃，相関攻撃，タイムメ
モリトレードオフ（TMTO）攻撃，代数攻撃，推測決定（GD）攻撃，関
連鍵/選択 IV 攻撃，統計的性質について確認した．
DFC 機構により制御される FSR（FSR-B）の出力の周期と線形複雑度
は，それぞれ上限が (2352 − 1)(2160 − 1)，352(2160 − 1) であることを確認した．
DFC 機構の出力ビットを cl1t = cl2t = 0 のように固定した KCipher-2に対して，識別攻撃 [7, 8] を適用した場合，大きな偏差のマスク値は発見されず，distinguisher の構成が困難であることを確認した．
DFC 機構の出力ビット cl1t ，cl2t を固定した KCipher-2 に対して，FSRB の初期値を得る相関攻撃 [11] を適用した場合，前処理の計算量は 2256 ，主処理の計算量は 2266 となり，攻撃は成立しないことを確認した．

27

KCipher-2 に対してタイムメモリトレードオフ攻撃 [14, 15] を適用した
場合，内部状態は十分な空間を有しており，また計算量は 2256 であることから，攻撃は成立しないことを確認した．
KCipher-2 に対して一般化された代数攻撃 [20] を適用した場合，連立方
程式を構成する計算量と Linearization の計算量は鍵の全数探索の計算量よりも大きく，攻撃は成立しないことを確認した．また，DFC 機構の出力ビット cl1t ，cl2t を一定の値で固定して，GF (232 ) 上の加算を XOR で置換えた KCipher-2 に対して，代数攻撃 [21] を適用した場合，NLF の構造
により方程式を構成できず攻撃は成立しないことを確認した．
提案論文 [2] において示された一般化した GD 攻撃を KCipher-2 に適用
すると計算量のオーダが O(2344 ) となり，鍵の全数探索よりも大きくなり攻撃が成立しないことを確認した．また，単純な GD 攻撃（FSR-A のレ
ジスタと NLF の内部レジスタを全て推測して，FSR-B のレジスタを全て決定する）を KCipher-2 に適用すると，計算量のオーダが O(2288 ) となり，同様に，攻撃が成立しないことを確認した．各フィードバック関数の αi , i = 0, 1, 2, 3 を除いて，GF (232 ) 上の加算を排他的論理和で置き換えた KCipher-2 に対して，提案論文 [2] にある GD 攻撃を適用した場合，計算量のオーダが O(2192 ) となることを確認した．
KCipher-2 に対して関連鍵/選択 IV 攻撃を適用することに関しては，初期化処理において，AES の鍵スケジューリングアルゴリズムを用いてラ
ウンド鍵を作成して，これと IV を内部状態に設定し，24 サイクルだけ内部状態を更新してラウンド鍵と IV を含む内部状態を撹拌しているため，攻撃は困難であることを確認した．
NIST 乱数検定（SP800-22）[22] を KCipher-2 のキーストリームに対して適用した場合，全ての検定項目をパスすることが述べられている．

参考文献[1] S. Kiyomoto, T. Tanaka, and K. Sakurai, “A Word-Oriented Stream
Cipher Using Clock Control,” Proc. of SASC2007, pp.260-273, 2007.
[2] S. Kiyomoto, T. Tanaka, and K. Sakurai, “K2: A Stream Cipher Algorithm Using Dynamic Feedback Control,” Proc. of SECRYPT2007,
pp.204-213, 2007.

28

[3] Royal Holloway Enterprises Ltd., “Provisional Study of the Properties
of Dynamic Linear Feedback Shift Registers-I,II,” third-party eval.
report, 2009.
[4] General Secretary, Cryptology Research Society of India, “Evaluationof the Word-Oriented Stream Cipher: K2,” third-party eval. report，
2009.
[5] G. Gone, “Theory and Applications of q-any Interleaved Sequences,”
IEEE Trans. on Information Theory, vol.41, no.2, pp.400-411, 1995.
[6] D. Coppersmith, S. Halevi, and C. Jutla, “Cryptanalysis of stream
ciphers with linear masking,” Advances in Cryptology, CRYPT2002,
LNCS2442, pp.515-532, 2002.
[7] D. Watanabe, A. Biryukov, and C.D. Canniere, “A Distinguishing
Attack of SNOW 2.0 with Linear Masking Method,” In Proc. of
SAC2003, LNCS3006, pp.222-233, 2004.
[8] K. Nyberg and J. Wallen, “Improved linear distinguishers for SNOW
2.0,” In Proc. of FSE2006, LNCS4047, pp.144-162, 2006.
[9] T. Siegenthaler, “Decrypting a class of stream ciphers using ciphertext
only,” IEEE Trans. Comput., vol.C-34, no.1, pp.81-85, 1985.
[10] R.G. Gallager, “Information Theory and Reliable Communications,”
JohnWiley and Sons, Inc. New York, London, Sydney, Toronto, 1968.
[11] V.V. Chepyzhov, T. Johansson, and B. Smeets, “A simple algorithm
for fast correlation attacks on stream ciphers,” FSE2000, LNCS1978,
pp.181-195, 2001.
[12] S.H. Babbage, “Improved exhaustive search attacks on stream ciphers,” European Convention on Security and Detection, IEE Conference publication, no.408, pp.161-166, 1995.
[13] J.Dj. Golic, “Cryptanalysis of alleged A5 stream cipher,” Eurocrypt’97, LNCS1233, pp.239-255, 1997.

29

[14] A. Biryukov and A. Shamir, “Cryptanalytic time/memory/datatradeoﬀs for stream ciphers,” Asiacrypt2000, LNCS1976, pp.1-13,
2000.
[15] J. Hong and P. Sarker, “Rediscovery of time memory tradeoﬀs,”
IACR ePrint Archive, Report 2005/090, 2005.
[16] M.E. Hellman, “A cryptanalytic time-memory trade-oﬀ,” IEEE
Trans. on Infor. Theory, pp.401-406, 1980.
[17] N. Courtois, “Higher Order Correlation Attacks, XL Algorithm
and Cryptanalysis of Toyocrypt,” ICISC2002, LNCS2587, pp.182-199,
2002.
[18] N. Courtois and W. Meiter, “Algebraic Attacks on Stream Ciphers with Linear Feedback,” Eurocrypt2003, LNCS2656, pp.345-359,
2003.
[19] D. Coppersmith and S. Winograd, “Matrix multiplication via arithmetic progressions,” J. Symbolic Computation, pp.251-280, 1990.
[20] N. Courtois, “Algebraic attacks on combiners with memory and several outputs,” In Proc. of ICISC2004, LNCS3506, pp.3-20, 2005.
[21] O. Billet and H. Gilbert, “Resistance of SNOW 2.0 against algebraic
attacks,” In Proc. of CT-RSA2005, LNCS3376, pp19-28, 2005.
[22] NIST, Statistical Tests, Cryptographic Toolkit, available at
http://csrc.nist.gov/groups/ST/toolkit/rng/documentation software.html[23] P. Ekdahl and T. Johansson, “A new version of the stream cipher
SNOW,” Proc. of SAC2002, LNCS 2595, pp.47-61, 2002.
[24] J. Daemen and Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard, Springer, 2002.

30