Feistel结构差分活动S盒的搜索算法*

2014-02-10明亚运祝世雄曹云飞

通信技术 2014年10期

关键词：汉明下界搜索算法

明亚运,祝世雄,曹云飞

(保密通信重点实验室,四川成都610041)

Feistel结构差分活动S盒的搜索算法*

明亚运,祝世雄,曹云飞

(保密通信重点实验室,四川成都610041)

为了设计安全的分组密码算法,评估算法抵抗差分分析和线性分析的能力至关重要。目前一个比较实际的方法就是计算分组算法活动S盒的最小数目,或者最小数目的下界。2004年Shirai等人在FSE会议上提出了一种基于汉明重量针对Feistel结构的估计差分活动S盒数量下界的算法。本文指出了此算法的不足,并基于一种特殊的剪枝策略,对原算法提出了一个改进方案,将算法提升到实际应用水平。

Feistel结构差分分析活动S盒

0 引言

分组密码由于具有容易被标准化和易于实现同步的优点,在信息安全领域得到了广泛的应用。在分组密码的标准化过程中,密码算法的安全性成为衡量算法好坏的重要指标之一。分组密码分析方法中最知名的莫过于Biham与Shamir提出的差分分析[1]和Matsui提出的线性分析[2],这是已知的攻击分组密码算法最有力的途径。对于一个密码设计者来说,评估分组密码算法的安全性,应该首先重点考虑其抵抗差分分析和线性分析的能力。目前一个有效的方法即是计算分组密码算法的活动S盒的数量。

目前主要有两类方法来计算差分(线性)活动S盒的最小数或者最小数的下界。一是理论证明,此种方法能够解决较小轮数的计数问题。首先提出Feistel结构的活动S盒下界理论计算的是Kanda[3],主要是基于分支数的理论推导证明,后由Wang等人[4]优化。吴文玲等人[5]分析了CAST256结构并得到了8轮和16轮的活动S盒的下界。对于CLEFIA和SMS4结构的活动S盒的下界分别由Shibutani[6]和Wang等人[7]做了研究。

如果要解决较大轮数甚至完整算法的活动S盒计数问题,则需要利用第二种方法,即是建立搜索算法。通过对Matsui[8]的算法的改进,Aoki等人[9]给出了一种有效地输出Feistel结构活动S盒最小数的下界的算法。Shirai等人[10,11,12]采用了一些有效的搜索算法对Feistel、CAST256、GFS安全性做出了评估。同时值得一提的是,Wu[13]、Mouha[14]等人采用线性规划方法计算活动S盒数量也取得了不错的效果。

在文献[10]中,Shirai等人针对套嵌SP型轮函数的Feistel结构,提出一种基于汉明重量的活动S盒搜索算法。此算法采用穷尽搜索法,数据复杂度高,离实际使用有较大差距。

1 相关定义

定义1有非零输入的S盒就叫做活动S盒。

定义2令x=(x1,…,xn)∈()n,x的汉明重量wh(x)定义为

定义3令θ:是一个变换,x=(x1,…,xn)∈()n,则称B(θ)=(wh(x)+wh(θ(x)))为θ的分支数。

分支数的概念和差分密码分析及线性密码分析紧密相关,本文后面将利用它给出活动S盒数目的界。下面定义θ的差分分支数Bd:

其中x、x*为变换θ的两个输入,x⊕x*为变换θ的输入差分,θ(x)⊕θ(x*)为变换θ的输出差分。

定义4SP型F函数定义如下:令n为双射S盒的输入比特宽,m为F函数中所使用S盒的数量,在F函数中

(1)mn比特的轮密钥ki∈()m和数据X∈()m异或:W=X⊕ki。此过程为加密钥。

(2)W分成m份的n比特数据,输入到对应n个S盒S1、S2、…、Sn。

(3)S盒输出的数据记作Z∈()m,通过一个在上的m×m矩阵M变换:Y=MZ。

本文所研究的对象即是SP型轮函数的Feistel结构,如图1所示。

