动态S盒的密码性质*

申 兵,霍家佳

(1.保密通信重点实验室,四川成都610041;2.中国电子科技集团公司第三十研究所,四川成都610041)

动态S盒的密码性质*

申 兵1,霍家佳2

(1.保密通信重点实验室,四川成都610041;2.中国电子科技集团公司第三十研究所,四川成都610041)

刘国强和金晨辉给出了动态S盒差分概率的定义,分析了其不可能差分的特性、最大差分概率的上界及可达性,这是首个从动态S盒的概念和性质方面的研究。沿着这个方向,本文给出动态线性概率、动态非线性度、动态代数次数、动态代数免疫阶等定义,分析了这些动态性能指标的界及可达性,并用仿真模拟的方法验证了定义的合理性和定理的正确性,同时还分析了动态S盒的性能随规模变化的规律。

动态S盒 动态差分概率 动态线性概率 动态非线性度 动态代数次数 动态代数免疫阶

0 引 言

S盒(Substitution Box)是在密码算法设计中广泛使用的一类非线性部件,能够为算法提供好的非线性性,并具有良好的数学模型和较系统的评价指标,理论基础较为完善,但研究成果较少,存在一定的研究难度。

S盒首次出现在Lucife算法中,随后因DES的使用而广为流行。如DES使用8个6入4出S盒, AES、SMS4、Camellia使用有限域GF(28)上乘法求逆变换构造的S盒,MARS使用随机产生的8入32出S盒,序列密码RC4则完全依赖于一个随时间变化的8入8出S盒。

S盒的使用模式大致分为两类,一类是静态使用,即S盒在算法中始终保持不变,如前面提到的

AES、SMS4、Camellia、MARS等,另一类是动态使用,即在算法中动态可变,如RC4每运行一拍,S盒的某两个位置的值交换一次,还有一些分组密码算法使用与密钥相关的S盒,密钥每变化一次,S盒动态改变一次,如Khufu,Blowfish,Twofish,PRINTcipher。

算法中动态使用S盒的主要目的是提高算法的安全性,1995年,E.Biham提出一种使用密钥相关S盒的方法来改进DES[1],分析表明改进后的DES在抗差分密码分析和线性密码分析的性能上有所提升,作者在文中写道:

“只有在知道S盒的内容的前提下,线性攻击和差分攻击才可以实施,如果S盒依赖于密钥,且通过强有力的密码方法选取,则线性攻击和差分攻击会更困难”。

Khufu的S盒本身是秘密的,从密钥扩展得来,每8轮使用一个,即第一个8轮使用第一个S盒,第二个8轮使用第二个S盒,以此类推。由于Khufu有一个与密钥相关的秘密S盒,它对抗差分密码分析起到很重要的作用,对16轮最好的攻击需要243个选择明文和243次操作[2]。

Twofish的密钥相关S盒是这样构造的,使用两个8入8出固定S盒q0和q1,以及密钥,构造4个密钥相关S盒,首先对密钥作一个线性变换,得到k个32比特数据L0,L1,…,Lk-1,其中k根据密钥长度可以取2,3,4。对32比特输入X,将其分为4个字节,每个字节查两个固定S盒中的一个,然后异或密钥数据,重复上述步骤至少k次,再查一次固定S盒,得到32比特输出Y。如图1所示。

图1 Twofish密钥相关S盒构造示意Fig.1 Construction key related S-box of Twofish

作者在其设计文档中声称,设计密钥相关的动态S盒的目的是为了抗差分攻击、高阶差分攻击、线性攻击、相关密钥攻击,而且,如果动态S盒设计得当,这样做是有效的。

动态S盒的研究方向包括产生方法、密码学性质研究、以及在算法中的使用模式等。文献[3]研究了随机产生S盒的密码学性质,并给出了一种构造依赖于密钥的随机S盒的产生方法。文献[4]研究了随机交换S盒的两个位置上的值后密码学性质的变化特征。文献[5]则针对有限域上求逆变换构造的S盒,给出了交换位置后差分概率不降低的条件,并给出了具体的构造方法。

