社団法人 電子情報通信学会

信学技報

THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERSTECHNICAL REPORT OF IEICE.

隣接 S-box の影響を一部考慮した DES の経路探索
青木和麻呂

首藤一幸 ∗

maro@isl.ntt.jp shudoh@muraoka.info.waseda.ac.jp

NTT 情報通信研究所〒 238–03 神奈川県 横須賀市 武 1–2356∗

早稲田大学理工学部情報学科〒 169 東京都 新宿区 大久保 3–4–1

あらまし
差分解読法や線形解読法に対する安全性を表す指標に最大差分特性確率、最大線形特性確率がある。松井が提案した探索アルゴリズムにより DES に対する最大差分特性確率や最大線形特性確率はすでに求められている。このアルゴリズムは DES の最小構造である S-box の差分特性確率や線形特性確率を求め、それから F 関数の差分特性確率や線形特性確率を導き、最終的にアルゴリズム全体の差分特性確率や線形特性確率に拡張している。しかし実際には、計算量の問題から 1 つの F 関数内の 8
つの S-box の差分特性確率や線形特性確率が独立に求められると仮定して差分特性確率や線形特性確率が求められていた。
今回の報告では DES の S-box の差分特性確率や線形特性確率が独立であるとの仮定を一部外して行なった最良経路探索法と探索結果を報告する。
和文キーワード

最大差分特性確率, 最大線形特性確率, 探索アルゴリズム, DES∗ 首藤は平成 8 年 3 月 NTT 情報通信研究所で本研究に参加

Characteristic Search for DES
Considering Eﬀect of Adjacent S-boxes
Kazumaro AOKI

Kazuyuki SHUDOH ∗maro@isl.ntt.jp shudoh@muraoka.info.waseda.ac.jp
NTT Laboratories
1–2356 Take, Yokosuka-shi, Kanagawa-ken, 238-03 Japan∗
Department of Information and Computer Science, School of Science and Engineering, Waseda University
3–4–1 Ookubo, Shinjuku-ku, Tokyo-to, 169 Japan

Abstract
The maximum diﬀerential characteristic probability and maximum linear characteristic
probability are security indicators for diﬀerential cryptanalysis and linear cryptanalysis. Matsui’s
search algorithm is used to ﬁnd the maximum diﬀerential characteristic probability and maximum
linear characteristic probability of DES. His algorithm ﬁrst calculates the diﬀerential characteristic
and linear characteristic probabilities of S-boxes which are the minimum structure of DES, and thenintroduces the diﬀerential characteristic and linear characteristic probabilities of an F function. Finally, the algorithm expands the diﬀerential characteristic and linear characteristic probabilities into
an entire cipher algorithm. However, the diﬀerential characteristic and linear characteristic probabilities which Matsui’s algorithm determines are calculated under the assumption that diﬀerential
characteristic and linear characteristic probabilities of 8 S-boxes for an F function are independent
due to the complexity of these probabilities. However, the diﬀerential characteristic and linear characteristic probabilities which Matsui’s algorithm determines are calculated under the assumptionthat diﬀerential characteristic and linear characteristic probabilities of 8 S-boxes and that of an F
function are independent due to the complexity of these probabilities.
This paper describes an investigation of the maximum diﬀerential characteristic and maximum
linear characteristic probabilities using fewer assumptions for S-box independence than in diﬀerential
characteristic and linear characteristic probabilities of the F function.
英文 key words

Maximum Diﬀerential Characteristic Probability, Maximum Linear Characteristic Prob-

ability, Search Algorithm, DES∗ SHUDOH participated in this research at NTT Laboratories during March 1996.

はじめに

1

に確率 1/2 で従来より低い、確率 1/2 で従来より高い安全性をもつことがわかった。

差分解読法 [BS91] および線形解読法 [M94] という共通鍵ブロック暗号に対する強力な解読法が発表されて以来、これらの解読法に対する安
全性評価は重要な課題となった。
差分解読法、線形解読法のどちらも最初の発

2

準備
本稿では、DES 型暗号の初期転置 IP 、最終

表では局所的な性質を解析し、それを暗号アル

転置 IP −1 は評価対象とした差分特性確率およびゴリズム全体に拡張し、解読に必要な選択平文

線形特性確率に全く影響を与えないので省略す

量や、既知平文量を制する差分特性確率や線形る。64 ビット鍵のパリティビットを除去する選特性確率を導出し、これらの値により安全性を択的転置 P C−1 も省略し、鍵は 56 ビットであ評価していた。しかし、それぞれの解読法に対るとして扱う。また、基本的に線形解読法に関する安全性はいわゆる多重経路 (multiple paths)