图1 套嵌SP轮函数的Feistel结构Fig.1 Feistel structure with SP round function

2 算法介绍

Feistel结构差分模型见图2。

图2 Feistel结构扭正图(4轮)Fig.2 Untwist form of Feistel structure(4 rounds)

令Δxi(i=0,1,2,3,…)代表各轮的差分,根据Feistel结构的扭正图,我们可以得到如图3所示的结构,并得到各轮差分之间有如下关系:

图3 扭正图细节Fig.3 Details of Untwist form of Feistel structure

令W1为wh(Δxi+Δxi+2j),可以得到下面的不等式,

另一方面,我们令W2为wh(),如果至少存在一个wh(Δxj)非零,那么有如下不等式

如果所有的汉明重量wh(Δxj)都为0,那么W2的值为0。在下面的搜索算法中,对于某一个汉明重量组合,比较W1与W2的值,如果二者的取值范围没有重合,那么说明此汉明重量组合是不合理的,不应当计入到活动S盒的下界的目标组合中去。

以下算法基于汉明重量,可以输出一个R轮活动S盒数量的下界:

1)令L=∞。

2)任意一个对δx0,δx1,…,δxR+1汉明重量为0, 1,2,3,…,m的组合(不妨设m=8,共9R+2种可能):

(1)从i=2到R+1,做如下操作

从j=2到j≤i,j=j+2,做如下操作

A.检验所给的汉明重量组合是否满足条件。

B.如果检测通过则继续,否则跳出流程。

(2)如果所有的检测皆通过,计算在此路径中所有活动S盒的数量A。如果A＜L,则设置L=A。

3.输出L,作为R轮活动S盒数量的下界。

此算法采用穷尽搜索法,数据复杂度高,我们的实验表明当m=8,Bd=9时搜索12轮的Feistel结构的活动S盒下界所需的时间已经超过一天,离实际使用存在很大差距。

3 改进方案

根据文献[12]剪枝方法,可将算法优化如下,可以输出一个R轮活动S盒数量的下界:

1)令LR=∞。

2)从i=1到R,调用函数Func(i)。Func(y)定义为:

(1)如果y=R+1,做如下操作

如果L＞。

(2)如果y≠R+1,从j=0到j≤m,执行如下操作:令δxy=j。如果,则执行以下操作:

(3)检验所给的汉明重量组合是否满足条件。如果检测通过,则转到Func(y+1)。

3)输出L,作为R轮活动S盒数量的下界。

4 方案分析

改进的方案充分利用了较小轮数的下界的结果,即是,如果前y轮活动S盒的数量与剩下R-y轮的活动S盒的下界的总和已经超过目前得到的R轮活动S盒数量下界的结果,那此搜索再进行下去也无法得到一个更优的结果。此种提前跳出的剪枝策略大大降低了算法的计算复杂度,实验表明,当m=8,Bd=9时搜索30轮的Feistel结构的活动S盒下界所需的时间仅需几秒。以m=8,Bd=9为例,可得如结果,见表1。

表1 实验结果Table 1 Experiment results

5 结语

借助于计算机,构造一个普适性较好的分组密码实际安全性分析工具在分组密码设计工作中非常必要,科研人员可以通过此工具对密码算法进行可行性论证和改进,使算法设计等实际工作更加快速高效,并对可重构密码安全性分析提供重要理论支持。Feistel结构差分活动S盒搜索算法的应用,可以作为分组密码实际安全性分析工具的重要功能之一,后续进一步研究将算法拓展到SMS4、MISTY、L-M等结构。

[1] Biham E.,Shamir A.Differential Cryptanalysis of DES-like Cryptosystems[J].Journal of Cryptology,1991,4 (01):3-72.

[2] Matsui M.Linear Cryptanalysis Method for DES Cipher [C]//EUROCRYPT'1993,Heidelberg:Springer.1994: 386-397.

