申 兵,霍家佳

(1.保密通信重點實驗室,四川成都610041;2.中國電子科技集團(tuán)公司第三十研究所,四川成都610041)

動態(tài)S盒的密碼性質(zhì)*

申 兵1,霍家佳2

(1.保密通信重點實驗室,四川成都610041;2.中國電子科技集團(tuán)公司第三十研究所,四川成都610041)

劉國強(qiáng)和金晨輝給出了動態(tài)S盒差分概率的定義,分析了其不可能差分的特性、最大差分概率的上界及可達(dá)性,這是首個從動態(tài)S盒的概念和性質(zhì)方面的研究。沿著這個方向,本文給出動態(tài)線性概率、動態(tài)非線性度、動態(tài)代數(shù)次數(shù)、動態(tài)代數(shù)免疫階等定義,分析了這些動態(tài)性能指標(biāo)的界及可達(dá)性,并用仿真模擬的方法驗證了定義的合理性和定理的正確性,同時還分析了動態(tài)S盒的性能隨規(guī)模變化的規(guī)律。

動態(tài)S盒 動態(tài)差分概率 動態(tài)線性概率 動態(tài)非線性度 動態(tài)代數(shù)次數(shù) 動態(tài)代數(shù)免疫階

0 引 言

S盒(Substitution Box)是在密碼算法設(shè)計中廣泛使用的一類非線性部件,能夠為算法提供好的非線性性,并具有良好的數(shù)學(xué)模型和較系統(tǒng)的評價指標(biāo),理論基礎(chǔ)較為完善,但研究成果較少,存在一定的研究難度。

S盒首次出現(xiàn)在Lucife算法中,隨后因DES的使用而廣為流行。如DES使用8個6入4出S盒, AES、SMS4、Camellia使用有限域GF(28)上乘法求逆變換構(gòu)造的S盒,MARS使用隨機(jī)產(chǎn)生的8入32出S盒,序列密碼RC4則完全依賴于一個隨時間變化的8入8出S盒。

S盒的使用模式大致分為兩類,一類是靜態(tài)使用,即S盒在算法中始終保持不變,如前面提到的

AES、SMS4、Camellia、MARS等,另一類是動態(tài)使用,即在算法中動態(tài)可變,如RC4每運(yùn)行一拍,S盒的某兩個位置的值交換一次,還有一些分組密碼算法使用與密鑰相關(guān)的S盒,密鑰每變化一次,S盒動態(tài)改變一次,如Khufu,Blowfish,Twofish,PRINTcipher。

算法中動態(tài)使用S盒的主要目的是提高算法的安全性,1995年,E.Biham提出一種使用密鑰相關(guān)S盒的方法來改進(jìn)DES[1],分析表明改進(jìn)后的DES在抗差分密碼分析和線性密碼分析的性能上有所提升,作者在文中寫道:

“只有在知道S盒的內(nèi)容的前提下,線性攻擊和差分攻擊才可以實施,如果S盒依賴于密鑰,且通過強(qiáng)有力的密碼方法選取,則線性攻擊和差分攻擊會更困難”。

Khufu的S盒本身是秘密的,從密鑰擴(kuò)展得來,每8輪使用一個,即第一個8輪使用第一個S盒,第二個8輪使用第二個S盒,以此類推。由于Khufu有一個與密鑰相關(guān)的秘密S盒,它對抗差分密碼分析起到很重要的作用,對16輪最好的攻擊需要243個選擇明文和243次操作[2]。

Twofish的密鑰相關(guān)S盒是這樣構(gòu)造的,使用兩個8入8出固定S盒q0和q1,以及密鑰,構(gòu)造4個密鑰相關(guān)S盒,首先對密鑰作一個線性變換,得到k個32比特數(shù)據(jù)L0,L1,…,Lk-1,其中k根據(jù)密鑰長度可以取2,3,4。對32比特輸入X,將其分為4個字節(jié),每個字節(jié)查兩個固定S盒中的一個,然后異或密鑰數(shù)據(jù),重復(fù)上述步驟至少k次,再查一次固定S盒,得到32比特輸出Y。如圖1所示。

圖1 Twofish密鑰相關(guān)S盒構(gòu)造示意Fig.1 Construction key related S-box of Twofish