してのみ記述するが、差分解読法と線形解読法を考慮した評価によらなければ正確な評価がでの双対性 [M95] により本稿の結果はそのまま差きないといわれている [LMM91, N95] 。

分解読法にも適用可能である。

そこで現在、多重経路を考慮した評価ができ次に用いる記号、用語を定義する。括弧内のるような暗号系が設計されているが (例えば文献

数字はその文字が表すビット数である。またビッ[M96]) 、従来から存在する暗号系に対する評価も重要な課題として残っている。
すでに差分解読法や線形解読法に対する安全性評価手法として、最大差分特性確率や最大線形特性確率を導出するアルゴリズムが提案されている [M95] 。しかし、実際の適用としては計算量の問題から、多重経路が考慮されていないばかりではなく、F 関数内の局所構造である複数の S-box に対して成り立つ統計的性質が独立だと仮定されて最大差分特性確率や最大線形特性
確率が導出されていた。実際この仮定が成り立たない実例も見つかっている [K93b, OMA95] 1 。
本稿では DES 型暗号に対して、F 関数内の複数の S-box の統計的性質が一部独立でないと仮定した最大差分特性確率や最大線形特性確率を導出するアルゴリズムを提案し、適用した結果を報告する。
アルゴリズムを適用した結果、線形解読法に対する安全性は、DES では従来知られていたものと同じであること、8 段以上の偶数段 s2 DES
ではランダムに鍵を選んだときに確率 1/4 で安全性が従来知られていたものより若干低いこと、
6,14 段の s3 DES ではランダムに鍵を選んだとき

ト位置は最下位ビットを 0 とおく。さらに S-boxの番号 j は 1 <=j <= 8 を代表値とするmod8 で

1

文献 [OMA95] の Appendix で指摘されている DESの 数 値例 は誤って い る。正 しい 例 とし て、Ki [4, 6] =Ki [5, 7] = 0 で、(ΓOi , ΓIi ) = (02100820, 00000193) のとき、Piling-up Lemma を使った場合は pi (ΓOi , ΓIi ) =1.13 × 2−6 で 、式 (4) を 使った 定 義 通 り の 値 は
pi (ΓOi , ΓIi ) = 1.13 × 2−4 というのがある。

考える。

P
平文 (64)
平文の上位半分 (32)PH
平文の下位半分 (32)PL
暗号文 (64)
C
暗号文の上位半分 (32)CH
暗号文の下位半分 (32)CL
鍵 (56)
K
第 i 段 F 関数の入力値 (32)Ii
第 i 段 F 関数の出力値 (32)Oi
第 i 段拡大鍵 (48)Ki
j
第 i 段第 j 番 S-box の入力値 (6)Iij
第 i 段第 j 番 S-box の出力値 (4)OijIij に排他的論理和する鍵 (6)Ki
Fi (Ii, Ki) 第 i 段 F 関数
Sij (Iij )第 i 段第 j 番 S-box
Γx
x に対するマスク値∆xx に対する差分値⊕
ビット毎の排他的論理和•
ビット毎の論理積||
ビット列の連結x[t]x の第 t ビット
x[t : u]x の第 t ビットから第 u ビット
x[t1 , . . . , t a] x[t1 ] ⊕ · · · ⊕ x[ta ]x[Γx]x • Γx の偶数パリティ

このとき、定義より明らかに以下の関係が成立ついて求めた性質を F 関数に、F 関数についてする。

の性質を暗号アルゴリズム全体に拡張する。具
体的には、n 段 DES 型暗号において、第 i 段第Oi = Fi (Ii , Ki)
Oij

j 番 S-box の= Sij (Iij )j

上で定義した記号を用いると、第 i 段第 j 番

S-box に対して、
Iij [ΓIij ] ⊕ Oij [ΓOij ] = 0jから、第 i 段 F 関数の

ΓIi , ΓOi , ΓKi , pi (1 <
=i<
= n)

(1)

を導き、これらから

第 i 段 F 関数に対して、

Ii [ΓIi ] ⊕ Oi [ΓOi ] ⊕ Ki [ΓKi ] = 0

ΓP, ΓC, ΓK, p(2)
jを導く。pi から pi 、そして p を導くときに、

DES 型暗号全体に対して、
P [ΓP ] ⊕ C[ΓC] ⊕ K[ΓK] = 0(3)Piling-up Lemma を用い、pi ,p は次のように計算される。
pi = [p i , p i , . . . , p  i ]1という線形表現が定義できる。
またそれぞれの線形表現に対して、入力値 I
次のように定義する。

