孫曉玲，李姍姍，楊光，楊秋格

（防災(zāi)科技學(xué)院信息工程學(xué)院，河北三河 065201）

0 引言

Feistel 密碼結(jié)構(gòu)是一種高效的對稱結(jié)構(gòu)，被廣泛應(yīng)用于分組密碼算法的設(shè)計，對該結(jié)構(gòu)的攻擊方法也被廣泛研究，差分分析是最經(jīng)典的一種。差分分析是一種選擇明文攻擊，通過分析特定明文差分對相應(yīng)密文差分的影響來獲得最大可能的密鑰。通過算法分析最終獲取密鑰的方法也稱為密鑰恢復(fù)攻擊。

Blow-CAST-Fish 算法［1］是一種Feistel 結(jié)構(gòu)的對稱加密算法，結(jié)合了Blowfish［2］和CAST-128（C.Adams S.Tavares-128）［3］兩種算法的優(yōu)點，算法實現(xiàn)簡單快速，且安全性更強(qiáng)。使用了基于密鑰的S 盒、基于輪數(shù)的輪函數(shù)和基于子密鑰的循環(huán)移位操作，使算法具有強(qiáng)大的抗線性分析和差分分析的能力。S 盒由密鑰產(chǎn)生，使得算法分析更加困難，目前對該類算法的分析方法較少。研究針對該算法的攻擊方法，可對算法安全性進(jìn)行分析并實現(xiàn)密鑰恢復(fù)過程，有助于精研對此類Feistel 結(jié)構(gòu)密碼算法的攻擊方法，具有一定的理論意義和應(yīng)用價值。文獻(xiàn)［4］中分別根據(jù)單個活性S 盒和兩個活性S盒的差分特征給出了Blowfish 算法的密鑰恢復(fù)攻擊；文獻(xiàn)［5］中根據(jù)輪函數(shù)f1和f3的差分特性，構(gòu)造了CAST-128 的6輪差分特征，并給出了8 輪算法的差分攻擊方法；文獻(xiàn)［6］中根據(jù)兩個活性S 盒的差分特征，構(gòu)造了Blow-CAST-Fish 算法的6 輪差分特征，并對8 輪算法進(jìn)行了攻擊；文獻(xiàn)［7］中根據(jù)單個活性S 盒的差分特征，構(gòu)造了Blow-CAST-Fish 算法的14輪差分特征，并對16 輪算法進(jìn)行了攻擊；文獻(xiàn)［8］中提出了一種利用差分表對CAST-128 進(jìn)行攻擊的方法，該方法通過事先計算輪函數(shù)的差分表，根據(jù)算法輸出與輪函數(shù)輸入差分和輸出差分的關(guān)系，計算輪密鑰的值，該方法大幅降低了攻擊的時間復(fù)雜度；文獻(xiàn)［9］中基于32 輪差分特征對36 輪CAST-256 算法進(jìn)行了差分攻擊；文獻(xiàn)［10］中利用積分區(qū)分器對29 輪CAST-256 算法進(jìn)行了密鑰恢復(fù)攻擊；文獻(xiàn)［11］中利用積分分析與零相關(guān)分析兩種方法之間的聯(lián)系，實現(xiàn)了28 輪CAST-256 算法的積分分析；文獻(xiàn)［12］中對Type-1 廣義Feistel 結(jié)構(gòu)進(jìn)行研究，給出了改進(jìn)的多項式時間量子區(qū)分器，給出了19 輪CAST-256 的量子密鑰恢復(fù)攻擊。

