基于混沌的雙模塊Feistel結(jié)構(gòu)高安全性高速分組密碼算法安全性分析

杜小妮 段娥娥王天心

(西北師范大學數(shù)學與統(tǒng)計學院 蘭州730070)

1 引言

分組密碼是密碼學的一個重要分支，在保護數(shù)據(jù)安全方面有著重要的地位，隨著1977年DES分組密碼算法的公開，開啟了分組密碼分析的新時代。影響分組密碼方案的安全因素有多種，如分組長度以及密鑰長度等。分析密碼安全性主要包括分析算法的部件性質(zhì)和分析算法的安全性。算法的部件性質(zhì)分析主要包括分析算法的結(jié)構(gòu)、S盒、線性層和密鑰擴展方案。對于算法的安全性分析主要包括1990年文獻[1]針對DES提出的差分攻擊，1993年Matsui針對DES提出的線性攻擊，計算活性S盒個數(shù)的下界是另外一種評估分組密碼抵抗差分和線性分析的方法，此外還有不可能差分分析、零相關(guān)線性分析、積分攻擊、中間相遇攻擊、插值攻擊、相關(guān)密鑰攻擊、循環(huán)移位攻擊和不變量攻擊等多種攻擊方法。

2019年2月中國密碼學會啟動了分組密碼算法設(shè)計競賽活動(http://www.icaisconf.com/)。基于混沌的雙模塊Feistel結(jié)構(gòu)高安全性高速(high security and high speed block cipher algorithm of twomodule FEistel structure based on Chaos,CFE)分組密碼算法是參加競賽的29個分組密碼算法之一。該分組密碼算法的明文分組支持128位和256位兩種模式，加密輪數(shù)為5輪。算法使用密鑰生成非線性組件S盒，利用明文參與非線性部件的選擇，線性變換選用滾動正向加和逆向加策略實現(xiàn)信息擴散。算法設(shè)計中先隨機選取種子密鑰，將其通過混沌迭代系統(tǒng)生成序列，再利用序列構(gòu)造密碼算法的非線性S盒，此設(shè)計使得分析者進行密碼攻擊時，不能將編碼環(huán)節(jié)作為已知因素來構(gòu)造基于已知S盒的差分和線性分析；非線性S盒受1 bit輪輸入因素控制，動態(tài)可變，使得分析者不能基于傳統(tǒng)的固定編碼環(huán)節(jié)分析方法進行密碼攻擊。

本文結(jié)構(gòu)如下，第2節(jié)對密碼算法進行描述，第3節(jié)討論密碼結(jié)構(gòu)和部件的安全性，第4節(jié)對密碼算法安全性進行分析，第5節(jié)總結(jié)全文。

2 CFE分組密碼算法概述

圖1 結(jié)構(gòu)圖

(d)S盒選擇與替換：若v=0選擇S1，否則選擇S2；根據(jù)得到的S盒，將CR0(i)(i=0,1,···,7)進行S盒查表替換，即完成函數(shù)F的處理過程。

(5)解密過程：由于本方案的結(jié)構(gòu)嚴格對稱，因此解密過程需將密鑰順序進行調(diào)整，并使用逆向Feistel網(wǎng)絡(luò)完成解密。

3 密碼結(jié)構(gòu)和密碼部件安全性分析

(1)密碼結(jié)構(gòu)安全性。該密碼算法總體結(jié)構(gòu)為Feistel結(jié)構(gòu)，迭代5輪，但輪函數(shù)動態(tài)可變。

(2)密碼部件性質(zhì)分析。S盒：S盒是基于混沌系統(tǒng)構(gòu)造的，且隨著種子密鑰的不同而不同，并且S盒不公開，這是依賴于密鑰的S盒的一個很大的優(yōu)點，所以事先分析S盒以尋找弱點加以攻擊是不可能的。

本部分針對隨機選取的一個S盒，其參數(shù)為

科創(chuàng)板“選秀”閃爍“行政化政績幻覺”，也容易誘導企業(yè)的依賴思想。企業(yè)是市場的主體，是否上市，純粹是企業(yè)的一種市場行為，應(yīng)由企業(yè)自己決定。現(xiàn)在的情況是，一些地方政府主動充當“媒婆”的角度，出臺各種優(yōu)惠政策鼓勵一些高新企業(yè)去科創(chuàng)板上市，行政化“動員”手段過于張揚，滋長了企業(yè)抱“奶瓶”的想法，在某種程度上侵害了企業(yè)的自主權(quán)，也不利于企業(yè)提升自力更生闖市場的能力。須知科創(chuàng)板也不是隨便閑逛的集市，那些科技含量高、市場潛力大、規(guī)范性強、具有一定產(chǎn)業(yè)規(guī)模的企業(yè)才能捷足先登，而不是一味仰仗政府的行政支持。

經(jīng)分析，其滿足雙射性和嚴格雪崩準則[2]。但是因為S盒由混沌系統(tǒng)構(gòu)造，所以其具體密碼學性質(zhì)[3]，如差分均勻度和線性度并不明確。

P置換：P置換為一個線性變換，起到信息擴散作用。算法的線性變換由正向擴散和逆向擴散兩部分組成，具體擴散過程見式(6)和式(7)。針對擴散過程可得明文線性變換T和密鑰線性變換W分別為

圖2 輪函數(shù)

4 密碼算法安全性分析

這里只對128 bit的CFE算法詳細敘述其分析過程并給出結(jié)果，而256 bit的算法有類似的分析過程與結(jié)果。

4.1 差分攻擊

評估一個分組密碼算法抗差分攻擊能力的常用方法是估計其差分活性S盒個數(shù)的下界[4]。差分活性S盒個數(shù)越多，對應(yīng)的差分特征概率越小。因此，差分活性S盒個數(shù)的下界體現(xiàn)了差分特征概率的上界，若差分特征概率的上界小于某個標準，則該算法具有抵抗差分攻擊的能力。

性質(zhì)1 CFE分組算法的差分活性S盒個數(shù)下界見表1。

表1 差分活性S盒個數(shù)下界

證明 以1 2 8 b i t 為例取5 輪差分特征(0000α000,00000000)→(00000β0β,0000α0γ0)，記?CRi,?Y i,i=1,2,···,5為S盒的輸入輸出差分，且每輪取特征碼相同的概率為2–1。

第1 輪：活 性S 盒 為0 個，其 中?CR1=0,?Y1=0,?R1=?L0⊕?Y1=?L0,?L1=?R0。

第2輪：活性S盒為2個，其中?CR2=(0,0,0,0,0,α,0,α),?Y2=(0,0,0,0,0,?Y2(5),0,?Y2(7)),?R2=?L1⊕?Y2=?Y2,?L2=?R1。

第3 輪：活 性S 盒 為1 個，其 中?Y2(5)=?Y2(7)的概率為2–8,?CR3=(0,0,0,0,0,0,?Y2(7),0) ,?Y3=(0,0,0,0,0,0,?Y3(6),0),?R3=?L2⊕?Y3=(0,0,0,0,α,0,?Y3(6),0),?L3=?R2。

第4輪：活性S盒為2個，其中α取 定，?Y3(6)有2 5 4 種取法，則α=?Y3(6)的概率為2 5 4/255=2–0.0050，且?CR4=(0,0,0,0,0,α ⊕?Y3(6),0,?Y3(6)) ,?Y4=(0,0,0,0,0,?Y4(5),0,?Y4(7)),?L4=?R3,?R4=?L3⊕?Y4=(0,0,0,0,0,?Y2(5)⊕?Y4(5),0,?Y2(7)⊕?Y4(7))。

第5輪：活性S盒為1個。由于使用的S盒是雙射，且兩個S盒輸入的字節(jié)有1bit不同，則輸出不同。因為數(shù)字化的混沌序列輸出的是均勻分布的偽隨 機 數(shù)，其 值 為1,2,···,255，那 么?Y2(5)=?Y2(7)=0完 全相同的概率為1/255=2?7.9943。故?Y2(5)⊕?Y4(5)=?Y2(7)⊕?Y4(7)的概率為2–7.9943，則有? CR5=(0,0,0,0,0,0,?Y2(7)⊕?Y4(7),0)。

需要說明的是，方案的提交者給出的活性S盒的下界個數(shù)為14，應(yīng)該有誤。

4.2 不可能差分攻擊

在不可能差分分析[5,6]中，攻擊者利用不可能出現(xiàn)的輸入輸出差分模式排除錯誤密鑰，從而縮小密鑰的搜索空間。為此，本文構(gòu)造5輪不可能差分特征如下。

第3輪輸入的右半部分為β；

圖3 5輪不可能差分特征圖

4.3 零相關(guān)線性分析

零相關(guān)線性分析[7,8]利用相關(guān)度為零的線性逼近來區(qū)分分組密碼算法與隨機置換。基于相關(guān)度為零的線性逼近表達式進行密鑰恢復(fù)。

4.4 積分攻擊

圖4 5輪零相關(guān)線性區(qū)分器

因此，利用上述3輪積分區(qū)分器對5輪算法實施攻擊時，需猜測L 3和SK 4兩個值。若式(16)成立，則L 3和SK4為正確猜測值。

但是S盒由混沌系統(tǒng)生成，屬于不確定元素，所以對CFE分組密碼算法做積分攻擊較困難。

4.5 中間相遇攻擊

構(gòu)造中間相遇區(qū)分器[11,12]的基本思想是給定一組滿足一定條件的明文集(δ-集)作為輸入，考察明文集經(jīng)密碼函數(shù)(隨機置換)加密后，按明文集次序截取對應(yīng)輸出密文集固定位置的取值構(gòu)成一個有序序列，根據(jù)該序列可取值范圍隨密碼函數(shù)和隨機置換的不同，將密碼函數(shù)與隨機置換區(qū)分。

圖5 積分攻擊

4.6 其他攻擊

插值攻擊：插值攻擊[13]實質(zhì)上是一種代數(shù)方法，其基本思想是將密文看作明文的多項式函數(shù)，然后通過研究多項式性質(zhì)來分析一個加密算法所具有的密碼學性質(zhì)。插值攻擊一般對那些輪函數(shù)次數(shù)比較低且具有比較緊湊的表達式的密碼算法有效。因為CFE算法輪函數(shù)的S盒性質(zhì)不確定，故明文和密文之間的多項式函數(shù)的次數(shù)不確定，所以用插值攻擊分析比較困難。

圖6 5輪中間相遇區(qū)分器

相關(guān)密鑰攻擊：在相關(guān)密鑰[14]模型下，攻擊者能夠通過某種方式獲得明文及其在某些未知密鑰下所對應(yīng)的密文。攻擊者雖不知道這些密鑰的具體值，但知道甚至可以選取這些密鑰之間的關(guān)系。由于在CFE密鑰擴展算法中，每輪的輪子密鑰由混沌序列生成，排列方式與取值都不同且無法確定，所以兩個輪子密鑰之間沒有關(guān)系，故無法確定或選取這些密鑰之間的關(guān)系，該算法可以抗擊相關(guān)密鑰攻擊。

5 類似結(jié)構(gòu)的混沌密碼分析對比

在2016年，文獻[16]對Fridrich的混沌圖像加密方案進行了密碼分析。對于密碼算法設(shè)計，CFE算法基于時空混沌系統(tǒng)式(1)構(gòu)造密鑰和非線性部件S盒，然后使用了5輪Feistel結(jié)構(gòu)。與之相似，F(xiàn)ridrich的方 案 是 基 于混 沌方 程g(x)=(β+1)(1+1/β)β x(1?x)β,β∈[1,4]設(shè)計的，然后迭代幾輪位置置換和值替換(使用了非線性函數(shù)g)。不同的是，F(xiàn)ridrich方案的非線性部件使用的是模加，而CFE算法則使用了S盒。在密碼分析方面，文獻[16]討論了Fridrich方案的一些數(shù)學性質(zhì)，并給出了Solak選擇密文攻擊方法的實際缺陷和應(yīng)用，而本文主要討論了CFE算法的密碼部件的性質(zhì)，然后進行了一系列傳統(tǒng)的密碼分析。

6 結(jié)束語

本文對CFE分組算法的安全性進行了分析，結(jié)果顯示，因為算法具有動態(tài)S盒特性，而積分攻擊、插值攻擊、循環(huán)移位攻擊、中間相遇攻擊和不變量攻擊對S盒的密碼學特性有較強的依賴性，所以該算法不適合用這些攻擊方法，并且由密鑰擴展方案可得該算法可以抵抗相關(guān)密鑰攻擊；其次本文構(gòu)造出了5輪不可能差分特征鏈，并利用其進行區(qū)分攻擊；更進一步地，求得算法的活性S盒下界為6，概率約為2–21；最后指出了算法存在5輪零相關(guān)線性特征。接下來我們的工作將著重對該算法的S盒進行研究。