一类广义Feistel结构的安全性分析

徐林杰 王春红 彭 聪 刘丽辉

(中国船舶重工集团公司第七二二研究所 武汉 430079)

一类广义Feistel结构的安全性分析

徐林杰 王春红 彭 聪 刘丽辉

(中国船舶重工集团公司第七二二研究所 武汉 430079)

广义Feistel结构(以下简称GFS)的形式多种多样,广泛应用于分组密码设计。论文定义了一类GFS为GFSRP,研究了整体结构为GFSRP-SP结构(GFSRP的F函数是SP型结构)的分组密码的性质。考虑到实际应用,论文给出一个4子块的GFSRP-SP结构的实例,并通过建立搜索算法,得到了更精确的活动S盒个数的下界。结果表明,4子块的GFSRP-SP结构具有较好的抵抗差分攻击与线性攻击的能力,可应用于分组密码设计。

分组密码; 广义Feistel结构; 活动S盒

Class Number TP393

1 引言

整体结构作为分组密码的重要特征,对分组密码的实现效率与安全性都有非常大的影响。国内外公开的分组密码最为常见的整体结构是SPN结构和Feistel结构。广义Feistel结构(以下简称GFS)是Feistel结构的一种推广,同样具有Feistel结构加解密相似的特点。Feistel结构将输入分组分为2个子块,而GFS将输入分组分为k(k>2)个子块。这样做,一方面使得F函数的规模小,更好设计;另一方面使得软硬件实现代价更低。广义Feistel结构的形式多种多样,如Ⅰ-型[1]GFS、Ⅱ-型[1]GFS、Nyberg-型[2]GFS等。整体结构采用GFS的分组密码设计,较为常见的是将输入分组分为四个子块,如SMS4[3]、CAST-256[4]、CLEFIA[5]等。

对整体结构的安全性研究,一直是密码学领域的研究热点。设计安全的分组密码,一定要评估该密码抵抗差分攻击与线性攻击的能力,目前常用的评估方法是估计活动S盒个数的下界[5]。对SPN结构和Feistel结构,通常采用理论证明的方法[6～7],而对于GFS,由于其形式多种多样,分析方法也不尽相同。文献[8]利用理论证明的方法研究了SMS4算法结构的活动S盒个数的下界,文献[5]采用建立搜索算法的方式研究了CLEFIA算法的活动S盒个数的下界,同样的方法,文献[9]对文献[5]的方法加以改进,研究了Ⅰ-型、Ⅱ-型和Nyberg-型GFS活动S盒的个数的下界。

对于以上提到的GFS,这些结构的特点,都是一个或者若干个子块进入F函数,然后再进入扩散层。扩散层都是基于子块位置的置乱,可以看作一个置换。值得思考的是,扩散层是否一定是这种基于子块位置的置乱?能否将子块拆分成更小的单元,再将这些更小的单元位置置乱?如果这样做,对这种结构抵抗差分攻击与线性攻击的能力应该怎样评估?本文对这几个问题进行了研究。

2 基础知识

为方便描述,本文先引入文献[10]的定义。k为偶数,k子块的GFSπ是({0,1}n)k上的置换,定义如下:

定义1[10]:(X0,X1,…,Xk-1)→π(X0,F0(X0)⊕X1,X2,F1(X2)⊕X3,…,F(k-2)/2(Xk-2)⊕Xk-1)

其中,Fi:{0,1}n→{0,1}n是F函数,π:({0,1}n)k→({0,1}n)k是一个子块位置置乱、可看作是一个置换,k是子块的个数,n是一个子块的比特长度,则称具有这样结构的置换为GFSπ。GFSπ如图1所示。

对于GFSπ,π置换的选取不同,对应的结构就不同。目前分组密码设计中较为常用的是4子块的GFS(即k=4)。于是,令k=4,当π(Y0,Y1,Y2,Y3)=(Y1,Y2,Y3,Y0),即为4子块的Ⅱ-型GFS,结构如图2所示;当π(Y0,Y1,Y2,Y3)=(Y1,Y3,Y0,Y2),即为4子块的Nyberg-型GFS,结构如图3所示。Ⅰ-型GFS不是GFSπ置换,但与Ⅰ-型GFS与Ⅱ-型GFS的结构类似,如图4所示。这两种结构,相同的是π置换一致,都是循环左移一个子块;不同的是,单轮Ⅱ-型GFS有k/2个F函数,而单轮Ⅰ-型GFS只有1个F函数。

定义2:(X0,X1,…,Xk-1)→RP(X0,F0(X0)⊕X1,X2,F1(X2)⊕X3,…,F(k-2)/2(Xk-2)⊕Xk-1)。

其中,Fi:{0,1}→{0,1}n是F函数,RP:({0,1}n/2)2×k→({0,1}n/2)k×2是一个置换。则称具有这样结构的置换为GFSRP。