除了經(jīng)典的差分分析和線性分析，近幾年出現(xiàn)了很多新的密碼分析方法。文獻(xiàn)［13］中提出了一種新的統(tǒng)計積分區(qū)分器，成功地攻擊了Skipjack-BABABABA（B：Rule B，A：Rule A）的全輪密碼；文獻(xiàn)［14］中通過構(gòu)建相關(guān)密鑰不可能差分區(qū)分器對Deoxys 算法進(jìn)行攻擊；文獻(xiàn)［15］中給出了一種在單一密鑰模式下構(gòu)建調(diào)柄密鑰差分區(qū)分器方法對CRAFT（with effiCient pRotection Against differential Fault analysis aTtacks）算法進(jìn)行密鑰恢復(fù)攻擊的方法。近幾年，量子計算環(huán)境下的對稱密碼安全性研究成為熱點，出現(xiàn)了一些針對Feistel 結(jié)構(gòu)的分析成果：文獻(xiàn)［16］中構(gòu)造了一個針對4 輪Feistel 結(jié)構(gòu)的量子區(qū)分器；文獻(xiàn)［17］和文獻(xiàn)［18］中對Feistel 結(jié)構(gòu)構(gòu)造了一些量子密鑰恢復(fù)攻擊；文獻(xiàn)［19］中給出了廣義Feistel 結(jié)構(gòu)的量子區(qū)分器和密鑰恢復(fù)攻擊方法。

針對Blow-CAST-Fish 的攻擊，文獻(xiàn)［6-7］中采用傳統(tǒng)的差分攻擊，在構(gòu)造的n輪差分特征基礎(chǔ)上，最多只能擴(kuò)充2 輪進(jìn)行密鑰恢復(fù)攻擊，且時間復(fù)雜度和數(shù)據(jù)復(fù)雜度較高。本文利用文獻(xiàn)［8］中查找差分表的方法，對Blow-CAST-Fish 的差分攻擊進(jìn)行了改進(jìn)。該攻擊在構(gòu)造的n輪差分特征基礎(chǔ)上，可繼續(xù)擴(kuò)充3 輪實現(xiàn)密鑰恢復(fù)，與傳統(tǒng)攻擊相比，在相同差分特征下，增加了攻擊輪數(shù)，且時間復(fù)雜度和數(shù)據(jù)復(fù)雜度大幅減少，提高了攻擊的效率。

文獻(xiàn)［6］中，構(gòu)造6 輪差分特征，實現(xiàn)了8 輪算法的攻擊，差分特征概率為2-61，弱密鑰比例為2-12，時間復(fù)雜度為2107.9次8 輪加密，數(shù)據(jù)復(fù)雜度為264個選擇明文。本文基于此6 輪差分特征，繼續(xù)擴(kuò)充3 輪，實現(xiàn)了9 輪Blow-CAST-Fish 的差分攻擊，增加了1 輪攻擊輪數(shù)，差分特征概率為2-61，弱密鑰比例為2-12，時間復(fù)雜度降為274次9 輪加密，數(shù)據(jù)復(fù)雜度為264個選擇明文。

文獻(xiàn)［7］中，構(gòu)造14 輪差分特征，實現(xiàn)了16 輪算法的攻擊，差分特征概率為2-49，弱密鑰比例為2-52.4，時間復(fù)雜度為260次16 輪加密，數(shù)據(jù)復(fù)雜度為254個選擇明文。本文基于文獻(xiàn)［7］中的2 輪差分特征，構(gòu)造12 輪差分特征，在此基礎(chǔ)上擴(kuò)充3 輪，實現(xiàn)了15 輪Blow-CAST-Fish 的密鑰恢復(fù)攻擊，攻擊輪數(shù)減少1 輪，差分特征概率提高至2-42，弱密鑰比例增加至2-42，時間復(fù)雜度為266.1次15 輪加密，數(shù)據(jù)復(fù)雜度降為247個選擇明文。

兩種情況下，新的攻擊與已有攻擊相比，攻擊效率明顯提高。將本文中所使用的基于“查詢差分表”的攻擊與傳統(tǒng)差分攻擊對CAST 類算法的攻擊結(jié)果做比較，如表1 所示。

表1 CAST類算法攻擊方案對比Tab.1 Comparison of attack schemes for CAST algorithms

1 背景知識