[3] Kanda M.Practical Security Evaluation against Differential and Linear Cryptanalyses for Feistel Ciphers with SPN round function[C]//Selected Areas in Cryptography' 2000.Heidelberg:Springer.2001:324-338.

[4] Wang N.,Jin C.Security Evaluation against Differential and Linear Cryptanalyses for Feistel Ciphers[J].Frontiers of Computer Science in China,2009.3(4).494-502.

[5] Wu W.,Zhang W.,Lin D.On the Security of Generalized Feistel Scheme with SP Round Function[J].International Journal of Network Security.2006.3(3).215-224.

[6] Shibutani K.On the Diffusion of Generalized Feistel Structures Regarding Differential and Linear Cryptanalysis[C]//Selected Areas in Cryptography'2010.Heidelberg:Springer.2011:211-228.

[7] Wang M.,Liu J.,Wang X.The upper bounds on differential characteristics in block cipher SMS4[DB/OL]. (2010-03-25)[2014-08-10].http://eprint.iacr.org/ 2010/155.pdf.

[8] Matsui M.:Differential Path Search of the Block Cipher E2[C]//International Superconductive Electronics Conference'1999.[s.l.]:[s.n.].1999:57-64.

[9] Aoki K.,Ichikawa T.,Kanda M.,et al.Camellia:A 128-bit Block Cipher Suitable for Multiple Platforms-Design and Analysis[C]//Selected Areas in Cryptography' 2000.Heidelberg:Springer.2001:39-56.

[10] Shirai T.,Shibutani K.Improving immunity of Feistel ciphers against differential cryptanalysis by using multiple MDS matrices[C]//Fast Software Encryption' 2004.[s.l.]:Springer.2004:260-278.

[11] Shirai,T.,Shibutani,K.:On Feistel Structures Using a Diffusion Switching Mechanism[C]//Fast Software Encryption'2006.Heidelberg:Springer.2006:41-56.

[12] Shirai T.,Araki K.On Generalized Feistel Structures U-sing the Diffusion Switching Mechanism[J].IEICE Trans.Fundam.Electron.Commun.Comput.Sci.2008. E91-A(8).2120-2129.

[13] Mouha N.,Wang Q.,Gu D.,Preneel B.Differential and linear cryptanalysis using mixed-integer linear programming[C]//7th International Conference on Information Security and Cryptology.Beijing:Springer. 2012:57-76.

[14] Wu S.,Wang M.Security evaluation against differential cryptanalysis for block Cipher structures[DB/OL]. (2011-10-06)[2014-08-10].http://eprint.iacr. org/2011/551.pdf.

MING Ya-yun(1989-),male,graduate student,mainly engaged in the design and analysis of block cipher.

祝世雄(1965—),男,硕士,研究员,主要研究方向为密码学;

ZHU Shi-xiong(1965-),male,M.Sci.,research fellow, mainly engaged in cryptography.

曹云飞(1971—),男,硕士,高级工程师,主要研究方向为密码学。

CAO Yun-fei(1971-),male,M.Sci.,senior engineer, mainly engaged in cryptography.

Search Algorithm for Differential Active S-boxes of Feistel Structure

MING Ya-yun,ZHU Shi-xiong,CAO Yun-fei
(Science and Technology on Communication Security Laboratory,Chengdu Sichuan 610041,China)

In order to design secure block ciphers,the ability of evaluation algorithm to resist differential cryptanalysis and linear cryptanalysis is of utmost importance.Currently,a relatively practical measure is to calculate the minimum quantity of differential active S-boxes,or the lower bound of the minimum quantity.In 2004,Shirai et al.proposed a search algorithm to estimate the lower bound of active S-boxes quantity of Feistel based on hamming weight at FSE conference.This paper points out the flaw of this proposed search algorithm,and based on a special branch cutting strategy,puts forward an improved scheme is introduced to upgrade the algorithm to a practical application level.

feistel;differential cryptanalysis;active S-boxes

TN918

1002-0802(2014)10-1207-04

10.3969/j.issn.1002-0802.2014.10.020