文献[6]则针对有限域上求逆与仿射变换复合得到的动态S盒进行研究,给出了动态S盒差分概率的刻画方法,分析了其不可能差分的特性、最大差分概率的上界及可达性。这是首个从动态S盒的概念和性质方面的研究。本文将沿着这个思路,给出一般意义下动态S盒的密码学性质的定义,并给出了动态S盒密码性质的界及可达性。

本文的第1节给出动态S盒的相关定义,第2节给出已有的结果,第3节给出并证明动态密码性质的界及可达性,第4节为仿真实验,第5节为结论。

1 动态S盒的相关定义

设S:{0,1}n→{0,1}n为n比特S盒,An为{0, 1}n→{0,1}上的仿射布尔函数集,x·y表示x和y的内积,wb(f(x))表示布尔函数f(x)的汉明重量,即f(x)值域中1的个数。用d(f(x),g(x))表示两个布尔函数f(x)和g(x)的距离,即d(f(x),g(x)) =wb(f(x)⊕g(x))。

记E(·)为数学期望,用#{X}表示集合X的元素个数,当S的输入差分为α,输出差分为β的差分概率表示为

当S的输入掩盖值为a,输出掩盖值为b的线性概率表示为

文献[6]给出了动态S盒及其差分概率的定义,如下:

定义1(动态S盒)[6]设:Si:{0,1}n→{0,1}n,i∈{0,1,…,m-1},则称{Si}为动态S盒,并称动态S盒由S0,S1,…,Sm-1构成。

不失一般性,本文总假设控制参数服从均匀

分布。