1.1 Blow-CAST-Fish算法

Blow-CAST-Fish 算法是一種Feistel 結(jié)構(gòu)的分組加密算法，輸入64 bit 明文，經(jīng)過16 輪迭代運算，輸出64 bit 密文。初始密鑰長度可變，范圍為32～448 bit，由初始密鑰通過密鑰擴(kuò)展算法生成18 個32 bit 的子密鑰P1，P2，…，P18（稱為P 盒）和4 個8 × 32 的S 盒S1、S2、S3、S4，S 盒的輸入為8 bit，輸出為32 bit，S 盒運算為查表運算。每輪運算包括P 盒的異或運算和輪函數(shù)f運算，輪函數(shù)f的核心為S 盒。算法分析過程與密鑰擴(kuò)展算法無關(guān)，故此處不對密鑰擴(kuò)展做詳細(xì)介紹。

算法加密過程為：將64 bit 明文分為左、右兩部分，記為（L0，R0），根據(jù)如下規(guī)則計算(Li，Ri)(1 ≤i≤16)：

設(shè)密文C=(CL，CR)，CL=R16⊕P18，CR=L16⊕P17。

函數(shù)f與輪數(shù)有關(guān)，第1、4、7、10、13、16 輪為f1，第2、5、8、11、14 輪為f2，第3、6、9、12、15 輪為f3。f1、f2和f3描述如下：

其中：“＜＜＜”表示循環(huán)左移操作，“⊕”表示異或運算，“-”表示模232減法運算，“+”表示模232加法運算，“‖”為連接符，F(xiàn)為f的部分操作。I為32 bit 數(shù)據(jù)，由高位到低位分成4 個字節(jié)，分別為Ia、Ib、Ic、Id。Si［It］表示對S 盒Si進(jìn)行查表運算，輸入為It，輸出為Si［It］。

算法加密流程如圖1 所示。

圖1 Blow-CAST-Fish算法的加密流程Fig.1 Encryption flow of Blow-CAST-Fish algorithm

1.2 差分分析

以下知識介紹中的S 盒和差分特征以Blow-CAST-Fish算法為例。S 盒的輸入為8 bit，輸出為32 bit。

S 盒的碰撞性 若S 盒存在一對輸入，其差分值等于γ（γ是一個字節(jié)，γ≠0），經(jīng)過S 盒變換后，輸出差分值為0000（0000 是4 個字節(jié)），則稱S 盒存在碰撞γ→0000。存在碰撞的S 盒稱為活性S 盒。

S 盒的碰撞概率 若S 盒共有M對不相等的輸入，其中m對滿足輸入差分為γ、輸出差分為0000，則S 盒存在碰撞γ→0000 的概率為m/M。

單輪差分特征及特征概率 首先將S 盒的碰撞性擴(kuò)展到整個F函數(shù)，假設(shè)只有S1存在碰撞γ→0000，概率為p，可構(gòu)造F函數(shù)的輸入差分為γ000、輸出差分為0000 的差分特征，概率為p。繼而擴(kuò)展到整輪，可構(gòu)造輸入差分為γ000＞＞＞Kri（Kri為本輪循環(huán)左移密鑰）、輸出差分為0000 的差分特征，概率為p。此時單輪差分特征概率只與輸入、輸出差分有關(guān)，概率為活性S 盒的碰撞概率。

n輪差分特征 選取合適的輸入差分，可以在單輪差分特征的基礎(chǔ)上擴(kuò)展到n輪差分特征。選取明文輸入差分為0000‖（γ000 ＞＞＞Kr2）。第1 輪左半部分輸入差分為0000、輸出差分一定為0000，概率為1；第2 輪左半部分輸入差分為γ000 ＞＞＞Kr2，經(jīng)過密鑰加密和左移，F(xiàn)函數(shù)的輸入差分為γ000，輸出差分為0000，概率為p；第3 輪與第1 輪相同；第4輪左半部分輸入差分為γ000 ＞＞＞Kr2，經(jīng)過密鑰加密和左移，F(xiàn)函數(shù)的輸入差分為（γ000 ＞＞＞Kr2）＜＜＜Kr4，差分特征（γ000 ＞＞＞Kr2）＜＜＜Kr4→0000 是否存在與Kr2、Kr4有關(guān)，特征概率與活性S 盒的碰撞概率相同，只與活性S 盒的輸入、輸出差分有關(guān)。后續(xù)輪數(shù)與前面類似。