文献[10]指出,为了达到最优扩散效果,GFSπ的π置换应具有这样的特点:任意一个奇数的输入子块都应映射为偶数的输出子块。同样,为了使GFSRP具有较好的扩散效果,本文对RP置换做出相同要求,即RP置换的奇数的输入子块Y2i+1都应映射为偶数的输出子块Z2j,可表示为:RP(Y0,Y1,Y2,…,Yk-1)=(Z0,Z1,Z2,…,Zk-1),Z2j∈{Y1,Y3,…,Yk-2},0≤j≤k/2-1。与GFSπ一致的是,GFSRP也将每个分组分为k个子块;不同的是,GFSπ的π置换使k个子块的位置置乱,而GFSRP的RP置换将每个子块平均分为两个更小的单元,然后这2k个单元位置置乱。图5即为4子块的GFSRP的结构示意图。选用文献[11]中的置换作为RP置换,如图6所示。

差分攻击与线性攻击是分组算法最常用且很有效的攻击方法。为评估一个分组密码抵抗的这两种攻击的能力,通常采用估计这个分组密码差分特征(线性逼近)中活动S盒的个数的下界的方法。而活动S盒的个数与差分分支数与线性分支数密切相关。

定义3:一个差分特征中,如果S盒的输入差分不为零,则称此S盒是差分活动的;一个线性逼近中,如果一些输入和输出比特被涉及,则称此S盒是线性活动的。

为P的分支数。其中wb(x)表示非零xi(1≤i≤m)的个数,称为x的包重量。

类似地定义差分分支数与线性分支数的定义:

其中c(x·αt,P(x)·βt)=2×Pr(x·αt,P(x)·βt)-1,x·αt是矩阵乘。c(x·αt,P(x)·βt)≠0意味着α·x=β·y是有效线性逼近。上标t表示向量或矩阵的转置。

P的差分分支数与线性分支数的最大值为m+1。当变换P的差分分支数与线性分支数的均达到最大,则称P为最优扩散映射,其对应的矩阵M是m阶MDS矩阵。

3 GFSRP-SP结构的安全性分析

3.1 GFSRP-SP结构的性质

当R轮GFSRP-SP至少存在一个非零输入差分,显然有如下性质。

性质1:任意连续2轮k子块的GFSRP-SP结构,至少有1个F函数有差分活动S盒。

这个性质是由于GFSRP-SP结构的可逆性。如果连续2轮加密的k个F函数均没有活动S盒,即没有非零的输入差分,则意味着这两轮加密之前的两轮的k个F函数均没有非零输入差分。同样的,这两轮加密之后的k个F函数也没有非零输入差分,以此类推目标结构不存在非零的输入差分,这与R轮GFSRP-SP结构至少存在一个非零输入差的前提条件相矛盾。

而由GFSRP-SP结构的定义,结合差分分支数的定义不难有如下性质。

性质2:任意连续3轮GFSRP-SP结构加密,其差分活动S盒个数有如下特点。

性质1考虑了连续两轮输入差分的关系,性质2考虑了连续三轮输入差分的关系。显然任意R(R≥3)轮GFSRP-SP结构迭代都要满足这两个性质。

3.2 搜索算法

对于一个分组密码,一般有两种方式统计活动S盒的个数。一种是理论证明的方式,一种是建立搜索算法的方式。理论证明得到的结果一般比较粗略,而针对算法结构建立搜索算法的方式往往时间消耗与资源消耗都比较大。于是,结合这两种方式,文献[9]提出了如下的搜索算法。

输入:R(轮数),STR(R轮算法结构)

输出:STR的活动S盒个数

步骤1:设定全局变量LBi=∞(1≤i≤R);

步骤2:fori=1 toR

Func(1,i);

步骤3:输出LBR;

其中,Func(x,r)如下:

步骤4:ifx=NFr+1

步骤5:ifx≠NFr+1

forj=0 tom

令Dx=j,并检测算法结构是否满足所有的限定条件,若满足,则进行如下步骤;

步骤5.1:ifx∉{NFk|1≤k≤r-1}

调用Func(x+1,r);

步骤5.2:ifx∈{NFk|1≤k≤r-1}

令z是一个满足x=NFz的整数,

调用Func(x+1,r)。

NFi是STR的前i轮F函数的个数。

3.3 4子块GFSRP-SP结构的差分(线性)活动S盒个数的下界

令m=4,P为最优扩散映射(即令Bd=5),以性质1与性质2为搜索条件,使用3.1节的搜索算法可以搜索4子块的GFSRP-SP的差分活动S盒个数的下界。由于P是最优扩散映射,差分分支数与线性分支数均为5,因此搜索算法中的限制条件相似,使得差分活动S盒个数的下界与线性活动S盒个数的下界相同,以下统称活动S盒。活动S盒的搜索结果如表1所示。

表1 性质结果