定义2(动态S盒的差分概率)[6]设:Si:{0,1}n→{0,1}n,i∈{0,1,…,m-1},α,β∈{0,1}n,则称(α→β)=E((α→β)=(α→β)为动态S盒{S}i的差分对应α→β的差分概率。称为maxα≠0,β((α→β))动态S盒的最大差分概率。

类似地,我们给出动态线性概率、动态非线性度、动态代数次数、以及动态代数免疫阶的定义:

定义3 设Si:{0,1}n→{0,1}n,i∈{0,1,…,m-1},a,b∈{0,1}n,则:

(2)给定l(x)∈An,

表示Si和l的距离。称

(3)设deg(Si)为Si的代数次数,则称

(4)称

从定义可以看出,当m=1时,定义2和定义3即为S盒的密码性质在通常意义下的定义。

2 已有的结果

关于单个S盒的密码学性质,已得到深入的研究,关于其理论界,已有以下已知的结果:

定理1设S为一个n入n出S盒,则:

(1)非线性度nl(S)≤2n-1-.

(2)差分概率≥21-n.

(3)线性概率≥2-n.

(4)代数次数deg(S)≤n.

(5)代数免疫阶AI(S)≤

.

在产生S盒时,应使各项指标达到或者尽可能地接近上述的界。

文献[6]则针对有限域上求逆与仿射变换复合得到的动态S盒进行研究,有以下结果:

定理2设n为偶数,动态S盒由GF(2n)的乘法逆变换及[GF(2)]n上的m个仿射变换Li(x)=Aix⊕ai的复合构成,且任意的β∈GF(2n){0},对1≤i≠j≤m均成立,则动态S盒的差分概率≤21-n(m+1)/m.

定理3设n为偶数,m＜n,动态S盒由GF(2n)的乘法逆变换x-1及GF(2n)上的m个一次可逆函数Li(x)=aix⊕bi构成且a1,a2,…,am互不相同,α,β∈GF(2n){0}。则动态S盒的差分对应α→β的差分概率为21-n(m+1)/m,当且仅当存在1≤j≤m使得α×β=ai,且对1≤j≤m均有TrGF(2n)(×aj)=0。

文献[6]只对特殊类型的动态S盒的差分概率做了研究,实际上可以容易地将它推广到一般的S盒,下面各节是相关的结果。

3 动态S盒的密码性质及其构造准则

文献[1]给出了AES的S盒在仿射动态变换下的密码学性质,这种仿射动态变化的数量有限,不能满足实际的需求。这里我们给出一般意义下的动态S盒的密码学性质。

定理4 设{S0,S1,…,Sm-1}为动态S盒,且对每一个i∈{0,1,…,m-1}有:

(3)nl(Si)=n.

(4)deg(Si)=d.

(5)AI(Si)=a.

则动态S盒的相应密码性质也满足这些界,即:

对应α→β,使得对每一个i∈{0,1,…,m-1},有(α→β)=p.

(2)≤q.而且,plS=q当且仅当存在一对线性近似a→b,使得对每一个i∈{0,1,…,m-1},有

(a→b)=q.

(3)nl(S)≥n.而且,nl(S)=n当且仅当存在l∈An,使得对每一个i∈{0,1,…,m-1},有d(Si,l) =n.

(4)deg(S)=d.

(5)AI(S)≥a.而且,AI(S)=a当且仅当存在一个多项式函数P(X,Y),使得对每一个i∈{0,1,…,m-1},在Y=Si(X)且P(X,Y)=0的条件下,deg(P(X,Y))=a.

从定义2和定义3出发可以很容易地证明定理4,这里不再赘述。

由定理4,在产生动态S盒时,其中单个的S盒要满足一定密码学指标外,作为一个整体的动态S盒还要满足一定的动态性质,主要有:

(1)动态差分概率尽可能小。

(2)动态线性概率尽可能小。

(3)动态非线性度尽可能大。

(4)动态代数次数尽可能大。

(5)动态代数免疫阶尽可能大。

4 模拟实验

本节利用模拟实验验证定义3的合理性以及定理4的正确性,首先随机产生256个8入8出的S盒,对每一个i=1,2,…,256,满足:

(1)≤2-4.

(2)≤2-4.

(3)nl(S)≤96.

(4)deg(Si)=7.然后按照定义3测试它们的动态差分概率、动态线性概率、动态非线性度、和动态代数次数,结果为:

(1)=2-7.5.

(2)=2-8.1.

(3)nl(Si)=104.7.

(4)deg(Si)=7.

由此验证了定义3和定理4的合理性和正确性,也可以看出,动态S盒的密码学性能比单个的S盒的性能要好,甚至超过了单个S盒的理论界。

动态S盒的个数取多少合适?很难有一个理论的量化结论,这里仍然通过模拟的方法研究动态S盒的密码学性能随着个数变化的规律。随机产生m个S盒,每个S盒满足上述4个条件,然后测试其动态密码学性能,结果如表1所示。

表1 随机动态S盒单个密码性能比较表Table 1 Comparison of the single cryptographic property of random dynamic S-box

从表1可以看出,动态S盒的代数次数不会随着m的变化而变化,动态非线性度、随着m增大而增大,但增加的速度比较慢,动态差分概率和动态线性概率随m的增大而增大,且增加的速度比较快。所以,动态S盒对提升差分和线性性能的优势明显,对提升非线性度的优势一般,对提升代数次数没有作用。如果只满足差分和线性性能,m取8就够了,若还考虑到非线性度,m应该取得比较大,但这也会增加实现的资源耗费,所以在实际中最好折衷考虑。

下面对每个S盒的密码性质不作限制的条件下随机产生S盒,考察它们的动态性质。首先随机产生256个随机S盒,然后按照定义3测试它们的动态差分概率、动态线性概率、动态非线性度、和动态代数次数,结果为:

(1)=2-6.95.

(2)=2-8.0.

(3)nl(Si)=104.7.

(4)deg(Si)=6.99.

比较这两种产生随机S盒的方法对动态性能的影响,可以看出,限定单个S盒的指标与不限定,其动态性能的差别并不大,后者只是稍微弱了一点点,但由于不限定指标产生S盒不需要测试,从而节省了不少计算资源和时间,所以,在某些资源受限且需要在线产生S盒的场合,完全可以用后一种方式。

下面同样测试动态性质随规模变化的规律,如表2所示。

表2 随机动态S盒多个S盒指标的密码性能比较表Table 2 Comparison ofmulti-cryptographic properties of randomdynamic S-box

从表2也同样可以看出,除了代数次数外,规模越大,动态性能越好,动态代数次数例外的原因是只要有一个差一点,动态性能就要下降,m越小,取到小于7的概率越小,所以表中前三个都是7而后面却小于7,也可以看出当m取到较大,性能也趋于稳定且也有逐渐变好的趋势。

5 结 语

本文在文献[6]的基础上,给出了动态S盒的动态差分概率、动态线性概率、动态非线性度、动态代数次数、以及动态代数免疫阶的定义,在给定单个

S盒的这些指标的前提下,给出了对应动态性能的界,并用模拟的方法验证了定义的合理性和定理的正确性,同时还分析了动态S盒的性能随规模变化的规律,对实际的动态算法设计有重要的指导作用。如何利用这些性能分析动态密码算法的安全性,以及如何快速在线产生S盒等问题,是未来研究的方向。

[1] BIHAM E.and BIRYUKOV A..How to Strengthen DES using Existing Hardware[C]//Advances in Cryptology-ASIACRYPT'94,Springer-Verlag,1995.

[2] H.GILLBERT and P.CHAUVAUD.A Chosen Plaintext Attack of the 16-Round Khufu Cryptosystem[C]//Advances in Cryptology-CRYPTO'94,Springer-Verlag, 1994:259-268.

[3] LIAM Keliher.Substitution Permutation Network Cryptosystems Using Key Dependent S-Boxes[D].Kingston, Ontario,Canada:Queen's University,1997.

[4] YU Yuyin.Wang Mingsheng,Li Yongqiang.Constructing differentially 4 uniform functions from known ones[J].Chinese Journal of Electronics,2013,22(3):495-499.

[5] QU Longjiang,Tan Yin,Tan Chikhow,Li Chao.Constructing Differentially 4-Uniform Permutations Over via the Switching Method[J].IEEE Transactions on Information Theory.2013,59(7),4675-4686.

[6] 刘国强,金晨辉.一类动态S盒的构造与差分性质研究[J].电子与信息学报,2014,36(1):74-81.

LIU Guo-qiang,JIN Chen-hui,Investigation on Construction and Differential Property of a Classof Dynamic S-box [J],Journal of Electronics&Information Technology. 2014,36(1):74-81.

申 兵(1971—),男,硕士,高级工程师,主要研究方向为信息安全与通信保密;

SHEN Bing(1971—),male,M.Sci.,senior engineer,mainly engaged in information security and communications privacy.

霍家佳(1978—),女,硕士,高级工程师,主要研究方向为信息安全与通信保密。

HUO Jia-jia(1978—),female,M.Sci.,senior engineer,mainly engaged in information security and communications privacy.

Cryptographic Property of Dynam ic S-box

SHEN Bing1,HUO Jia-jia2
(1.Science and Technology on Communication Security Laboratory,Chengdu Sichuan 610041,China;
2.No.30 Institute of CETC,Chengdu Sichuan 610041,China)

LIU Guo-qiang and JIN Chen-huigives the definition of differential probability for dynamic S-box,analyze the charicteristics of impossible difference and the upper-bound and accessibility ofmaximum differential probability for dynamic S-box.This is the first try on the research of dynamic S-box's definition and properties.In lightof this,the definitions of dynamic linear probability,dynamic nonlinearity,dynamic algebraic degree and dynamic algebraic immunity are proposed,and the bounds of these cryptographic criterions and the accessibility of these bounds analyzed.Simulation experiments verify the rationality and validity of the definitions.Meanwhile,the rule of dynamic property with the change of dynamic S-box's size is also given.

dynamic S-box;dynamic differential probability;dynamic linear probability;dynamic nonlinearity;dynamic algebraic degree;dynamic algebraic immunity

TN918.1

A

1002-0802(2014)12-1429-05

10.3969/j.issn.1002-0802.2014.12.017

2014-09-02;

2014-11-12 Received date：2014-09-02;Revised date：2014-11-12

国家自然科学基金(No.61309034)资助;四川省科技厅杰出青年基金项目(2014JQ0055)资助

Foundation Item:National Natural Science Foundation of China(No.61309034);Outstanding Youth Foundation of the Science and Technology Department in Sichuan Province(2014JQ0055)