n輪差分特征概率 等于每輪特征概率的乘積。

弱密鑰 使得碰撞存在，即使得上述構(gòu)造的差分特征存在的密鑰稱為弱密鑰。弱密鑰存在，則差分特征可構(gòu)造。

正確對 對于由n輪差分特征擴(kuò)展而來的攻擊過程，隨機(jī)選擇明文，滿足給定輸入差分和對應(yīng)輸出差分的明文對，稱為正確對。假設(shè)n輪差分特征概率為2v，攻擊選取的明文對數(shù)量為2w，則正確對的個數(shù)為2v× 2w。由正確對分析出來的密鑰即為正確密鑰。對于輸入明文長度為64 bit 的Blow-CAST-Fish 算法，可選明文對最多有263對，故可用于攻擊的差分特征概率不能低于2-63。

1.3 攻擊效率

評價攻擊效率，主要從攻擊輪數(shù)、弱密鑰比例、代價這3個方面綜合分析。對于Blow-CAST-Fish 算法，首先考慮兩個S 盒的碰撞性，兩個S 盒的輸入、輸出是16 bit 到32 bit 的映射，碰撞概率較高，故弱密鑰比例很高，但差分特征概率較低，最多可構(gòu)造特征概率為2-61的6 輪差分特征，因為如果輪數(shù)再多，差分特征概率將低于2-63，在明文空間為264的情況下，將不存在正確對，攻擊無法實現(xiàn)，所以基于兩個S 盒的碰撞，最多構(gòu)造6 輪差分特征，用本文攻擊方法最多可實現(xiàn)9 輪攻擊，比已有攻擊多了1 輪，且降低了時間復(fù)雜度。為了增加攻擊輪數(shù)，考慮單個S 盒的碰撞性，單個S 盒是8 bit 到32 bit 的映射，碰撞概率較低，故弱密鑰比例很低，但差分特征概率較高，可構(gòu)造特征概率為2-49的14 輪差分特征，但本文攻擊方法可在已構(gòu)造差分特征的基礎(chǔ)上擴(kuò)充3 輪，而Blow-CAST-Fish 算法共有16 輪，所以本文選擇構(gòu)造特征概率為2-42的12 輪差分特征，在此基礎(chǔ)上可實現(xiàn)15 輪算法的攻擊，與已有攻擊相比，總攻擊輪數(shù)減少了1 輪，但同樣基于12輪差分特征，攻擊輪數(shù)還是增加了1 輪，攻擊的總代價相對有所降低。兩種情況相比，基于的活性S 盒個數(shù)不同，導(dǎo)致特征概率和弱密鑰比例不同，可攻擊輪數(shù)也不同。9 輪攻擊基于多個活性S 盒，特征概率低，可攻擊輪數(shù)有限，但弱密鑰比例很高；15 輪攻擊基于單個活性S 盒，特征概率高，可攻擊輪數(shù)多，但與9 輪攻擊相比，弱密鑰比例很低。兩種攻擊，各有優(yōu)缺點，具有不同的理論意義。

2 9輪Blow-CAST-Fish的密鑰恢復(fù)攻擊

2.1 6輪差分特征

假設(shè)F函數(shù)已知，即4 個S 盒的值已知。文獻(xiàn)［6］中給出了基于兩個S 盒的碰撞性構(gòu)造的Blow-CAST-Fish 的6 輪差分特征：