作者在其設(shè)計文檔中聲稱,設(shè)計密鑰相關(guān)的動態(tài)S盒的目的是為了抗差分攻擊、高階差分攻擊、線性攻擊、相關(guān)密鑰攻擊,而且,如果動態(tài)S盒設(shè)計得當(dāng),這樣做是有效的。

動態(tài)S盒的研究方向包括產(chǎn)生方法、密碼學(xué)性質(zhì)研究、以及在算法中的使用模式等。文獻(xiàn)[3]研究了隨機(jī)產(chǎn)生S盒的密碼學(xué)性質(zhì),并給出了一種構(gòu)造依賴于密鑰的隨機(jī)S盒的產(chǎn)生方法。文獻(xiàn)[4]研究了隨機(jī)交換S盒的兩個位置上的值后密碼學(xué)性質(zhì)的變化特征。文獻(xiàn)[5]則針對有限域上求逆變換構(gòu)造的S盒,給出了交換位置后差分概率不降低的條件,并給出了具體的構(gòu)造方法。

文獻(xiàn)[6]則針對有限域上求逆與仿射變換復(fù)合得到的動態(tài)S盒進(jìn)行研究,給出了動態(tài)S盒差分概率的刻畫方法,分析了其不可能差分的特性、最大差分概率的上界及可達(dá)性。這是首個從動態(tài)S盒的概念和性質(zhì)方面的研究。本文將沿著這個思路,給出一般意義下動態(tài)S盒的密碼學(xué)性質(zhì)的定義,并給出了動態(tài)S盒密碼性質(zhì)的界及可達(dá)性。

本文的第1節(jié)給出動態(tài)S盒的相關(guān)定義,第2節(jié)給出已有的結(jié)果,第3節(jié)給出并證明動態(tài)密碼性質(zhì)的界及可達(dá)性,第4節(jié)為仿真實驗,第5節(jié)為結(jié)論。

1 動態(tài)S盒的相關(guān)定義

設(shè)S:{0,1}n→{0,1}n為n比特S盒,An為{0, 1}n→{0,1}上的仿射布爾函數(shù)集,x·y表示x和y的內(nèi)積,wb(f(x))表示布爾函數(shù)f(x)的漢明重量,即f(x)值域中1的個數(shù)。用d(f(x),g(x))表示兩個布爾函數(shù)f(x)和g(x)的距離,即d(f(x),g(x)) =wb(f(x)⊕g(x))。

記E(·)為數(shù)學(xué)期望,用#{X}表示集合X的元素個數(shù),當(dāng)S的輸入差分為α,輸出差分為β的差分概率表示為

當(dāng)S的輸入掩蓋值為a,輸出掩蓋值為b的線性概率表示為

文獻(xiàn)[6]給出了動態(tài)S盒及其差分概率的定義,如下:

定義1(動態(tài)S盒)[6]設(shè):Si:{0,1}n→{0,1}n,i∈{0,1,…,m-1},則稱{Si}為動態(tài)S盒,并稱動態(tài)S盒由S0,S1,…,Sm-1構(gòu)成。

不失一般性,本文總假設(shè)控制參數(shù)服從均勻

分布。

