基于差分表的Blow-CAST-Fish算法的密鑰恢復(fù)攻擊

孫曉玲，李?yuàn)檴?，楊光，楊秋?/p>

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

0 引言

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

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

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

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

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

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

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

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

1 背景知識(shí)

1.1 Blow-CAST-Fish算法

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

算法加密過(guò)程為：將64 bit 明文分為左、右兩部分，記為（L0，R0），根據(jù)如下規(guī)則計(jì)算(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)左移操作，“⊕”表示異或運(yùn)算，“-”表示模232減法運(yùn)算，“+”表示模232加法運(yùn)算，“‖”為連接符，F(xiàn)為f的部分操作。I為32 bit 數(shù)據(jù)，由高位到低位分成4 個(gè)字節(jié)，分別為Ia、Ib、Ic、Id。Si［It］表示對(duì)S 盒Si進(jìn)行查表運(yùn)算，輸入為It，輸出為Si［It］。

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

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

1.2 差分分析

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

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

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

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

n輪差分特征 選取合適的輸入差分，可以在單輪差分特征的基礎(chǔ)上擴(kuò)展到n輪差分特征。選取明文輸入差分為0000‖（γ000 ＞＞＞Kr2）。第1 輪左半部分輸入差分為0000、輸出差分一定為0000，概率為1；第2 輪左半部分輸入差分為γ000 ＞＞＞Kr2，經(jīng)過(guò)密鑰加密和左移，F(xiàn)函數(shù)的輸入差分為γ000，輸出差分為0000，概率為p；第3 輪與第1 輪相同；第4輪左半部分輸入差分為γ000 ＞＞＞Kr2，經(jīng)過(guò)密鑰加密和左移，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)造。

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

1.3 攻擊效率

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

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

2.1 6輪差分特征

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

映射（Ia，Ib）→S1[Ia]-S2[Ib]是一個(gè)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只存在一對(duì)輸入滿足輸入差分為δμ、輸出差分為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ò)展到整個(gè)6 輪差分特征為：

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

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

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

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

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

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

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

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

具體攻擊過(guò)程如下：

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

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

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

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

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

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

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

2.3 復(fù)雜度分析

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

其中：p為差分特征概率，k為所恢復(fù)密鑰的比特?cái)?shù)，α為分析每對(duì)消息時(shí)的密鑰計(jì)數(shù)，β為分析的消息對(duì)占總消息對(duì)的比例。本次攻擊中，p=2-61，所恢復(fù)密鑰為Kr2、Kr9、P11，總長(zhǎng)度為42 bit，所以k=42，分析每對(duì)消息時(shí)，Kr2、Kr9取值是遍歷的，故α=210，因?yàn)橛糜诜治龅南?duì)要滿足異或值為0000‖（δ μ00 ＞＞＞Kr2），故β=2-32。

攻擊成功的概率由如下公式計(jì)算：

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

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

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

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

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

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

3.1 12輪差分特征

文獻(xiàn)［7］中，在假設(shè)F函數(shù)已知的情況下，為提高差分特征的概率，以增加攻擊輪數(shù)，只考慮單個(gè)活性S 盒的情況。以S1為研究對(duì)象，考慮映射Ia→S1［Ia］（Ia為8 bit），假設(shè)S1存在碰撞，即存在兩個(gè)不同的字節(jié)Ia和Ia'，使得S1[Ia]=S1[Ia']。假設(shè)滿足碰撞的輸入只有一對(duì)，則碰撞概率為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

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

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

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

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

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

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

具體攻擊過(guò)程如下：

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

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

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

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

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

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

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

3.3 復(fù)雜度分析

首先計(jì)算此次差分分析的信噪比。本次攻擊中，p=2-42，所恢復(fù)密鑰為Kr2、Kr15、P17，總長(zhǎng)度為42 bit，所以k=42，分析每對(duì)消息時(shí)，Kr2，Kr15取值是遍歷的，故α=210，因?yàn)橛糜诜治龅南?duì)要滿足異或值為0000‖（δ000＞＞＞Kr2），故β=2-32。

攻擊成功的概率由如下公式計(jì)算：

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

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

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

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

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

4 結(jié)語(yǔ)

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

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