映射（Ia，Ib）→S1[Ia]-S2[Ib]是一個16 bit 到32 bit 的映射函數(shù)，以較高的概率存在碰撞，即存在輸入（Ia，Ib）、（Ia'，Ib'），使得(S1[Ia]-S2[Ib])⊕（S1[Ia']-S2[Ib']）=0。設(shè)δ=Ia⊕Ia'、μ=Ib⊕Ib'，假設(shè)S1-S2只存在一對輸入滿足輸入差分為δμ、輸出差分為0000（δμ為16 bit 數(shù)值、0000 為32 bit 數(shù)值），則該碰撞的概率為2-15?？蓸?gòu)造第2 輪中F函數(shù)的輸入差分為δ μ00、輸出差分為0000 的差分特征（δ μ00、0000 為32 bit 數(shù)據(jù)），進(jìn)而可構(gòu)造Blow-CAST-Fish 的2 輪差分特征，如下所示：

在此基礎(chǔ)上，可擴(kuò)展到整個6 輪差分特征為：

其中：＞＞＞為循環(huán)右移；‖連接左、右兩半部分差分值；Kr2為第2 輪循環(huán)左移密鑰，取值任意；p為當(dāng)前輪的差分特征概率。此6 輪差分特征概率為2-61、弱密鑰比例為2-12，如圖2所示。

圖2 6輪差分特征Fig.2 Six-round differential characteristics

弱密鑰比例測試方法參見文獻(xiàn)［6］，任選5 個隨機(jī)密鑰及其產(chǎn)生碰撞的一種情況作為示例，如表2 所示，表中初始密鑰為字符形式，S 盒的輸入、輸出均為十六進(jìn)制形式，用下標(biāo)x表示。

表2 S1 - S2碰撞情況示例Tab.2 Examples of S1 - S2 collision

2.2 9輪算法的密鑰恢復(fù)過程

為了提高攻擊效率，為f3預(yù)先計算一個差分表，即為所有輸入、輸出差分組合創(chuàng)建一個表，用于存儲具有相同輸入、輸出差分的輸入-輸出對，例如，設(shè)a、b為f3的2 個32 bit 輸入，輸入差分ΔIn=a⊕b，輸出差分ΔOut=f3(a)⊕f3(b)，則將（a，f3（a））存儲在表中ΔIn→ΔOut對應(yīng)的條目處。在F函數(shù)已知的情況下，考慮Kri共有25種取值，需計算32 個表，記作Tj(j=0，1，…，31)。由于f3的輸入、輸出均為32 bit，所以共有264種輸入、輸出差分組合和232× 232種輸入-輸出對，故對于固定的輸入、輸出差分組合，平均可以找到一個對應(yīng)的輸入-輸出對。

下面利用差分表實現(xiàn)9 輪算法攻擊。首先在6 輪差分特征的基礎(chǔ)上，將算法輪數(shù)擴(kuò)充到9 輪，如圖3 所示，設(shè)第i輪的輸入為(Li-1，Ri-1)，輸出（Li，Ri）為下一輪的輸入，第9 輪中，輪函數(shù)f3的輸入記為X9，輸出記為Y9，對明文進(jìn)行9 輪加密后的密文記為（CL，CR），“？？？？”表示數(shù)值不確定。

圖3 9輪Blow-CAST-Fish算法的差分攻擊過程Fig.3 Flow of differential attack of 9-round Blow-CAST-Fish algorithm

具體攻擊過程如下：

1）循環(huán)Kr2的25個值。數(shù)據(jù)采集階段，選取232個結(jié)構(gòu)，每個結(jié)構(gòu)包含232個具有相同左半部分的明文。為滿足明文差分為0000‖（δμ00 ＞＞＞Kr2），每個結(jié)構(gòu)可產(chǎn)生231個明文對，一共可得263個明文對，對這些明文進(jìn)行9 輪加密，可得263個密文對。

2）循環(huán)Kr9的25個值，設(shè)置計數(shù)器數(shù)組V［232］并將其初始化為零。