p(ΓP, ΓC, ΓK)pi (ΓOi , ΓIi , ΓKi)pji (ΓOij , ΓIij )マスク値が自明な場合は引数を省略する。
ま た 任意 の 確 率 q に対 し て 偏 差 を q =
q − 1/2 と定義し、偏差を Piling-up したもの
[q1 , q2 , . . . , q t ] を以下の式で定義する。
1[q1 , q2 , . . . , q t ] =t

(2q  )
2 i=1 i28p = [p1 , p2, . . . , p n ]または P をランダムに与えた場合の成立確率を

DES 型暗号全体
第 i 段 F 関数
第 i 段第 j 番 S-boxjΓIi , ΓOi , pi (1 <
=j<
= 8)

こ こ で 近 似 が 行 な わ れ て い る 。Piling-up
Lemma は、Piling-up される確率変数が独立であることを要求する。しかし、隣接する S-boxの統計的性質は独立ではない。F 関数の入力はまず転置 E で拡大されるため、第 j 番、第 (j + 1)jj+1
番 S-box の入力 Ii 、Ii は、F 関数の入力 Ii 中のある 2 ビットを共有しているからである (図
1)。
Ii

(4)

perm. E
12bit

Ki

従来探索法の問題点

3

I

j
i

j+1

Ii
j

S -boxj+1

S -box線形解読法に対する安全性を表す指標として最大線形特性確率がある。いくつかの DES 型暗号 (DES[U.S77], s 2 DES[K93a], s 3 DES[KPL93],

s5 DES[KLPL95]) に対しては、文献 [M95] による探索アルゴリズムによりすでに求まっている[M95, TSM95, TSM94, STM94, LSK95] 2 。
文献 [M95] の探索法は、局所的に求めた統計的性質を暗号アルゴリズム全体に拡張するという手法をとっている。すなわち単独の S-box に
2

我々の知る限りでは s3 DES, s5 DES の最大差分特性
確率はまだ定まっていない。

Oi

図 1: 入力の共有
それぞれの S-box の番号 j に対して、(1) 式が成立するか否かは独立ではないが、独立だという仮定をおいて Piling-up Lemma を用いている。
このために、一般には、(2) 式の成立確率という定義通りの値と F 関数の pi の値が異なる。これは、文献 [OMA95] によって指摘されている。

しかし、pi の真の値の算出は空間および時間計算量の双方の問題から困難である。そのためだ、できるだけ大きく取っておけばそれだけ探索時間を短くできる。

文献 [M95] の探索法では、計算量を抑えるために個々の S-box に成り立つ統計的性質は独立だという仮定をおいていた。

4Procedure Round-1:
For each candidate for ΓO1 , do the following:

隣接 S-box の相関を一部考慮し Let p1 = max |p1 (ΓO1 , ΓI)|.

た経路探索

 If [p1 , BESTn−1] < BESTn, thentry another candidate for ΓO 1 .

ΓI

本章では、従来の探索法においては独立だと仮定されていた隣接する S-box の統計的性質を
一部独立ではないと仮定しての、最良線形表現、
およびその成立確率の探索アルゴリズムを述べる。このアルゴリズムは文献 [M95] のアルゴリ

 Call Procedure Round-2.
Let BESTn = BESTn.
Exit the program.
Procedure Round-2:

ズムの拡張となっている。
複数の S-box をまとめて近似する、というのが基本のアイディアである。8 個の S-box を同For each candidate for ΓO2 and ΓI2 , do
the following:

時に近似できれば、定義通りの真の特性確率が

 Let p2 = |p2 (ΓO2 , ΓI2 )|.

得られ、真の “最良” 表現が得られるが、計算量

 If [p1 , p2 , BESTn−2] < BESTn,
then try another candidate forΓO2 and ΓI2 .

の問題からそれは困難である。よってここでは2 個以上 8 個以下の S-box をまとめて近似する。
このとき、一度に近似する S-box が 1 個である
場合より探索の計算量が増す。どの程度増すかは、いくつまでの隣接 S-box をまとめて近似するかによる。今回の実験では、まとめて近似する S-box は 2 個までとした。
まず文献 [M95] の探索アルゴリズムを紹介し、次に提案探索アルゴリズムの詳細を述べる。

 Call Procedure Round-3.
Return to the upper procedure.
Procedure Round-i (3 <=i<= n − 1):For each candidate for ΓIi , do the following: Let ΓOi = ΓOi−2 ⊕ ΓIi−1 .

4.1

 Let pi = |pi (ΓOi, ΓIi )|.

松井の探索アルゴリズム

 If

文献 [M95] では、DES のように変換テーブルを用いるインボリューション構造の暗号方式において最良差分特性または最良線形表現、また Call Procedure Round-(i+1).

その特性確率を導出する探索アルゴリズムが紹介されている。
既知の i 段 (1 <=i <= n − 1) の最大特性確率