需要注意的是,GFSRP的扩散层不同于Ⅰ-型GFS、Ⅱ-型GFS、Nyberg-型GFS的扩散层。GFSRP的扩散层将每个子块平均分为两个更小的单元,RP置换是这些单元的位置置乱。因此GFSRP的性质应与RP置换的特点密切相关。以本文定义的RP置换,研究4子块的GFSRP-SP结构的差分(线性)活动S盒个数的下界。

更进一步地,有:

于是,根据以上的搜索算法,满足性质1～性质5时,有以下的搜索结果。

表2 搜索结果

3.4 对比与分析

当F函数为SP结构时,通过使用搜索算法,本文对比了4子块的Nyberg-型GFS、Ⅰ-型GFS、Ⅱ-型GFS与GFSRP的R轮活动S盒个数的下界。这四种结构中,均限定m=4,k=4,并且Bd=5。简称这三种结构为Nyberg、Ⅰ-型、Ⅱ-型,评估结果如表3所示。根据结果可以发现:GFSRP的扩散效果虽然不如Ⅱ-型GFS,但是明显好于Ⅰ-型GFS与Nyberg-型GFS。

表3 对比结果

4 结语

不同于常见的GFS的扩散层都是基于子块位置的置乱的结构特点,本文定义了一类GFS为GFSRP。该结构将子块拆分成更小的单元,再将这些更小的单元位置置乱。目前还没有国内外公开的分组密码使用GFSRP-SP结构,也没有GFSRP-SP结构安全性研究的文献。本文采与Feistel-SP结构相似的方法,研究了GFSRP-SP结构的性质。

特别地,考虑到实际应用,针对本文定义的4子块GFSRP-SP的结构特点,通过建立搜索算法,得到了更精确的活动S盒个数的下界。对于本文定义的4子块的GFSRP-SP结构,当P变换差分(线性)分支数为5,S盒的差分(线性)概率为2～6,则对于分组长度为128比特的GFSRP-SP结构分组密码,14轮迭代后,没有有效的差分(线性)特征,具有足够抵抗差分攻击与线性攻击的能力,具有实际应用价值。

[1] Y. Zheng, T. Matsumoto, H. Imai. On the construction of block ciphers probably secure and not relying on any unproved hypotheses[C]//Proc. Crypto’89, ed. G. Brassard, LNCS,1989,435:461-480.

[2] K. Nyberg. Generalized Feistel network[C]//Proc. Asiacrypt’96, ed. K. Kim and T. Mastsumoto, LNCS,1996,1163:91-104.

[3] 国家密码管理局公告第7号[EB/OL]. http://www.oscca.gov.cm,2006-01.

[4] ADAMS C. The CAST-256 encryption algorithm[J]. Computer Science & Communications Dictionary,2001,81(4):864-894.

[5] Shirai, T., Shibutani, K., Akishita, T., et al. The 128-bit Blockcipher CLEFIA[C]//Biryukov, A. (ed.) FSE 2007. LNCS, Springer, Heidelberg,2007,4593:181-195.

[6] J. Daemen, V. Rijmen. The Design of Rijndael[M]. Heidelberg: Springer,2002.

[7] Kanda M. Practical Security Evaluation against Differential and Linear Cryptanalyes for Feistel Ciphers with SPN round function[C]//SAC 2000. Heidelberg: Springer,2001:324-338.

[8] 吴文玲,贺也平.一类广义Feistel密码的安全性评估[J].电子与信息学报,2002,24(9):1177-1184.

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

[10] Tomoyasu Suzaki, Kazuhiko Minematsu. Improving the Generalized Feistel[C]//FSE 2010, LNCS 6147,2010:19-39.

[11] Shibutani, K., Isobe, T., Hiwatari, H., et al. Piccolo: An Ultra-Lightweight Blockcipher[C]//CHES 2011, LNCS 6917,2011:342-357.

Security Analysis on A Class of Generalized Feistel Structure

XU Linjie WANG Chunhong PENG Cong LIU Lihui

(No. 722 Research Institute of CSIC, Wuhan 430079)

The generalized Feistel structure (GFS) which is extensively applied in block cipher designing has kinds of forms. In this paper, a novel form of GFS is defined as GFSRP, and the character of this structure which F function is SP type either been studied. To practical application, a search algorithm is established to find lower bounds of number of active S-boxes for 4-subblocks GFSRP-SP which showed in this paper. The obtained result shows that 4-subblocks GFSRP-SP structure has good immunity against differential attack and linear attack, and can be applied in bock cipher design.

block cipher, generalized Feistel structure, active S-boxes

2016年8月12日,

2016年9月16日

徐林杰,男,硕士研究生,工程师,研究方向:通信安全。王春红,女,硕士研究生,高级工程师,研究方向:信息安全。彭聪,男,硕士研究生,工程师,研究方向:通信安全。刘丽辉,女,硕士研究生,工程师,研究方向:信息安全。

TP393

10.3969/j.issn.1672-9730.2017.02.014