3）循環(huán)263個密文對，可以計算第9 輪中輪函數(shù)f3的輸入異或差分和輸出異或差分：

查找對應(yīng)的差分表T，得到（X9，Y9）和（X9'，Y9'），計算P11=CL⊕X9。將計數(shù)器V［P11］加1。

4）將數(shù)值最大的計數(shù)器所對應(yīng)的（Kr2，Kr9，P11）的值保存下來，這些值即為正確密鑰。

將整個密鑰恢復(fù)過程更加簡潔地進(jìn)行歸納，如算法1所示。

算法1 9 輪Blow-CAST-Fish 算法的密鑰恢復(fù)過程。

2.3 復(fù)雜度分析

首先計算此次差分分析的信噪比，信噪比的計算公式為：

其中：p為差分特征概率，k為所恢復(fù)密鑰的比特數(shù)，α為分析每對消息時的密鑰計數(shù)，β為分析的消息對占總消息對的比例。本次攻擊中，p=2-61，所恢復(fù)密鑰為Kr2、Kr9、P11，總長度為42 bit，所以k=42，分析每對消息時，Kr2、Kr9取值是遍歷的，故α=210，因為用于分析的消息對要滿足異或值為0000‖（δ μ00 ＞＞＞Kr2），故β=2-32。

攻擊成功的概率由如下公式計算：

k=42，τ是正確對的個數(shù)，本文攻擊中，τ=232×231×2-61=22，故Ps=0.999，攻擊成功的概率接近于1。

數(shù)據(jù)復(fù)雜度 攻擊過程中，選擇了232× 232個明文，故數(shù)據(jù)復(fù)雜度為264個選擇明文。

時間復(fù)雜度 首先，預(yù)生成了32 個差分表，每個表的生成過程中，需遍歷所有輸入-輸出對，時間復(fù)雜度為32 ×232× 232× 2=270次一輪加密，等于270/9 ≈266.9次9 輪加密；其次，密鑰恢復(fù)過程中，為每個Kr2的取值選取263對異或值等于0000‖（δμ00 ＞＞＞Kr2）的明文對，其時間復(fù)雜度為25×263× 2=269次9 輪加密，第9 輪密鑰恢復(fù)過程中，用到了25×25× 263× 2=274次查表，假設(shè)一次查表操作等價于一次9 輪加密，則密鑰恢復(fù)的時間復(fù)雜度為274次9 輪加密。故總的時間復(fù)雜度為266.9+268+274≈274次9 輪加密。

空間復(fù)雜度 差分表所占存儲空間總共為32 × 264×8=272字節(jié)，密鑰恢復(fù)過程的空間復(fù)雜度為計數(shù)器和密鑰所占空間，約為232字節(jié)，總的存儲空間為272+232≈272字節(jié)。

構(gòu)造差分特征的時間和空間復(fù)雜度 構(gòu)造差分特征即測試是否存在弱密鑰使S 盒具有碰撞性，碰撞發(fā)生在第2、4、6 輪，每輪測試隨機(jī)選取210個初始密鑰。第2 輪有兩個活性S 盒，總共進(jìn)行210× 28× 28× 28× 28=242次S 盒查表運算，一次9 輪加密總共有4 × 9=36 ≈25次S 盒運算（其他異或運算耗時忽略不計），則總的時間復(fù)雜度約為237次9 輪加密。第4 輪和第6 輪，活性S 盒不固定，但無論密鑰取何值，一定有一個S 盒是非活性的，所以要測試3 個S 盒的碰撞，因為輸入差分固定且與循環(huán)密鑰Kri有關(guān)，則總共進(jìn)行210× 232×25× 6 ≈250次S 盒查表運算，相當(dāng)于245次9 輪加密。3 輪總的時間復(fù)雜度為237+245+245≈246次9 輪加密?？臻g復(fù)雜度為4 個S 盒的存儲空間和一個密鑰（32～442 bit）的存儲空間，總共為4 × 28× 4+112 ≈212字節(jié)。