BESTiから n 段の最大特性確率 BESTnを導出する。探索中は、BESTn の候補BESTnが更新されていき、実行終了時に BESTn = BESTnとなる。[p1 , p2, . . . , p t] の定義は (4) 式の通りである。
BESTnの初期値は、BESTn の値よりも小さ
く取っておけばアルゴリズムは正しく動く。た<[p1 , p2 , . . . , p i, BESTn−i]
BESTn , then try another candidate for ΓIi .

Return to the upper procedure.
Procedure Round-n:
Let ΓOn = ΓOn−2 ⊕ ΓIn−1 .
Let pn = max |pn (ΓOn , ΓI)|.
If

ΓI


[p1 , p2 , . . . , p n] > BESTn ,BESTn = [p1 , p2 , . . ., p n ].

Return to the upper procedure.

then

4.2

Active S-box

入力は、6 ビット × n ではなく転置 E で拡大さ今回の探索アルゴリズムで重要な役割を果た
す active S-box と、その run—隣接した active

S-box 群—について説明する。
active S-box とは、れる前の Ii 中の

ビットが意味を持つ。
以下では、第 i 段について、隣接した n 個の

ΓOij = 0
である Sj -box を指す。
その集合 As は、第 i 段 F 関数の出力マスク値

S-box、S j , S j+1, . . . , S j+n−1への転置 E への入j,j+1,...,j+n−1と表す。同様に、以下の力値を、Ii記号を定義する。

ΓOi に対して