定義2(動態(tài)S盒的差分概率)[6]設(shè):Si:{0,1}n→{0,1}n,i∈{0,1,…,m-1},α,β∈{0,1}n,則稱(α→β)=E((α→β)=(α→β)為動態(tài)S盒{S}i的差分對應(yīng)α→β的差分概率。稱為maxα≠0,β((α→β))動態(tài)S盒的最大差分概率。

類似地,我們給出動態(tài)線性概率、動態(tài)非線性度、動態(tài)代數(shù)次數(shù)、以及動態(tài)代數(shù)免疫階的定義:

定義3 設(shè)Si:{0,1}n→{0,1}n,i∈{0,1,…,m-1},a,b∈{0,1}n,則:

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

表示Si和l的距離。稱

(3)設(shè)deg(Si)為Si的代數(shù)次數(shù),則稱

(4)稱

從定義可以看出,當(dāng)m=1時,定義2和定義3即為S盒的密碼性質(zhì)在通常意義下的定義。

2 已有的結(jié)果

關(guān)于單個S盒的密碼學(xué)性質(zhì),已得到深入的研究,關(guān)于其理論界,已有以下已知的結(jié)果:

定理1設(shè)S為一個n入n出S盒,則:

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

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

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

(4)代數(shù)次數(shù)deg(S)≤n.

(5)代數(shù)免疫階AI(S)≤

.

在產(chǎn)生S盒時,應(yīng)使各項指標(biāo)達(dá)到或者盡可能地接近上述的界。

文獻(xiàn)[6]則針對有限域上求逆與仿射變換復(fù)合得到的動態(tài)S盒進(jìn)行研究,有以下結(jié)果:

定理2設(shè)n為偶數(shù),動態(tài)S盒由GF(2n)的乘法逆變換及[GF(2)]n上的m個仿射變換Li(x)=Aix⊕ai的復(fù)合構(gòu)成,且任意的β∈GF(2n){0},對1≤i≠j≤m均成立,則動態(tài)S盒的差分概率≤21-n(m+1)/m.

定理3設(shè)n為偶數(shù),m＜n,動態(tài)S盒由GF(2n)的乘法逆變換x-1及GF(2n)上的m個一次可逆函數(shù)Li(x)=aix⊕bi構(gòu)成且a1,a2,…,am互不相同,α,β∈GF(2n){0}。則動態(tài)S盒的差分對應(yīng)α→β的差分概率為21-n(m+1)/m,當(dāng)且僅當(dāng)存在1≤j≤m使得α×β=ai,且對1≤j≤m均有TrGF(2n)(×aj)=0。

文獻(xiàn)[6]只對特殊類型的動態(tài)S盒的差分概率做了研究,實際上可以容易地將它推廣到一般的S盒,下面各節(jié)是相關(guān)的結(jié)果。

3 動態(tài)S盒的密碼性質(zhì)及其構(gòu)造準(zhǔn)則

文獻(xiàn)[1]給出了AES的S盒在仿射動態(tài)變換下的密碼學(xué)性質(zhì),這種仿射動態(tài)變化的數(shù)量有限,不能滿足實際的需求。這里我們給出一般意義下的動態(tài)S盒的密碼學(xué)性質(zhì)。

定理4 設(shè){S0,S1,…,Sm-1}為動態(tài)S盒,且對每一個i∈{0,1,…,m-1}有:

(3)nl(Si)=n.

(4)deg(Si)=d.

(5)AI(Si)=a.

則動態(tài)S盒的相應(yīng)密碼性質(zhì)也滿足這些界,即:

對應(yīng)α→β,使得對每一個i∈{0,1,…,m-1},有(α→β)=p.

(2)≤q.而且,plS=q當(dāng)且僅當(dāng)存在一對線性近似a→b,使得對每一個i∈{0,1,…,m-1},有

(a→b)=q.

(3)nl(S)≥n.而且,nl(S)=n當(dāng)且僅當(dāng)存在l∈An,使得對每一個i∈{0,1,…,m-1},有d(Si,l) =n.

(4)deg(S)=d.

(5)AI(S)≥a.而且,AI(S)=a當(dāng)且僅當(dāng)存在一個多項式函數(shù)P(X,Y),使得對每一個i∈{0,1,…,m-1},在Y=Si(X)且P(X,Y)=0的條件下,deg(P(X,Y))=a.

從定義2和定義3出發(fā)可以很容易地證明定理4,這里不再贅述。

由定理4,在產(chǎn)生動態(tài)S盒時,其中單個的S盒要滿足一定密碼學(xué)指標(biāo)外,作為一個整體的動態(tài)S盒還要滿足一定的動態(tài)性質(zhì),主要有:

(1)動態(tài)差分概率盡可能小。

(2)動態(tài)線性概率盡可能小。

(3)動態(tài)非線性度盡可能大。

(4)動態(tài)代數(shù)次數(shù)盡可能大。

(5)動態(tài)代數(shù)免疫階盡可能大。

4 模擬實驗

本節(jié)利用模擬實驗驗證定義3的合理性以及定理4的正確性,首先隨機(jī)產(chǎn)生256個8入8出的S盒,對每一個i=1,2,…,256,滿足:

(1)≤2-4.

(2)≤2-4.

(3)nl(S)≤96.

(4)deg(Si)=7.然后按照定義3測試它們的動態(tài)差分概率、動態(tài)線性概率、動態(tài)非線性度、和動態(tài)代數(shù)次數(shù),結(jié)果為:

(1)=2-7.5.

(2)=2-8.1.

(3)nl(Si)=104.7.

(4)deg(Si)=7.

由此驗證了定義3和定理4的合理性和正確性,也可以看出,動態(tài)S盒的密碼學(xué)性能比單個的S盒的性能要好,甚至超過了單個S盒的理論界。

動態(tài)S盒的個數(shù)取多少合適?很難有一個理論的量化結(jié)論,這里仍然通過模擬的方法研究動態(tài)S盒的密碼學(xué)性能隨著個數(shù)變化的規(guī)律。隨機(jī)產(chǎn)生m個S盒,每個S盒滿足上述4個條件,然后測試其動態(tài)密碼學(xué)性能,結(jié)果如表1所示。

表1 隨機(jī)動態(tài)S盒單個密碼性能比較表Table 1 Comparison of the single cryptographic property of random dynamic S-box

從表1可以看出,動態(tài)S盒的代數(shù)次數(shù)不會隨著m的變化而變化,動態(tài)非線性度、隨著m增大而增大,但增加的速度比較慢,動態(tài)差分概率和動態(tài)線性概率隨m的增大而增大,且增加的速度比較快。所以,動態(tài)S盒對提升差分和線性性能的優(yōu)勢明顯,對提升非線性度的優(yōu)勢一般,對提升代數(shù)次數(shù)沒有作用。如果只滿足差分和線性性能,m取8就夠了,若還考慮到非線性度,m應(yīng)該取得比較大,但這也會增加實現(xiàn)的資源耗費,所以在實際中最好折衷考慮。

下面對每個S盒的密碼性質(zhì)不作限制的條件下隨機(jī)產(chǎn)生S盒,考察它們的動態(tài)性質(zhì)。首先隨機(jī)產(chǎn)生256個隨機(jī)S盒,然后按照定義3測試它們的動態(tài)差分概率、動態(tài)線性概率、動態(tài)非線性度、和動態(tài)代數(shù)次數(shù),結(jié)果為:

(1)=2-6.95.

(2)=2-8.0.

(3)nl(Si)=104.7.

(4)deg(Si)=6.99.

比較這兩種產(chǎn)生隨機(jī)S盒的方法對動態(tài)性能的影響,可以看出,限定單個S盒的指標(biāo)與不限定,其動態(tài)性能的差別并不大,后者只是稍微弱了一點點,但由于不限定指標(biāo)產(chǎn)生S盒不需要測試,從而節(jié)省了不少計算資源和時間,所以,在某些資源受限且需要在線產(chǎn)生S盒的場合,完全可以用后一種方式。

下面同樣測試動態(tài)性質(zhì)隨規(guī)模變化的規(guī)律,如表2所示。

表2 隨機(jī)動態(tài)S盒多個S盒指標(biāo)的密碼性能比較表Table 2 Comparison ofmulti-cryptographic properties of randomdynamic S-box

從表2也同樣可以看出,除了代數(shù)次數(shù)外,規(guī)模越大,動態(tài)性能越好,動態(tài)代數(shù)次數(shù)例外的原因是只要有一個差一點,動態(tài)性能就要下降,m越小,取到小于7的概率越小,所以表中前三個都是7而后面卻小于7,也可以看出當(dāng)m取到較大,性能也趨于穩(wěn)定且也有逐漸變好的趨勢。

5 結(jié) 語

本文在文獻(xiàn)[6]的基礎(chǔ)上,給出了動態(tài)S盒的動態(tài)差分概率、動態(tài)線性概率、動態(tài)非線性度、動態(tài)代數(shù)次數(shù)、以及動態(tài)代數(shù)免疫階的定義,在給定單個

S盒的這些指標(biāo)的前提下,給出了對應(yīng)動態(tài)性能的界,并用模擬的方法驗證了定義的合理性和定理的正確性,同時還分析了動態(tài)S盒的性能隨規(guī)模變化的規(guī)律,對實際的動態(tài)算法設(shè)計有重要的指導(dǎo)作用。如何利用這些性能分析動態(tài)密碼算法的安全性,以及如何快速在線產(chǎn)生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] 劉國強(qiáng),金晨輝.一類動態(tài)S盒的構(gòu)造與差分性質(zhì)研究[J].電子與信息學(xué)報,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

國家自然科學(xué)基金(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)