3 15輪Blow-CAST-Fish的密鑰恢復(fù)攻擊

3.1 12輪差分特征

文獻(xiàn)［7］中，在假設(shè)F函數(shù)已知的情況下，為提高差分特征的概率，以增加攻擊輪數(shù)，只考慮單個活性S 盒的情況。以S1為研究對象，考慮映射Ia→S1［Ia］（Ia為8 bit），假設(shè)S1存在碰撞，即存在兩個不同的字節(jié)Ia和Ia'，使得S1[Ia]=S1[Ia']。假設(shè)滿足碰撞的輸入只有一對，則碰撞概率為2-7。設(shè)δ=Ia⊕Ia'，Kr2為第2 輪的循環(huán)左移密鑰，取0～31 的任意值，構(gòu)造了如下所示的2 輪差分特征，其中“0000”，“δ000 ＞＞＞kr2”分別表示明文左右兩半部分的32 位異或差分值，＞＞＞表示循環(huán)右移，p為當(dāng)前輪的差分特征概率。

假設(shè)Kr4=Kr6=Kr8=Kr10=Kr12=Kr2，將上述2 輪差分特征重復(fù)6 次，可構(gòu)造12 輪差分特征，如圖4 所示。前12 輪差分特征概率為2-42，弱密鑰比例為2-42。

圖4 十二輪差分特征Fig.4 Twelve-round differential characteristics

弱密鑰比例測試方法參見文獻(xiàn)［7］，表3 為一輪測試10萬個隨機(jī)初始密鑰中弱密鑰及使S1產(chǎn)生碰撞的情況，表中初始密鑰為字符形式，S 盒的輸入、輸出均為十六進(jìn)制形式，用下標(biāo)x表示。

表3 S1碰撞情況示例Tab.3 Examples of S1 collision

3.2 15輪算法的密鑰恢復(fù)過程

用前面所述同樣的方法為f3建立差分表，下面利用差分表實現(xiàn)15 輪算法的密鑰恢復(fù)攻擊。

首先在12 輪差分特征的基礎(chǔ)上，將算法輪數(shù)擴(kuò)充到15輪，如圖5 所示，設(shè)第i輪的輸入為(Li-1，Ri-1)，輸出（Li，Ri）為下一輪的輸入，第15 輪中，輪函數(shù)f3的輸入記為X15，輸出記為Y15，對明文進(jìn)行15 輪加密后的密文記為（CL，CR），“？？？？”表示數(shù)值不確定。

圖5 15輪Blow-CAST-Fish算法的差分攻擊過程Fig.5 Flow of differential attack of 15-round Blow-CAST-Fish algorithm

具體攻擊過程如下：

1）循環(huán)Kr2的25個值。數(shù)據(jù)采集階段，選取215個結(jié)構(gòu)，每個結(jié)構(gòu)包含232個具有相同左半部分的明文。為滿足明文差分為0000‖（δ000 ＞＞＞Kr2），每個結(jié)構(gòu)可產(chǎn)生231個明文對，一共可得246個明文對，對這些明文進(jìn)行15 輪加密，可得246個密文對。

2）循環(huán)Kr15的25個值，設(shè)置計數(shù)器數(shù)組V［232］并初始化為零。

3）循環(huán)246個密文對，可以計算第15 輪中輪函數(shù)f3的輸入異或差分和輸出異或差分：

查找對應(yīng)的差分表T，得到（X15，Y15）和（X15'，Y15'），計算P17=CL⊕X15。將計數(shù)器V［P17］加1。

4）將數(shù)值最大的計數(shù)器所對應(yīng)的（Kr2，Kr15，P17）的值保存下來，這些值即為正確密鑰。

將整個密鑰恢復(fù)過程進(jìn)行歸納，如算法2 所示。

算法2 15 輪Blow-CAST-Fish 的密鑰恢復(fù)過程。