ΓIij,j+1,...,j+n−1 ,Oij,j+1,...,j+n−1 , ΓOij,j+1,...,j+n−1 ,pj,j+1,...,j+n−1i8=s<2 ) = A(ΓO ) = {Sj -box|ΓO j = 0}
As(0<
i
i

と定義できる。ここで s は

s[8 − j] =1
0

if S j is active.
if S j is not active.

なる 8 ビットの値である。
隣接する active S-box の一群を、active S-boxの run と呼ぶ。run に含まれる S-box の数を runの長さと呼ぶ。例えば、次の active S-box 群A(11110110) 2 = {S 1 , S 2, S 3, S 4 , S 6, S 7 }(5)に含まれる run は {S 1 , S 2, S 3 , S 4}, {S 6, S 7} の2 個、長さはそれぞれ 4, 2 で、run の集合 Rは
以下の通りである。
R(A(11110110) 2) = {{S 1 , S 2, S 3 , S 4}, {S 6, S 7 }}(6)
特に断らずに run と言った場合は、できる限り
長い run を取ることとする。ここで S8 -box とS1 -box は隣接しているということに注意。隣接
S-box とは、本稿では F 関数の入力値 Ii 中のある共通するビットから影響を受ける複数の S-boxを指すからである。

4.3

6n − 2(n − 1) = 4n + 2 if 1 <
=n<
=7
32
if n = 8

隣接する複数 S-box の同時近似

今回の探索法において、active S-box 群を run
集合へ分割するということは、まとめて近似する

S-box の決定という意味を持つ。本節では隣接する S-box をまとめて近似する方法を説明する。
DES 型暗号において、単独の S-box への入力
は 6 ビットである。隣接した n 個の S-box へのOij,...,j+n−1 、ΓOij,···,j+n−1 は、単に Oij , Oij+1 , . . .,Oij+n−1 、ΓOij , ΓOij+1 , . . . , O ij+n−1を連結しただけのものである。
Iij,j+1,...,j+n−1 が 転 置 E で 拡 大 さ れ 、第 i段 拡 大 鍵 Ki と の 排 他 的 論 理 和 が と ら れ てIij , Iij+1, . . . , I ij+n−1が求まり、S-box に入力される。
文献 [M95] の探索アルゴリズムでは、転置 E
jによる拡大後の Ii を S-box の入力だと考えていたが、転置 E で拡大される前の Ii を隣接 S-box
群への入力だと考えて近似を行なうことで、Sbox の統計的性質が独立であるという仮定は必要なくなる。
隣接していない active S-box 群については、Iiの段階で近似せずとも統計的性質が独立である
ので個々の S-box 群の線形特性確率に Piling-up
Lemma を適用しても問題はない。Ii の段階でまとめて近似するのは active S-box が隣接している場合のみで充分である。

4.4

同時近似する S-box の組の決定

active S-box 群を run 集合に分割することで、まとめて近似する隣接 S-box 群が決まる。しかし、ここで単にできるだけ長い run に分割しただけでは最大 8 個の S-box をまとめて近似することになってしまう。例えば、(6) 式に従うと最大 4 個の S-box をまとめて近似することになる。
計算量を現実的な範囲に収めるためには、まとめて近似する S-box 数を制限する必要ある。
そこで、run の集合 Rの各要素を、それぞれさらに部分 run に分割する。例えば、同時に近似

は、(000000000000) 2から (111111111111) 2の任する S-box 数を 2 までと決定した場合、(6) 式

意の値を取るわけではない。

の run 集合中の第 1 要素 {S 1 , S 2, S 3, S 4 } は、

S-box を単独で近似して Piling-up Lemma でj
結び付けている限り、S-box への入力値 Ii がj
取り得る値の集合 {Ii } は常に {(000000) 2, . . .,(111111) 2} で、鍵に依存することはない。とこjj+1
ろが、まとめて近似する場合の {Ii ||Ii } は
jj+1
鍵に依存して決まる。Ii [2 : 5], I i [0 : 3] はIij , Iij+1中の他のビットとは独立しているもの
jj+1の、Ii [0 : 1], I i [4 : 5] の 4 ビットが取り得る組合せが鍵のあるビットに依存するからである。
DES 型暗号の F 関数には転置 E による拡大がj j+1
あり、下式のように Ii , Ii それぞれのあるビッ
j,j+1
トが Ii
中の共通のビットの影響を受けるよ
うになっている (図 1)。

1. {S 1 }, {S 2, S 3}, {S 4}
2. {S 1 , S 2}, {S 3, S 4 }のどちらか分割する。
第 2 要素 {S 6 , S 7} はこれ以上分割しない。

{S 6 }, {S 7} と分割して独立に近似した後 Pilingup Lemma で結び付けるには、S 6 , S 7 が独立であると仮定する必要がある。まとめて近似すればその仮定は必要ないので、近似はできる限り
まとめて行なうこととした。
以上により、active S-box の集合 (5) 式から、まとめて近似する S-box の組は次のように 2 通
り求まる。

4.5

{{S 1}, {S 2, S 3}, {S 4}, {S 6, S 7 }}{{S 1, S 2 }, {S 3, S 4 }, {S 6, S 7}}

Iij+1 [4] = Iij,j+1[4] ⊕ Kij+1 [4]鍵に依存した線形特性確率

Iij+1 [5] = Iij,j+1[5] ⊕ Kij+1 [5]

n(2 <
=n<
= 7) 個の隣接 active S-box をまとめて特性確率を求めるためには、鍵に関する情報を 2(n − 1) ビット仮定する必要がある3 。その理由を述べる。以下では簡単のために、まとめて考える隣接 S-box を S j , S j+2の 2 個とする。
定義通りに特性確率を求めるならば、入力値
j,j+1 10Ii
2 通りに対して、次の線形表現が成立するかどうかを調べることになる。
Iij,j+1 [ΓIij,j+1 ] ⊕ Oij,j+1 [ΓOij,j+1 ] = 0
Oij,j+1 は以下のように求められる。
Oij,j+1= Oij ||Oij+1= Sij (Iij )||Sij+1(Iij+1)
j

j,j+1

= Si (Iij[4 : 9] ⊕ K i )|| Sij+1 (Iij,j+1[0 : 5] ⊕ K ij+1 )Sij , Sij+1への直接の入力値を連結して 12 ビッ
トと考えた
j

j+1

Ii ||Ij=(Iij,j+1[4 : 9] ⊕ K ij ) || (I ij,j+1[0 : 5] ⊕ K ij+1 )3

Iij [0] = Iij,j+1[4] ⊕ Kij [0]n = 8 のときは、鍵に関する情報を 16 ビット仮定する必要がある。

Iij [1] = Iij,j+1[5] ⊕ Kij [1]

これよりIij [0] ⊕ Iij+1 [4] = Kij [0] ⊕ Kij+1 [4]Iij [1] ⊕ Iij+1 [5] = Kij [1] ⊕ Kij+1 [5] (7)となる。これは、鍵の情報 2 ビットにより、

Iij [0], I ij [1], I ij+1[4], I ij+1[5] の 4 ビット、ひいてjj+1
は Ii ||Ii の取り得る値が制約を受けることを示している。
隣接する 2 個の S-box を独立とみなして
Piling-up Lemma で結びつけた場合、線形表現
jj+1の成立確率は Ii ||Ii 212 通りに対して求められていた。独立だと仮定しないで同時に近似するということは、(7) 式の 2 ビットによって 212 を4 等分し、4 つの領域それぞれについて確率を求めることになる。線形表現成立の場合の数が、分割された領域に均等に分かれるならば、求まる確率は領域分割なしと変わらない。均等でなければ、Piling-up Lemma で結びつけるよりも
大きな |pi |、特性確率が導出されることになる。
従って安全性の評価結果が異なってくる可能性がある。
以上のように隣接 S-box をまとめて近似すると、(7) 式の値に依存して特性確率が複数求まる

場合がある。特性確率が鍵に依存するわけである。今回の探索では (7) 式の値として解読者にとってもっとも都合のよいものを選択した。その結果得られる線形表現、特性確率は (7) 式の値がある条件を満たした場合のものとなる。鍵5.1

DES についての探索

1 段から 20 段の DES について探索を行なった。得られた最良線形表現、最大線形特性確率は、既知の値 [M94] と全く同じであった。

がその条件を満たさない場合、その線形表現は本稿で示す値以下の特性確率を持つことになる。
本節では隣接 S-box 2 つの同時近似について述べたが、3 つ以上の S-box の同時近似も同様に考えることができる。

4.6

提案探索アルゴリズム

文献 [M95] の探索アルゴリズムを基に、提案
アルゴリズムを構成する。
今回の探索アルゴリズムと文献 [M95] のアル
ゴリズム (Matsui’s Algorithm) の相違を n 段探索について述べる。主に active S-box に関するもので、以下の通りである。

5.2

s2 DES についての探索

1 段から 20 段の s2 DES について探索を行なった結果、8 段以上の偶数段 s2 DES について、鍵の値によっては従来知られていたよりも安全性が低いことがわかった。
図 2に、8 段以上の偶数段 s2 DES の最良線形表現を示す。最終段では S 7 , S 8がまとめて近似されていて、特性確率が鍵の値に依存している。
図の線形表現は、鍵がある条件を満たしている
場合の最良表現である。
図 2から最終段を除いたものは 7 段以上の奇数段 s2 DES の最良線形表現となっている。この場合は鍵に関する条件はない。

• Procedure Round-1,2:
Matsui’s Algorithm: S-box を 順に 辿
り、特性確率を Piling-up していく。
Our Algorithm: active S-box 群 As の候8
補それぞれ (0 <= s < 2 ) に対して、同時近似する S-box の組 (run) を決定、run を順に辿って特性確率を Piling-up
していく。

得られた条件付き最良線形表現とその特性確率を、文献 [M95] のアルゴリズムで得られる値と比較する。
文献 [M95] のアルゴリズムで得られる最良線
形表現と特性確率は、

PL [5, 10, 11] ⊕ C H [5, 10, 11] =(8)

今回の探索法で得られた最良線形表現と特性
確率はPL [5, 10, 11] ⊕ C H [5, 10, 11] ⊕ C L [0, 5, 6, 8]

Matsui’s Algorithm: S-box を 順に 辿
り、特性確率を Piling-up していく。
Our Algorithm: A(ΓO i ) を求め、同時近似する S-box の組 (run) を決定し、run を順に辿って特性確率を Piling-up
していく。

K2i [4, 5, 6, 7]

i=1

BEST16 = 1.19 × 2−26

• Procedure Round-i (3 <=i<= n − 1):
F 関数の出力値に対するマスク値が決まる。
ΓOi = ΓOi−2 ⊕ ΓIi−18

= K16 [1, 8, 9, 11] ⊕7
K2i[4, 5, 6, 7]

i=1

BEST16 = 1.51 × 2−26(9)ただし、上の線形表現が (9) 式の特性確率を持つのは、鍵が次の条件を満たす場合のみである4 。

5

実験結果
第 4章で述べたアルゴリズムを実装、探索を行なった結果を報告する。

K16 [4, 6] = 0 かつ K16 [5, 7] = 1
4

この場合、鍵準備アルゴリズムを考慮してもこのような条件を満たす鍵は存在する。

この条件が満たされないと特性確率は以下のよ

従来知られていたよりも安全性が低いことがわ

うに小さくなる。

かった。




|p | =

1.59 × 2−28 if K16 [5, 7]=0
1.75 × 2−27 if K16 [4, 6]=K 16 [5, 7]=1

同様に、8 段以上の偶数 (n) 段について図 3、
表 1の最大線形特性確率が得られるのは、鍵が次の条件を満たす場合のみである。

Kn [4, 6] = 0 かつ Kn [5, 7] = 1
つまり表 1の最大線形特性確率は、鍵が持つ情報

56 ビットのうち 2 ビットに仮定をおいての値、ということになる。

6,14 段 s3 DES について文献 [M95] のアルゴ
リズムで得られるものとは異なった最大線形特性確率を得たが、その特性確率に対応する最良線形表現は、文献 [M95] のアルゴリズムで得られるものと同じであった。つまり、S 4 , S 5 が独立だと仮定した場合としない場合で、異なる特性確率が算出されたことになる。
14 段 s3 DES についての結果について比較する。
文献 [M95] のアルゴリズムで得られる最大特性確率はBEST14 = 1.48 × 2−21
表 1: s DES についての最大線形特性確率n rounds 最大線形特性確率−1/2

(10)

2

2

+1.13 × 2−2

3+1.27 × 2−3

4
5−1.91 × 2−6+1.20 × 2−7
−10

6
7

+1.12 × 2
+1.65 × 2−1189

+1.96 × 2−14
+1.54 × 2−14

 10

+1.83 × 2 −17

11
 12

+1.45 × 2−17
+1.72 × 2 −20

13
 14

+1.36 × 2−20
+1.61 × 2 −23

15

−23

+1.27 × 2

−26

 16
17

+1.51 × 2
+1.19 × 2−26

 18
19

+1.42 × 2 −29+1.12 × 2−29

 20

+1.33 × 2 −32

:鍵の情報 56 ビットのうち
2 ビットを仮定した場合の値

今回の探索で得た最大特性確率はBEST14 = 1.58 × 2−21 if K1 [16, 18] = 0
BEST14 = 1.38 × 2−21 if K1 [16, 18] = 1
最大線形特性確率が鍵の情報 1 ビットに依存し
ている。

6

まとめ
我々は文献 [M95] の経路探索アルゴリズムを拡張し、F 関数内の S-box に成り立つ統計的性
質が独立であるとの仮定を一部はずした経路探索を可能とした。
また、その拡張アルゴリズムを DES, s2 DES,

s3 DES に適用し、線形解読法に対する安全性を評価した。その結果、DES については同じ、s2 DESと s3 DES については安全性が従来知られているより若干低いことがわかった。
今回は時間の制約上 s5 DES の評価、および差分解読法に対する安全性評価ができなかった。今後の予定として、まずこの残された問題を解決し、また、さらに仮定が少ない経路探索アルゴ
リズムを樹立する。探索アルゴリズム中で F 関数の特性確率が必要になったときにその値を少5.3

s3 DES についての探索

1 段から 20 段の s DES について探索を行なった。6 段,14 段 s3 DES は、鍵の値によっては3ない計算量で導出できれば、F 関数の特性確率算出に関しては仮定が必要なくなる。このためには多少の事前計算と、転置 E と S-box の関係の細かい解析をすればよいだろう。

?
?




?

F1 

K1

hhh

(
hhhh
((((
hhh(((((((( hhhhh
hhhh
(((
h
((((
hhh

(
hhh
(((
hhh
(((
(
(
h(
hhhh
((
hhh
((((
(
hh
(
(
(
[4, 5, 6, 7] h?

 [5, 10, 11]


?

K2i

F2i 

hhh

(((
hhh
(((
hhh
(
(
h(
h(
hhh
(((
hhh
(((
(
hhh
(
((
?




?

K2i+1

F2i+1 

hhh

(
hhh
(((
hhh
(((
(
(
h
(
((( hhhhh
hhh
(((
hh
((((
hhh

(
hhh
(((
hhhh((((((((( hhhhh
hhh
(((
(
(
hh
((
? [5, 10, 11]




?

Fn

[1, 8, 9, 11] [0, 5, 6, 8]

Kn?

最終段以外は 2 段の繰り返し線形表現で構成されている。

図 2: 8 段以上 20 段以下の偶数段 s2 DES についての最良線形表現

0
Matsui’s Algorithm
Our Algorithm-5BESTn(log2)

-10

-15

-20

-25

-30

-35
1

2

3

4

5

6

7

8

9

10 11
Round n

12

13

14

15

16

17

18

19

20

図 3: s2 DES についての BESTn-22.5
Matsui’s Algorithm
OurAlgorithm,K16[4,6]=0andK16[5,7]=1
OurAlgorithm,K16[4,6]=1andK16[5,7]=1
OurAlgorithm,K16[5,7]=0

-23
-23.5
-24

BESTn(log2)

-24.5
-25
-25.5
-26
-26.5
-27
-27.5
15

16
Round n

図 4: 16 段 s2 DES についての最良表現における 鍵と特性確率の関係

17

参考文献
[BS91] E. Biham and A. Shamir. Diﬀerential Cryptanalysis of DES-like Cryptosystems. Journal of Cryptology, Vol. 4, No. 1,
pp. 3–72, 1991. (The extended abstract appeared at CRYPTO’90).
[K93a] K. Kim. Construction of DES-like Sboxes Based on Boolean Functions Satisfying the SAC. In H. Imai, R. L. Rivest, andT. Matsumoto, editors, Advances in Cryptology — ASIACRYPT’91, volume 739 of
Lecture Notes in Computer Science, pp. 59–
72. Springer-Verlag, Berlin Heidelberg New
York, 1993.
[K93b] L. R. Knudsen.
Iterative Charac2
teristic of DES and s -DES. In E. F.
Brickell, editor, Advances in Cryptology —CRYPTO’92, volume 740 of Lecture Notes
in Computer Science, pp. 497–511. SpringerVerlag, Berlin Heidelberg New York, 1993.
[KLPL95] K. Kim, S. Lee, S. Park, and D. Lee.
How to Strengthen DES against Two Robust
Attacks. In 1995 Japan-Korea Joint Workshop on Information Security and Cryptology, pp. 173–182, Inuyama, Aichi, JAPAN,
1995. ISEC Group of IEICE (Japan) and KIISC (Korea).
[KPL93] K. Kim, S. Park, and S. Lee. Reconstruction of s2 DES S-boxes and their Immunity to Diﬀerential Cryptanalysis. In 1993
Japan-Korea Joint Workshop on Information Security and Cryptology, pp. 386–397,
Seoul, KOREA, 1993. KIISC (Korea) andISEC Group of IEICE (Japan). (Technicalreport appeared at ISEC93-63).
[LMM91] X. Lai, J. L. Massey, and S. Murphy. Markov Ciphers and Diﬀerential Cryptanalysis. In D. W. Davies, editor, Advancesin Cryptology — EUROCRYPT’91, volume
547 of Lecture Notes in Computer Science,

pp. 17–38. Springer-Verlag, Berlin Heidelberg New York, 1991.
[LSK95] S. Lee, S. H. Sung, and K. Kim. An
Eﬃcient Method to Find the Linear Expressions for Linear Cryptanalysis. In 1995
Japan-Korea Joint Workshop on Information Security and Cryptology, pp. 183–190,
Inuyama, Aichi, JAPAN, 1995. ISEC Groupof IEICE (Japan) and KIISC (Korea).
[M94] M. Matsui.
Linear Cryptanalysis
Method for DES Cipher. In T. Helleseth,editor, Advances in Cryptology — EUROCRYPT’93, volume 765 of Lecture Notes in
Computer Science, pp. 386–397. SpringerVerlag, Berlin Heidelberg New York, 1994.
[M95] M. Matsui. On Correlation Between theOrder of S-boxes and the Strength of DES.
In A. D. Santis, editor, Advances in Cryptology — EUROCRYPT’94, volume 950 of
Lecture Notes in Computer Science, pp. 366–
375. Springer-Verlag, Berlin Heidelberg New
York, 1995.
[M96] M. Matsui. New Structure of Block Ciphers with Provable Security against Diﬀerential and Linear Cryptanalysis. In D. Gollmann, editor, Fast Software Encryption,
Third International Workshop, Cambridge,
UK, February 1996, Proceedings, volume1039 of Lecture Notes in Computer Science,
pp. 205–218. Springer-Verlag, Berlin Heidelberg New York, 1996.
[N95] K. Nyberg. Linear Approximation of
Block Ciphers.
In A. D. Santis, editor, Advances in Cryptology — EUROCRYPT’94, volume 950 of Lecture Notes in
Computer Science, pp. 439–444. SpringerVerlag, Berlin Heidelberg New York, 1995.
[OMA95] K. Ohta, S. Moriai, and K. Aoki.
Improving the Search Algorithm for theBest Linear Expression. In D. Coppersmith, editor, Advances in Cryptology —CRYPTO’95, volume 963 of Lecture Notes
in Computer Science, pp. 157–170. SpringerVerlag, Berlin Heidelberg New York, 1995.
[STM94] T. Sorimachi, T. Tokita, and M. Matsui. On a Cipher Evaluation Method Basedon Diﬀerential Cryptanalysis (II). In The
1994 Symposium on Cryptography and Information Security, number 4C in SCIS94, Lake
Biwa, Japan, 1994. Technical Group on Information Security (IEICE). (in Japanese).
[TSM94] T. Tokita, T. Sorimachi, and M. Matsui. An Eﬃcient Search Algorithm for The
Best Expression on Linear Cryptanalysis.
Technical Report ISEC93-97, The Instituteof Electronics, Information and Communication Engineers, 1994. (in Japanese).
[TSM95] T. Tokita, T. Sorimachi, and M. Matsui. Linear Cryptanalysis of LOKI and s2 DES. In J. Pieprzyk and R. Safavi-Naini,
editors, Advances in Cryptology — ASIACRYPT’94, volume 917 of Lecture Notes
in Computer Science, pp. 293–303. SpringerVerlag, Berlin Heidelberg New York, 1995.
[U.S77] U.S. Department of Commerce, National Bureau of Standards. Data Encryption Standard (Federal Information Processing Standards Publication 46), 1977.