All rights are reserved and copyright of this manuscript belongs to the authors.
This manuscript has been published without reviewing and editing as received
from the authors: posting the manuscript to SCIS 2011 does not prevent future
submissions to any journals or conferences with proceedings.
SCIS 2011
The 2011 Symposium on
Cryptography and Information Security
Kokura, Japan, Jan. 25-28, 2011
The Institute of Electronics,
Information and Communication Engineers
CLEFIA の差分攻撃及び線形攻撃に対する安全性評価の更新
Update of the Security Evaluation of CLEFIA Against Differential
Attack and Linear Attack
三津田 敦司∗
Atsushi Mitsuda
白井 太三 ∗
Taizo Shirai
あらまし 差分攻撃法及び線形攻撃法は共通鍵ブロック暗号に対する代表的なものであり，これらの攻
撃に対する十分な安全性があることを示す必要がある．128 ビットブロック暗号 CLEFIA では，複数の
拡散行列を用いて差分攻撃法および線形攻撃法への耐性を高める設計技法「拡散行列切り替え法」を採
用している．CLEFIA の設計者らは CLEFIA に対し，12 ラウンド以上で差分攻撃及び線形攻撃に有効に
利用できるパスが存在しないことを示した．本論文では，より詳細な差分特性評価及び線形特性評価を
行うことで，11 ラウンド以上で差分攻撃及び線形攻撃に有効に利用できるパスが存在しないことを示す．
キーワード 共通鍵ブロック暗号，CLEFIA, 差分特性確率，線形特性確率，安全性評価
1
はじめに
ラウンド以上で差分攻撃及び線形攻撃に有効に利用でき
るパスが存在しないことを示した [10]．本論文では，設
近年，共通鍵ブロック暗号は様々な分野の機器やアプ
計者らの評価手法を基にした，差分特性確率及び線形特
リケーションに搭載されるようになり，高い安全性と高
性確率の評価手法を示し，その評価手法を用いることで，
い性能を兼ね備えた暗号技術を低コストで実装するニー
CLEFIA は 11 ラウンド以上で差分攻撃及び線形攻撃に
ズはますます高まってきている．ブロック暗号に対して
有効に利用できるパスが存在しないことを示す．
は多くの暗号攻撃法が知られており，特に，差分攻撃法
[2] や線形攻撃法 [6] などの汎用的な攻撃法について，そ
の安全性を示すことがその暗号に対する信頼性を得る上
で必須と考えられる．
諸定義
2
128 ビットブロック暗号 CLEFIA[10] では，複数の拡
散行列を用いて差分攻撃法および線形攻撃法への耐性を
{0, 1}n : n ビット列の集合
⊕, ∧, ∨ : それぞれ XOR, AND, OR の演算子
X|Y : ビット列または行列の連結
高める設計技法「拡散行列切り替え法」[7, 8, 9] を採用
00112 , 10112 : 2 進数表記
し，これらの攻撃法に対する安全性を示している．さら
3
に，これ以外の既知の攻撃法についても網羅的に取り上
げ，それぞれについて配慮した設計を行っている．近年，
CLEFIA
鍵スケジュールをもつブロック暗号への適用が進んでい
CLEFIA は 2007 年に提案された 128 ビットブロック
暗号である．鍵長は 128, 192, 256 ビットから選択可能で
ある．安全性，速度，実装コストの 3 つの基準をバランス
るが，CLEFIA では，鍵スケジュール部に対しても安全
よく実現することを考慮して設計されている．CLEFIA
性を評価できる設計であり，関連鍵攻撃の適用を困難と
は鍵スケジュール部とデータ処理部に分けられており，
している．
本論文ではデータ処理部とその安全性について述べる．
関連鍵攻撃の進展が目覚ましく，AES などのシンプルな
本論文では，CLEFIA の差分攻撃及び線形攻撃に対
データ処理部の基本構造
する安全性評価を更新したので報告する．設計者らは
3.1
active S-box をカウントする手法により，CLEFIA は 12
CLEFIA のデータ処理部では Feistel 構造を拡張した
4 系列 Type-2 一般化 Feistel 構造を採用している [11]．
∗
ブロック長が 128 ビットであることから，各系列長は 32
ソニー株式会社, 〒 141-0001, 東京都品川区北品川 5-1-12 御殿山
Tec, Sony Corporation, Gotenyama Tec. 5-1-12 Kitashinagawa
Shinagawa-ku, Tokyo, 141-0001.
ビットとなる．4 系列の Type-2 構造は 1 ラウンドに 2 つ
1
Xr,0
RKr,0 S0
S1
S0
S1
表 1: S-box の最大差分確率及び最大線形確率
最大差分確率
−4.678
S0
2
2−6
S1
最大線形確率
2−4.385
2−6
M0
Xr+1,0
Xr,1 Xr,2
RKr,1 S1
S0
S1
S0
Xr+1,1 Xr+1,2
Xr,3
M1
Xr+1,3
の F 関数を持ち，一方の F 関数は 1 列目のデータ系列，
もう一方の F 関数は 3 列目のデータ系列に適用される．
3.2
図 1: CLEFIA のラウンド関数
F 関数
M0 , M1 をビット単位の 32 × 32 行列としたときの転置行
列とする．また，M0 , M1 を結合した 4 × 8 行列 M0 |M1
CLEFIA の F 関数は SP 型を採用しており，ラウンド
鍵の加算後，Substitution 層と Permutation 層の順に演
及び t M0−1 |t M1−1 の分岐数も 5 となるため，以下の補題
算される．このタイプの F 関数は，Camelia[1] などの
が成り立つ．
多くのブロック暗号設計に利用されている．CLEFIA は
補題 2 任意の X, Y ∈ {0, 1}32 に対し，Z = M0 X ⊕
Substitution 層に 4 つの 8 ビット S-box, Permutation 層
に 4 × 4 の拡散行列を用いている．
3.3
M1 Y , Z ′ = t M0−1 X ⊕ t M1−1 Y としたとき，以下の関係
式を満たす．但し，(X, Y, Z) ̸= (0, 0, 0) とする．
HW(X) + HW(Y ) + HW(Z) ≥ 5
HW(X) + HW(Y ) + HW(Z ′ ) ≥ 5
S-box
CLEFIA は 2 種類の 8 ビット S-box, S0 , S1 を採用し
ている．S0 はランダムに選択した 4 ビット S-box に基
づくものであり，S1 は GF(28 ) 上の逆元関数に基づくも
CLEFIA では，図 1 に示すように M0 , M1 を F 関数内
に配置している．この手法は拡散行列切り替え法 (DSM)
と呼ばれる．DSM を用いた場合，近傍ラウンド中の差分
のである．S0 , S1 それぞれの最大差分確率と最大線形確
率を表 1 に示す．
3.4
消失や線形マスク消失を防ぐことができるため，active
拡散行列切り替え法
S-box の保証数が増加することが期待できる．
差分攻撃や線形攻撃への耐性を高めるために，異なる
2 つの拡散行列 M0 , M1 を採用している．演算は GF(28 )
4.1
定義 1 任意の X = (x0 |x1 | . . . |xm−1 ) ∈ ({0, 1} )
差分攻撃への耐性評価
差分攻撃は Biham と Shamir によって提案された，ブ
ロック暗号に対する汎用的な攻撃である [2, 3]．差分攻
撃に対するブロック暗号の耐性を評価する方法には，以
下の 2 通りがある．
ここで，ハミング重みを以下のように定義する．
8 m
従来評価手法
4
上で行い，既約多項式は x8 + x4 + x3 + x2 + 1 を用いる．
1 2 4 6
1 8 2 a
2 1 6 4
8 1 a 2
M0 =
, M1 = 2 a 1 8 (1)
4 6 1 2
6 4 2 1
a 2 8 1
1. ランダム置換との識別に利用可能な差分が存在し
ないことを示す
に
対し，HW(X) = #{i|0 ≤ i ≤ m − 1, xi ̸= 0} を X のハ
2. ランダム置換との識別に利用可能な差分特性が存
在しないことを示す
ミング重みとし，HW(X) を X の HW 値とする．
分岐数が 5 である拡散行列 M と HW 値について以下
多くの暗号において 1 つ目の手法により評価するこ
の補題が成り立つ．
とは困難であることが知られている．設計者らはもう 1
補題 1 任意の X ∈ {0, 1}32 に対し，Y = M X とした
つのアプローチ，即ち差分特性確率を評価する手法を採
とき，以下の関係式を満たす．但し，(X, Y ) ̸= (0, 0) と
用した．これは active S-box の数を計算することで評
する．
価できることが知られており，この評価手法は AES や
Camellia などでも用いられている [1, 5]．
HW(X) + HW(Y ) ≥ 5
最大差分確率と最大差分特性確率の間にどれほどの
CLEFIA の 2 つの拡散行列 M0 , M1 及び t M0 , t M1 は
分岐数が 5 であり，補題 1 を満たす．但し，t M0 , t M1 は
ギャップがあるかはこれまで明らかになっていないが，
Daemen と Rijmen によって両者の関係が詳細に議論さ
2
れており，これによると，ある統計的な仮定のもとで，
δB
δA
∆B
∆A
両者には統計的な関連が存在している [4]．よって，差分
特性ベースのアプローチは差分攻撃に対する耐性を評価
する合理的な手法の 1 つであると考えられる．
∆A
Mi
S
S
∆α
Mi
∆β
Active S-box 数評価 S-box への入力差分が非 0 であ
るとき，その S-box は active であるという．差分特性確
率は系全体の active S-box の最大差分確率の積で抑えら
図 2: ラウンド関数の一部の差分 HW 値 (左) と差分値
れる．遷移する可能性のある全ての差分パスを考慮し，
(右) (但し，ラウンド鍵加算は省略，i = 0, 1)
δA
δC
∆A
∆C
active S-box 数の下界を評価することで，差分特性確率
の上界を評価することができる．一般に，ブロック暗号
δC
に含まれる active S-box の数を保証する方法には 2 種
δA
M0
δB
M1
∆C
∆A
M0
∆B
M1
類ある．1 つは証明などで示された active S-box 数の下
界を用いる方法，もう 1 つは探索アルゴリズムにより，
δD
active S-box 数の下界を評価する方法である．設計者ら
∆D
は両方において確認を行うことで，探索ベースで求めら
れる下界を厳密な評価として用いている．
図 3: 3 ラウンド間の一部の差分 HW 値 (左) と差分値
(右) (但し，系列をひねらない表記)
また，CLEFIA には 2 種類の S-box S0 , S1 があり，そ
れぞれの最大差分確率が異なる (表 1)．設計者の観点か
ら CLEFIA の差分攻撃に対する安全性を評価するには，
証明 ∆A, ∆B, ∆C, ∆α, ∆β を図 2 (右) のように置く．
全ての S-box が (差分攻撃に対して弱い=高い最大差分
但し，∆β = ∆B ⊕ ∆C = Mi ∆α である．また，S 層の
確率を有する) S0 であると仮定して評価している．
前後で HW 値は変わらないため，δA = δα である．
に対して評価することは一般に困難である．そこで，設
∆A = ∆α = 0 のとき，∆β = 0 であり，∆B = ∆C ，
即ち，δB = δC となる．次に，∆A ̸= 0 のとき，補題 1 よ
計者らは各経路の差分値のデータ表現にハミング重みを
り，δα+δβ ≥ 5 である．また，補題 3 より，δB+δC ≥ δβ
用いた．ハミング重みを用いた評価を Weight Base 評
である．よって，δA + δB + δC ≥ 5 が成り立つ．
Weight Base 評価 各経路毎，32 ビット全ての差分値
価とする．但し，情報量が減少しているため，XOR や
2
また，DSM の効果により，3 ラウンド間の差分遷移に
F 関数における遷移の条件を考慮する必要がある．HW
関して以下の定理が成り立つ．
値の定義より，XOR に関して以下の補題が成り立つ．
定理 2 3 ラウンド間の一部における各経路の差分 HW
補題 3 任意の A, B ∈ {0, 1}32 に対し，C = A ⊕ B と
値 δA, δB, δC, δD を図 3 (左) のように置いたとき，以
したとき，以下の関係式を満たす．
HW(A) + HW(B) ≥ HW(C)
HW(B) + HW(C) ≥ HW(A)
HW(C) + HW(A) ≥ HW(B)
下の関係式を満たす．但し，δA ̸= 0 または δB ̸= 0 ま
たは δC ̸= δD とする．
δA + δB + δC + δD ≥ 5
証明 ∆A, ∆B, ∆C, ∆D を図 3 (右) のように置く．こ
補題 4 任意の A, B ∈ {0, 1}32 に対し，HW(A) ̸= HW(B)
のとき，∆C ⊕ ∆D = M0 ∆A ⊕ M1 ∆B となるため，補
のとき，HW(A ⊕ B) ̸= 0 を満たす．
題 2, 3, 4 から，δA ̸= 0 または δB ̸= 0 または δC ̸= δD
以降では，任意の差分値 ∆X ∈ {0, 1}
32
のとき，与式が成り立つ．これは M0 , M1 が逆であって
に対する差分
も成り立つ．
HW 値を δX = HW(∆X) とする．ラウンド関数におけ
2
る差分遷移に関して以下の定理が成り立つ．
4.2
定理 1 ラウンド関数の一部における各経路の差分 HW
線形攻撃は松井によって提案された，ブロック暗号に
値 δA, δB, δC を図 2 (左) のように置いたとき，以下の
関係式を満たす．
δB = δC
δA + δB + δC ≥ 5
線形攻撃への耐性評価
対する汎用的な攻撃である [6]．線形攻撃に対する耐性
を評価するには，差分攻撃に対する耐性評価と同様の手
(δA = 0)
法，即ち，active S-box 数と S-box の最大線形確率を用
(δA ̸= 0)
いて評価することができる．
3
γD
γB
γA
S
ΓA
Mi
γC
ΓD
ΓB
γD
S
Γα
Mi
ΓC
ΓD
γA
M0
γB
M1
ΓA
M0
ΓB
M1
ΓC
ΓD
図 4: ラウンド関数の一部の線形 HW 値 (左) と線形マ
図 5: 3 ラウンド間の一部の線形 HW 値 (左) と線形マス
スク値 (右) (但し，ラウンド鍵加算は省略，i = 0, 1)
ク値 (右) (但し，系列をひねらない表記)
設計者らは，差分攻撃に対する耐性評価と同様に，各系
表 2: active S-box の保証数
列毎の線形マスク値を HW 値に置き換えることで Weight
Base 評価を行った．
以降では，任意の線形マスク値 ΓX ∈ {0, 1}32 に対す
る線形 HW 値を γX = HW(ΓX) とする．ラウンド関数
における線形マスク遷移に関して以下の定理が成り立つ．
定理 3 ラウンド関数の一部における各経路の線形 HW
値 γA, γB, γC, γD を図 4 (左) のように置いたとき，以
下の関係式を満たす．
γA = 0
γA + γD ≥ 5
γA + γB ≥ γC
γB + γC ≥ γA
γC + γA ≥ γB
γC
(γD = 0)
(γD ̸= 0)
R
Normal
DSM(D)
DSM(L)
1
2
3
0
1
2
0
1
2
0
1
5
4
5
6
6
8
12
6
8
12
6
10
15
7
8
12
13
14
18
16
18
9
10
11
14
18
20
20
22
24
20
23
26
12
24
28
30
証明 ΓA, ΓB, ΓC, ΓD, Γα を図 4 (右) のように置く．但
形 active S-box 数の下界を導出している．これを表 2 に
し，Γα = t Mi ΓD である．また，S 層の前後で HW 値
示す．DSM(D) 及び DSM(L) はラウンド数 R における，
は変わらないため，γA = γα である．よって，補題 1,3
差分 active S-box 及び差分 active S-box の最小数を示し
2
より成り立つ．
ている．また，DSM の条件 (定理 2,4) を用いない場合，
差分 active S-box 数の最小数と線形 active S-box 数の最
また，DSM の効果により，3 ラウンド間の線形マスク
小数は同じ値となり，Normal として表記している．
遷移に関して以下の定理が成り立つ．
この表より，12 ラウンド CLEFIA において 28 個の差
定理 4 3 ラウンド間の一部における各経路の線形 HW
分 active S-box が保証されている．S0 の最大差分確率
値 γA, γB, γC を図 5 (左) のように置いたとき，以下の
が 2−4.678 であることより，12 ラウンド CLEFIA の最大
関係式を満たす．但し，(γA, γB, γC) ̸= (0, 0, 0) とする．
差分特性確率は 2−4.678×28 = 2−130.984 以下となる．こ
れは，攻撃者が差分攻撃に利用可能な 12 ラウンド差分
γA + γB + γC ≥ 5
特性が存在しないことを意味する．
また，12 ラウンド CLEFIA において 30 個の線形 ac-
証明 ΓA, ΓB, ΓC を図 5 (右) のように置く．このとき，
tive S-box が保証されている．S0 の最大線形確率が 2−4.385
であることより，12 ラウンド CLEFIA の最大線形特性
確率は 2−4.385×30 = 2−131.55 以下となる．これは，攻撃
ΓC = t M0−1 ΓA ⊕ t M1−1 ΓB となるため，補題 2 より成
り立つ．これは M0 , M1 が逆であっても成り立つ．
4.3
2
者が線形攻撃に利用可能な 12 ラウンド線形特性が存在
従来評価結果
しないことを意味する．
設計者らは，データ表現にハミング重みを利用した
以上より，12 ラウンド以上で差分攻撃及び線形攻撃に
Weight Base 評価を行った．定理 1,2,3,4 を用いて，遷
有効に利用できるパスが存在しないことを示した．
移しうる全ての差分パス及び線形パスを考慮し，R ラウ
ンドの CLEFIA に含まれる差分 active S-box 数及び線
4
∆D
1
∆A
M0
1
M0
∆B
M1
1
M1
ΓA
M0
3
M1
4
∆C
M0
1
M0
∆E
ΓB
ΓC
ΓD
M0
2
M0
3
M1
1
M0
3
3
4
0
1
0
図 6: 5 ラウンド間の一部の差分値 (左) と遷移しない差
図 7: 5 ラウンド間の一部の線形マスク値 (左) と遷移し
分 HW 値の例 (右) (但し，系列をひねらない表記)
ない線形 HW 値の例 (右) (但し，系列をひねらない表記)
改善評価手法
5
5.2
CLEFIA では 2 種類の S-box を利用しており，それぞ
れ，最大差分確率及び最大線形確率が異なる (表 1)．従
本節では設計者ら従来の評価手法を基にした，差分特
性評価及び線形特性評価の改善評価手法を述べる．
5.1
2 種類の S-box S0 , S1
来評価では上界を導出するために，2−128 以下となるの
5 ラウンド間の DSM
に active S-box 数がそれぞれ 28 個，30 個必要であると
していた．しかし，全ての active な S-box が S0 でない
設計者らは DSM による条件として，補題 2 を用いて，
場合，実際の特性確率はこの値よりも小さくなる．
3 ラウンド間 2 種類の MDS 行列を考慮した遷移の条件
そこで，S0 , S1 の active 数をそれぞれ #AS0 , #AS1 と
を導出した (定理 2, 4)．本節ではさらに，5 ラウンド間の
して，それぞれのカウントを行う．また，#AS = #AS0 +
2 種類 3 つの MDS 行列を考慮した，新たな定理を示す．
#AS1 とする．例えば，ある差分パスにおいて，#AS0 =
定理 5 5 ラウンド間の一部における各経路の差分値 ∆A,
∆B, ∆C, ∆D, ∆E を図 6 (左) のように置いたとき，そ
の HW 値 δA, δB, δC, δD, δE は以下の関係式を満たす．
20, #AS1 = 6(即ち，#AS = 26) のとき，従来評価では
差分特性確率の上界を 2−4.678×26 = 2−121.628 としてい
たが，本評価では 2−4.678×20−6×6 = 2−129.56 となる．こ
但し，δA ̸= δC または δB ̸= 0 または δD ̸= δE とする．
のようにして，従来よりも厳密な特性確率の上界を導出
することが可能である．
δA + δB + δC + δD + δE ≥ 5
また，この評価方法においては最大差分特性確率及び
証明 M0 (∆A ⊕ ∆C) ⊕ M1 ∆B = ∆D ⊕ ∆E であるた
最大線形特性確率を得るパスが，最小 active S-box 数と
め，補題 2, 4 より成り立つ．これは M0 , M1 が逆であっ
ならない場合がある．例えば，ある差分パスにおいて，
2
#AS0 = 25, #AS1 = 2, #AS = 27 のとき，2−128.95 と
評価され，#AS0 = 20, #AS1 = 6, #AS = 26 のときの
これは，定理 1, 2 からは導けない条件であり，図 6 (右)
2−129.56 に比べ，active S-box 数が多くとも差分特性確
率が大きくなる．
但し，Weight Base 評価においては S0 , S1 を区別して
ても成り立つ．
のような差分 HW 値の遷移が存在しないことを表す．
定理 6 5 ラウンド間の一部における各経路の線形マスク
カウントすることはできないため，S0 を優先的に数える
値 ΓA, ΓB, ΓC, ΓD を図 7 (左) のように置いたとき，そ
といった方法が考えられる．例えば，F 関数への入力差
の HW 値 γA, γB, γC, γD は以下の関係式を満たす．但
分 ∆X に対し，δX = 3 のとき，#AS0 = 2, #AS1 = 1
し，γA ̸= γB または γC ̸= γD とする．
とする．また，5.3 節の Byte Truncate 評価を用いるこ
とで，S0 , S1 を区別してカウントできる．
γA + γB + γC + γD ≥ 5
5.3
証明 ΓA⊕ΓB = t M0 (ΓC ⊕ΓD) であるため，補題 1, 4
より成り立つ．これは M0 , M1 が逆であっても成り立つ．
Byte Truncate 評価
従来の Weight Base 評価では各系列毎のハミング重み
2
を考慮していた．任意の差分値 ∆X, 線形マスク値 ΓX
に対して，HW 値 δX, γX(0 ≤ δX, γX ≤ 4) に置き換
これは，定理 3, 4 からは導けない条件であり，図 7 (右)
え，遷移しうる全ての HW 値について active S-box 数
のような線形 HW 値の遷移が存在しないことを表す．
を計算していた．
本論文では 1 バイト毎に 0, 非 0 を考慮した評価を行
5
う．ここで，Byte Truncate を以下のように定義する．
定義 2 任意の X = (x0 |x1 | . . . |xm−1 ) ∈ ({0, 1} )
8 m
に
δC
2
δA
1
対し，
M0
δD
2
δB
1
BT(X) = BT(x0 |x1 | . . . |xm−1 ) = x̂0 |x̂1 | . . . |x̂m−1
M1
δE
2
を X の Byte Truncate とし，BT(X) を X の BT 値と
λA
00012
λB
00012
M0
M1
11112
λC
00112
11112
λD
11002
λE
00112
呼ぶ．但し，x̂i は xi = 0 のとき 0, xi ̸= 0 のとき 1 とす
る．即ち，BT(X) ∈ {0, 1}m である．
図 8: 遷移しない差分 HW 値 (左) と差分 BT 値 (右) の例
また，BT 値から HW 値への変換 HW′ (·) を以下のよ
定理 9 5 ラウンド間の一部における各経路の差分値を
うに定義する．
∆A, ∆B, ∆C, ∆D, ∆E を図 6 (左) のように置いたとき，
その BT 値 λA, λB, λC, λD, λE は以下の関係式を満た
す．但し，λA ̸= λC または λB ̸= 0 または λD ̸= λE と
定義 3 任意の X = (x0 |x1 | . . . |xm−1 ) ∈ ({0, 1}8 )m に
対し，
する．
HW′ (BT(X)) = HW′ (x̂0 |x̂1 | . . . |x̂m−1 )
= x̂0 + x̂1 + · · · + x̂m−1 = HW(X)
HW′ (λA ∨ λC) + HW′ (λB) + HW′ (λD ∨ λE) ≥ 5
この BT 値を用いた耐性評価を Byte Truncate 評
定理 10 5 ラウンド間の一部における各経路の線形マス
価とする．任意の差分値及び線形マスク値 ∆X, ΓX ∈
ク値を ΓA, ΓB, ΓC, ΓD を図 7 (左) のように置いたと
{0, 1}32 に対して，λX = BT(∆X), µX = BT(ΓX) と
き，その BT 値 µA, µB, µC, µD は以下の関係式を満た
し，λX, µX ∈ {0, 1}4 に置き換えることで遷移の判定を
す．但し，µA ̸= µB または µC ̸= µD とする．
行う．Byte Truncate 評価は Weight Base 評価に比べ，
HW′ (µA ∨ µB) + HW′ (µC ∨ µD) ≥ 5
情報量の低下が少ないといえる．Weight Base 評価と同
様に BT 値に対する遷移の条件を示す．BT 値，HW 値
証明 定理 7,8,9,10 はそれぞれ，定理 1,2,5,6 の証明に
の定義より，XOR に関して以下の補題が成り立つ．
おいて，補題 5 を加えることで導かれる．
補題 5 任意の差分値 ∆A, ∆B ∈ {0, 1}32 及び，線形マ
2
定理 7,8,9,10 を用いることで，より詳細な遷移の判定
スク値 ΓA, ΓB ∈ {0, 1}32 は以下の関係式を満たす．
HW(∆A ⊕ ∆B) ≤ HW′ (λA ∨ λB) ≤ δA + δB
HW(ΓA ⊕ ΓB) ≤ HW′ (µA ∨ µB) ≤ γA + γB
を行うことが可能となる．例として，図 8 (左) のような
差分 HW 値の遷移が存在しないことを示す．
δC = 2 より，λC = 00112 とおく．このとき，δA =
1, δD = 2 及び定理 7 より，λD = 11002 となる．同様
また，∆C = ∆A ⊕ ∆B, ΓC = ΓA ⊕ ΓB としたとき，
に，δB = 1, δE = 2 より，λE = 00112 となる．また，
以下の関係式を満たす．
λA ⊕ λB ⊕ λC ⊕ (λA ∧ λB ∧ λC) = 0000
2
µA ⊕ µB ⊕ µC ⊕ (µA ∧ µB ∧ µC) = 0000
DSM の条件 (補題 2) より，
HW(∆A) + HW(∆B) + HW(∆C ⊕ ∆E) ≥ 5
2
を満たす必要がある．しかし，HW(∆A) = HW(∆B) =
補題 5 を利用することで，以下の定理 7,8,9,10 が成り
1, λC = λE = 00112 及び定理 8 より，
立つ．
定理 7 ラウンド関数の一部における各経路の差分値 ∆A,
HW(∆A) + HW(∆B) + HW(∆C ⊕ ∆E)
∆B, ∆C を図 2 (右) のように置いたとき，その BT 値
λA, λB, λC は以下の関係式を満たす．
λB = λC
(λA = 0)
HW′ (λA) + HW′ (λB ∨ λC) ≥ 5 (λA ̸= 0)
≤ 2 + HW′ (λC ∨ λE) = 2 + HW′ (00112 ) = 4
であるため，不適である．他の λC の値に対しても同様
である．よって，図 8 (左) のような差分 HW 値の遷移
は起こらない．
Byte Truncate 評価では値の XOR に関する条件式に
定理 8 3 ラウンド間の一部における各経路の差分値を
おいて，Weight Base 評価に比べ情報量の低下が少ない
∆A, ∆B, ∆C, ∆D を図 3 (右) のように置いたとき，そ
ため，ハミング重みだけでなく，非 0 のバイト位置を考
の BT 値 λA, λB, λC, λD は以下の関係式を満たす．但
慮した条件を利用可能となる．また，Byte Truncate 評
し，λA ̸= 0 または λB ̸= 0 または λC ̸= λD とする．
価では各 S-box 毎に active かどうかを判別できるため，
#AS0 , #AS1 をそれぞれカウント可能である．
HW′ (λA) + HW′ (λB) + HW′ (λC ∨ λD) ≥ 5
6
λX0
00112
∆X0
∆X3
M0
λX3
00012
M0
λX4
00112
M1
λX1
11012
∆X1
∆X4
M1
ΓX3
ΓX4
ΓX1
M0
ΓX0
ΓX2
M1
λX2
00012
∆X2
図 9: 3 ラウンド間の一部の差分値 (左) と遷移しない差
図 10: 3 ラウンド間の一部の線形マスク値
分 BT 値の例 (右)
いた遷移の判定は，これまでの条件とは違い，M0 , M1
5.4
を入れ替えると判定結果が異なる場合がある．
代数条件の導入
ここまでは，MDS 行列の入出力重みや，HW 値，BT
線形マスク値についても同様に行列を利用した線形マ
値の XOR の性質を利用することで，遷移の条件を導出し
スク遷移の判定が可能である．3 ラウンド間の一部の線
てきた．本節では CLEFIA で用いられる 2 種類の MDS
形マスク値 ΓX0 , ΓX1 , ΓX2 , ΓX3 , ΓX4 を図 10 のように
行列の要素の値 (式 1) に着目した代数的な条件を導出
置くと，次式が成り立つ．
する．
ここで，3 ラウンド間の一部の差分値 ∆X0 , ∆X1 , ∆X2 ,
I
Z
Z
∆X3 , ∆X4 を図 9 (左) のように置くと，次式が成り立つ．
∆X0
(
)
∆X1 ( )
I I Z M0 Z
0
×
=
(2)
∆X2
Z I I
Z M1
0
∆X
3
∆X4
以上であっても同様の方程式が立てられる．本評価では
5 ラウンド間の関係式による判定を行っている．
5.5
ラウンドへと変更して評価することで，遷移の判定をよ
し，x0,2 , x0,3 , x1,0 , x1,1 , x1,3 , x2,3 , x3,3 , x4,2 , x4,3 ∈ {0, 1}
8
り詳細に行うことが可能となった．また，差分確率，線
は全て非 0 である．
1
0
0
0
6
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
4
2
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0 2
0 a
0
0
0
0
0
0
0
1
0
1
0
0
1
8
改善評価手法のまとめ
DSM の条件に依存するラウンドを 3 ラウンドから 5
各 λXi の値より，式 2 を整理すると次式が得られる．但
0
(3)
さらに，差分値及び線形マスク値に対し，3 ラウンド
ような差分 BT 値について以下に述べる．
形確率の異なる 2 種類の S-box を区別することで，より
0
0
x0,3
0
x1,0 0
0
0
x1,1
0
0
× x1,3
= 0
a
x2,3
2
x3,3 0
0
8
x4,2
1
0
x4,3
x0,2
0
Z
ΓX1
=
×
Z ΓX2 0
0
I
ΓX3
線形 BT 値の遷移が起こるかどうかの判定を行う．
ト毎に分割した方程式を考える．例として，図 9 (右) の
Z
I
Z
同様に任意の µXi について，行列を解くことで，その
ここで，∆Xi = (xi,0 |xi,1 |xi,2 |xi,3 ) とし，式 2 を 8 ビッ
I
Z
t
M1
ΓX4
但し，I を単位行列，Z をゼロ行列とする．
0
0
1
0
0
0
0
0
I
t
M0
Z
ΓX0
厳密な特性確率を導出することが可能となった．
次に，データ表現においてハミング重みの代わりにバ
イト毎の 0, 非 0 を扱う，Byte Truncate 評価を行った．
計算量は増加するが，情報量の低下が少なく，遷移の詳
細な条件が導出でき，2 種類の S-box を区別することが
可能となる．また，MDS 行列の入出力重みによる条件で
なく，MDS 行列の要素の値からなる条件を考慮すること
で，遷移の判定をさらに詳細に行うことが可能となった．
5.6
各行列の要素は GF(28 ) 上の要素である．この式を解く
改善された評価結果
Byte Truncate 評価及び代数条件は従来評価手法と比
べ，計算量が膨大なものとなる．Weight Base 評価と
と，x0,2 , x0,3 , x1,0 , x1,1 , x1,3 , x2,3 , x3,3 , x4,2 , x4,3 が全て
非 0 となる解は存在しないことが分かる．即ち，図 9 (右)
Byte Truncate 評価及び代数条件を併用することにより，
計算量の削減を図った．
これらの改善評価手法を適用した計算機実験による，
のような差分 BT 値の遷移が起こらないことを表す．
このように，任意の λXi について，同様に行列を解く
ことで，その差分 BT 値の遷移が起こるかどうかを判定
R ラウンド CLEFIA における最大差分特性確率及び最
することが可能である．但し，この行列の要素の値を用
7
[3] E. Biham and A. Shamir, “Differential Cryptanalysis of the Data Encryption Standard,” Springer-
表 3: 最大差分特性確率及び最大線形特性確率の評価結果
最大差分特性確率
※
Verlag, 1993.
最大線形特性確率
R
従来評価
本評価
従来評価
本評価
1
2
0
4.678
0
4.678
0
4.385
0
4.385
tion and Differentials in Block Ciphers,” in IACR
ePrint archive 2005/212, 2005.
3
4
9.356
28.068
9.356
32.034
21.925
26.310
21.925
29.540
[5] J. Daemen and V. Rijmen, “The Design of Ri-
5
6
7
37.424
56.136
65.492
41.390
62.746
73.424
43.850
65.775
70.160
47.080
70.620
82.620
8
9
84.204
93.560
101.492
110.136
78.930
87.700
98.545
113.775
10
11
12
102.916
112.272
130.984
119.492
134.848
151.526
100.855
114.010
131.550
121.390
134.085
144.470
[4] J. Daemen and V. Rijmen, “Statistics of Correla-
jndael: AES ― The Advanced Encryption Standard (Information Security and Cryptography),”
Springer, 2002.
[6] M. Matsui, “Linear cryptanalysis of the data
encryption standard,” in Proceedings of Eurocrypt’93 (T. Helleseth, ed.), no. 765 in LNCS, pp.
386–397, Springer-Verlag, 1994.
[7] T. Shirai and B. Preneel, “On Feistel ciphers using optimal diffusion mappings across multiple
rounds,” in Proceedings of ASIACRYPT’04 (P. J.
但し，それぞれの確率に対し，− log2 を取った．
また，網掛けは 128 以上を表す．
Lee, ed.), no. 3329 in LNCS, pp. 1–15, SpringerVerlag, 2004.
大線形特性確率の評価結果を表 3 に示す．従来評価では
特性確率が 2−128 以下となるのは差分，線形共に 12 ラ
[8] T. Shirai and K. Shibutani, “Improving immunity
of Feistel ciphers against differential cryptanalysis
by using multiple MDS matrices,” in Proceedings
ウンドが最低限必要としていたが，本評価手法を適用す
ることで 11 ラウンドでも 2−128 以下となることが分かっ
た．これは，攻撃者が差分攻撃及び線形攻撃に利用可能
of Fast Software Encryption - FSE’04 (B. Roy and
W. Meier, eds.), no. 3017 in LNCS, pp. 260–278,
な 11 ラウンド差分特性及び線形特性が存在しないこと
を意味する．
6
Springer-Verlag, 2004.
まとめ
[9] T. Shirai and K. Shibutani, “On Feistel structures
using a diffusion switching mechanism,” in Pro-
本論文では，CLEFIA に対し，設計者らの評価手法を
法を示した．また，その評価手法を用いることで，差分攻
ceedings of Fast Software Encryption ―FSE’06
(M. Robshaw, ed.), no. 4047 in LNCS, pp. 41–56,
撃及び線形攻撃に対する安全性評価を更新し，CLEFIA
Springer-Verlag, 2006.
基にした，差分特性確率及び線形特性確率の改善評価手
は 11 ラウンド以上で差分攻撃及び線形攻撃に利用可能
[10] T. Shirai, K. Shibutani, T. Akishita, S. Moriai,
and T. Iwata, “The 128-bit blockcipher CLE-
なパスが存在しないことを示した．
FIA,” in Proceedings of Fast Software Encryption
- FSE’07 (A. Biryukov, ed.), no. 4593 in LNCS,
参考文献
[1] K. Aoki, T. Ichikawa, M. Kanda, M. Matsui,
pp. 181–195, Springer-Verlag, 2007.
S. Moriai, J. Nakajima, and T. Tokita, “Camellia: A 128-bit block cipher suitable for multiple
[11] Y. Zheng, T. Matsumoto, and H. Imai, “On the
Construction of Block Ciphers Provably Secure
platforms,” in Proceedings of Selected Areas in
Cryptography - SAC’00 (D. R. Stinson and S.
E. Tavares, eds.), no. 2012 in LNCS, pp. 41–54,
and Not Relying on Any Unproved Hypotheses,”
in Proceedings of CRYPTO 89 (G. Brassard, ed.),
no. 435 in LNCS, pp. 461–480, Springer-Verlag,
1989.
Springer-Verlag, 2001.
[2] E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” Journal of Cryptology, vol. 4, pp. 3–72, 1991.
8