3.3 復(fù)雜度分析

首先計算此次差分分析的信噪比。本次攻擊中，p=2-42，所恢復(fù)密鑰為Kr2、Kr15、P17，總長度為42 bit，所以k=42，分析每對消息時，Kr2，Kr15取值是遍歷的，故α=210，因為用于分析的消息對要滿足異或值為0000‖（δ000＞＞＞Kr2），故β=2-32。

攻擊成功的概率由如下公式計算：

k=42，τ是正確對的個數(shù)，本文攻擊中，τ=215×231×2-42=24，故Ps=0.999，攻擊成功的概率接近于1。

數(shù)據(jù)復(fù)雜度 攻擊過程中，選擇了232×215個明文，故數(shù)據(jù)復(fù)雜度為247個選擇明文。

時間復(fù)雜度 首先，預(yù)生成了32 個差分表，每個表的生成過程中，需遍歷所有輸入、輸出對，時間復(fù)雜度為32 ×232× 232× 2=270次一輪加密，等于270/15 ≈266.1次15 輪加密。其次，密鑰恢復(fù)過程中，為每個Kr2的取值選取246對異或值等于0000‖（δ000 ＞＞＞Kr2）的明文對，其時間復(fù)雜度為25× 246× 2=252次15 輪加密，第15 輪密鑰恢復(fù)過程中，用到了25× 25× 246× 2=257次查表，假設(shè)一次查表操作等價于一次15 輪加密，則密鑰恢復(fù)的時間復(fù)雜度為257次15 輪加密。故總的時間復(fù)雜度為266.1+252+257≈266.1次15 輪加密。

空間復(fù)雜度 差分表所占存儲空間總共為32 × 264×8=272字節(jié)，密鑰恢復(fù)過程的空間復(fù)雜度為計數(shù)器和密鑰所占空間，約為232字節(jié)，總的存儲空間為272+232=272字節(jié)。

構(gòu)造差分特征的時間和空間復(fù)雜度 碰撞發(fā)生在第2、4、6、8、10、12 輪，每輪只有S1是活性的，只需測試S1的碰撞性即可。測試的時候隨機(jī)選擇106個初始密鑰，總共進(jìn)行106× 28× 28≈235.9次S 盒查表運算，一次15 輪加密總共有4 × 15=60 ≈26次S 盒運算（其他運算時間可忽略不計），則總的時間復(fù)雜度為229.9次15 輪加密?？臻g復(fù)雜度為4 個S 盒的存儲空間和一個密鑰（32～442 bit）的存儲空間，總共為4 ×28× 4+112 ≈212字節(jié)。

4 結(jié)語

本文通過為輪函數(shù)f3構(gòu)建差分表，改進(jìn)了Blow-CASTFish 的差分攻擊，可在固定n輪差分特征的基礎(chǔ)上，擴(kuò)充3 輪進(jìn)行密鑰恢復(fù)攻擊，可以更高的效率實現(xiàn)密鑰恢復(fù)過程。首先，基于多個活性S 盒，構(gòu)造6 輪差分特征，實現(xiàn)了9 輪算法的密鑰恢復(fù)攻擊；其次，基于單個活性S盒，構(gòu)造12 輪差分特征，實現(xiàn)了15 輪密鑰恢復(fù)攻擊。兩種攻擊相比：9 輪攻擊輪數(shù)少，但弱密鑰比例很高，攻擊成功概率高；15 輪攻擊輪數(shù)較多，但弱密鑰比例很低，攻擊成功概率低。

分析結(jié)果表明，使差分特征成立的弱密鑰是以一定概率存在的，故差分特征可構(gòu)造，攻擊在弱密鑰下可成功；且構(gòu)造差分特征的時間和空間復(fù)雜度相比攻擊代價要小得多，不會影響攻擊效果。此攻擊方法為該類CAST 型Feistel 結(jié)構(gòu)分組密碼算法的最優(yōu)攻擊方案。