ESF算法的截斷不可能差分分析*

李明明, 郭建勝, 崔競一, 徐林宏

信息工程大學(xué), 鄭州450001

1 引言

不可能差分分析, 由Knudsen[1]和Biham[2]兩人分別獨(dú)立提出, 是目前常用的密碼分析方法之一.其基本思想是排除那些導(dǎo)致概率為0 的區(qū)分器的猜測密鑰.對于一條概率為0 的差分路徑, 當(dāng)用正確密鑰解密密文對時, 不會得到符合該路徑的差分; 如果用猜測密鑰解密密文對, 得到符合該路徑的差分, 則該密鑰猜測值是錯誤的; 那么篩去所有的錯誤密鑰猜測值, 剩下的就是我們需要恢復(fù)的正確密鑰[3].對一個分組密碼算法進(jìn)行不可能差分分析的先決條件是找到一條概率為0 的差分路徑, 即不可能差分區(qū)分器.

Kim 等人[4]提出了μ方法, 該方法可以有效找出各種算法結(jié)構(gòu)中所固有的不可能差分形式, 這些固有的不可能差分只與算法的結(jié)構(gòu)有關(guān), 而與算法所采用的S盒無關(guān), 這也就是所謂的截斷不可能差分[5].后來 Luo 等[6]在μ方法基礎(chǔ)上改進(jìn)提出了 UID 方法.不同于μ方法, UID 方法利用中間相錯的思想將密碼算法結(jié)構(gòu)分解成兩部分進(jìn)行處理.此外, 孫兵等[7]基于整環(huán)上的矩陣論, 證明了 SPN 結(jié)構(gòu)及嵌套SPN 的Feistel 結(jié)構(gòu)的截斷不可能差分區(qū)分器的上界取決于線性層的本原指數(shù).

ESF 算法[8]是2013 年劉宣等人基于LBlock 算法[9]改進(jìn)的的輕量級分組密碼算法, 其置換層借鑒PRESENT 算法[10]中P置換的形式, 能夠使得在較少的輪數(shù)中快速擴(kuò)散, 從而達(dá)到增加密碼算法抵抗攻擊的安全性.該算法分組長度為 64-bit, 密鑰長度為 80-bit, 整體采用變形 Feistel 結(jié)構(gòu), 由非線性變換S盒、P置換、循環(huán)移位、異或四種運(yùn)算組成.

目前, 對于 ESF 算法有多個安全性分析結(jié)果.徐朋[11]給出了 ESF 算法的差分故障攻擊, 尹軍等人[12]給出了 ESF 算法的 13 輪相關(guān)密鑰差分分析.而ESF 算法的不可能差分分析結(jié)果相對較多, 最初劉宣等人[13]給出了 ESF 算法一條 8 輪不可能差分區(qū)分器, 并給出了 11 輪不可能差分分析, 之后陳玉磊等人[14]基于同一條 8 輪不可能差分區(qū)分器改進(jìn)了 ESF 算法的 11 輪不可能差分分析結(jié)果; 高紅杰等人[15]也基于同一條8 輪不可能差分區(qū)分器, 并根據(jù)密鑰之間的關(guān)系, 給出了ESF 算法的12 輪不可能差分分析.

本文首先給出了ESF 算法的一些新的8 輪截斷不可能差分區(qū)分器.其次, 基于得到的8 輪不可能差分區(qū)分器, 并利用密鑰編排算法部分子密鑰間存在的依賴關(guān)系, 給出了對ESF 算法的13 輪不可能差分分析, 恢復(fù)了 80 比特主密鑰, 時間復(fù)雜度為 277.39次 13 輪 ESF 算法加密, 數(shù)據(jù)復(fù)雜度為 261.99個選擇明文.

2 ESF 算法介紹

本節(jié)主要對文章里出現(xiàn)的符號進(jìn)行說明及介紹ESF 算法的基本知識.首先給出符號說明如下.

Li第i+1 輪輸入的左半分組

Ri第i+1 輪輸入的右半分組

?Li兩個輸入Li和的差分

?Ri兩個輸入Ri和的差分

<<<α循環(huán)左移α比特

Ki第i+1 輪子密鑰

Ki?jn第n+1 輪子密鑰的i到j(luò)比特

Li[j]表示Li的第j比特

?Li[j]表示 ?Li的第j比特

[i]2輪常數(shù)i的二進(jìn)制表示

?不確定的比特差分

∥二進(jìn)制字符連接

ESF 輕量分組密碼算法采用變形Feistel 結(jié)構(gòu), 其分組長度為64-bit, 密鑰長度為80-bit, 迭代輪數(shù)為32 輪.該算法加密流程如圖1 所示, 其中輪函數(shù)F由子密鑰異或、非線性變換S盒、P置換組成, 為典型 SPN 結(jié)構(gòu), 具體可表示為F(Ri,Ki)=PS(Ri⊕Ki).

ESF 算法中的非線性變換S盒、P置換及密鑰編排算法具體介紹如下.

非線性變換S 盒ESF 算法的非線性變換由8 個對合4 比特S盒組成,即S=(S1,S2,S3,S4,S5,S6,S7,S8), 其中Si:{0,1}4→ {0,1}4,i=1,2,··· ,8.

P 置換P置換將 32 比特的順序進(jìn)行重新排列.P: (b1,b2,··· ,b32) → (c1,c2,··· ,c32), 其中當(dāng)0 ≤i≤ 7 時, 有 (b4i+1,b4i+2,b4i+3,b4i+4) → (ci+1,ci+9,ci+17,ci+25).

圖1 ESF 系列算法輪函數(shù)Figure 1 Round function of ESF

密鑰編排算法ESF 算法主密鑰長度為 80 比特, 密鑰擴(kuò)展設(shè)計與 LBlock 算法類似.將主密鑰K=k79k78···k1k0存入密鑰寄存器, 每一輪取寄存器最左端32 比特作為子密鑰.對于0 ≤i≤31 , 擴(kuò)展算法可表述為

在得到第i輪子密鑰Ki?1后, 按如下步驟更新密鑰寄存器K

(1)K<<<13;

(2) [k79k78k77k76]←S0[k79k78k77k76], [k75k74k73k72]←S0[k75k74k73k72];

(3) [k47k46k45k44k43]←[k47k46k45k44k43]⊕[i]2;

(4) 取當(dāng)前密鑰寄存器K最左端32 比特作為子密鑰Ki.

3 ESF算法的8輪截斷不可能差分區(qū)分器

本節(jié)首先介紹 ESF 算法的相關(guān)性質(zhì), 其次根據(jù)這些性質(zhì)給出ESF 算法的一些新的 8 輪截斷不可能差分區(qū)分器.

性質(zhì) 1S盒的輸出差分不為零當(dāng)且僅當(dāng)其輸入差分不為零.

性質(zhì) 2對于ESF 算法任意不可能差分區(qū)分器, 如果比特矛盾出現(xiàn)在分組的左半部分, 則分組的右半部分也必存在矛盾, 反之亦然.

證明:不妨設(shè)加密方向差分路徑 (?Li,?Ri) → (?Li+s,?Ri+s) 以概率 1 成立, 解密方向差分路徑 (?Lj?t,?Rj?t)←(?Lj,?Rj) 也以概率 1 成立, 且則可知 (?Li,?Ri) ?(?Lj,?Rj) 是一條s+t輪不可能差分區(qū)分器.

由于 ESF 算法是變形 Feistel 結(jié)構(gòu),有Lk+1=Rk<<<7,故 ?Li+s= ?Ri+s?1<<<7,?Lj?t=?Rj?t?1<<<7 .從而當(dāng)且僅當(dāng)

根據(jù)性質(zhì)1 和性質(zhì)2, 發(fā)現(xiàn)了一些新的8 輪截斷不可能差分區(qū)分器, 如定理1 所示.

定理 1當(dāng)初始輸入狀態(tài)差分滿足 (?L1,?R1) = (a1a2a3a41a5a6a70000 0000 0000 0000 0000 0000, 0000 0000 0000 0000 0000 0000 0000 0000), 其中a1,a2,a3,a4,a5,a6,a7為任意值, 經(jīng) 8 輪ESF 算法加密后輸出狀態(tài)差分滿足 (?L9,?R9) = (0000 0000 0000 0000 0000 0000 0000 0000,0000 0000 0000 0000 0000 0000 0000 1000) 是不可能的.具體形式如圖2 所示, 其中bi/di/ei/fi/gi/hi,i∈ {1,2,3,···} 皆不全為 0.

圖2 ESF 算法的8 輪不可能差分區(qū)分器Figure 2 8-round impossible differential distinguisher of ESF

證明:當(dāng)初始輸入狀態(tài)差分滿足 (?L1,?R1) = (a1a2a3a41a5a6a70000 0000 0000 0000 0000 0000, 0000 00000000 0000 0000 0000 0000 0000) 時, 初始輸入狀態(tài) (L1,R1) 經(jīng) 3 輪 ESF 算法加密后輸出差分滿足 ?R4= (d1⊕a70d50d90d130d20d60d100d140d30d70d110d150d4a1d8⊕a2a3d12⊕a41d16⊕a5a6).由于故由性質(zhì) 1 可知s8(d12⊕a41d16⊕a5a6) = (e29e30e31e32)(0000).(L4,R4) 再經(jīng) 1 輪 ESF 算法加密后輸出差分滿足 ?R5(e1e5⊕b2e9⊕b6e13e17e21e25e29e2e6⊕b3e10⊕b7e14e18e22e26e30e3e7⊕b4e11⊕b8e15e19e23e27e31e4e8⊕b1e12⊕b5e16e20e24e28e32) .

而當(dāng)初始輸出狀態(tài)差分滿足 (?L9,?R9) = (0000 0000 0000 0000 0000 0000 0000 0000, 0000 0000 0000 0000 0000 0000 0000 1000), (L9,R9) 經(jīng) 4 輪 ESF 算法解密后輸出差分滿足 ?R5=(f40f80f120f160f10f5⊕10f90f130f20f60f100f140f30f70f110f150).由于 (e29e30e31e32)(0000),故(e1e5e9e13e17e21e25e29e2e6e10e14e18e22e26e30e3e7e11e15e19e23e27e31e4e8e12e16e20e24e28e32)(f40f80f120f160f10f5⊕10f90f130f20f60f100f140f30f70f110f150), 從而產(chǎn)生矛盾, 所以結(jié)論成立.

除定理1 中的不可能差分區(qū)分器外, 還找到了如下 ESF 算法的 8 輪截斷不可能差分區(qū)分器, 其中ai(1 ≤i≤15) 為任意值,b1,b2,b3不全為 0,c1,c2,c3,c4也不全 0.

4 ESF算法的13輪不可能差分分析

利用定理1 給出的 8 輪不可能差分區(qū)分器, 向上解密 2 輪, 向下加密 3 輪, 得到 ESF 算法的 13 輪不可能差分路徑, 如圖3 所示, 其中a1,a2,a3,a4,a5,a6,a7為任意值,bi/ci/di/ei/fi,i∈ {1,2,3,···} 皆不全為0.

圖3 ESF 算法的13 輪不可能差分路徑Figure 3 13-round impossible differential cryptanalysis of ESF

性質(zhì) 3若已知子密鑰K12, 便可推導(dǎo)出主密鑰k3,k2,k1,k0,k79,··· ,k54及子密鑰的值; 若已知子密鑰可推導(dǎo)出主密鑰k4.

證明:密鑰寄存器更新算法由循環(huán)移位、非線性變換S盒、常數(shù)異或三種變換組成.由于常數(shù)異或變換為線性變換且常數(shù)值已知, 其逆運(yùn)算只需在對應(yīng)位置異或同一個常數(shù)即可, 為敘述簡潔, 故不考慮密鑰編排算法中使用的常數(shù)異或變換.

密鑰比特位置的更新由循環(huán)移位變換決定.若不考慮S盒, 根據(jù)密鑰編排算法中的循環(huán)移位變換, 可得各輪子密鑰與其對應(yīng)原始主密鑰之間關(guān)系, 如表1 所示.攻擊過程中需要猜測的子密鑰與其對應(yīng)原始主密鑰之間關(guān)系, 如表2 所示.

表1 各輪子密鑰與其對應(yīng)原始主密鑰之間關(guān)系Table 1 Relationship between each round key and its corresponding original master key

表2 需要猜測的子密鑰與其對應(yīng)原始主密鑰之間關(guān)系Table 2 Relationship between guessed subkey and its corresponding original master key

由于密鑰編排算法中采用的移位數(shù)13 不是4 的倍數(shù), 會打亂半字節(jié)塊內(nèi)的順序.故需進(jìn)一步分析S盒對子密鑰與對應(yīng)原始主密鑰比特之間關(guān)系的影響.根據(jù)密鑰編排算法, 可得如下密鑰關(guān)系

由上可知, 若已知子密鑰K12, 可逆推導(dǎo)出子密鑰及主密鑰k3,k2,k1,k0,k79, ··· ,k54的值.又因?yàn)镵0=k79k78···k48, 故進(jìn)一步得出子密鑰同樣若已知子密鑰可推導(dǎo)出主密鑰k4.

利用子密鑰之間的依賴關(guān)系, 可大大減少攻擊過程中需要猜測的總密鑰數(shù), 現(xiàn)只需猜測 48 比特子密鑰結(jié)合早夭技術(shù) (early abort technique)[16], ESF 算法的 13 輪不可能差分攻擊過程具體如下.

(1) 選擇 2n個明文結(jié)構(gòu), 其中的明文滿足L0[1,3,5,7,9,11,13,19,23,25,27,29,31],R0[4,5,6,7,8,12, 13,14,15,16, 20,21,22,23,24,28,29,30,31,32]取定值, 其余比特取任意值, 故一個明文結(jié)構(gòu)包含231個明文, 可以構(gòu)造261個明文對.因此攻擊的選擇明文量為2n+31, 其中包含2n+61個明文對.這些明文對經(jīng)13 輪ESF 加密可得2n+61個密文對.

(2) 篩選出滿足如下差分的密文對 ?L13= (e130e20e60e100e140e30e70e11⊕10e150e40e80e120e160e10e50e90), ?R13=(f1⊕d1f5f9f13f17f21f25f29f2⊕d2f6f10f14f18f22f26f30f3⊕d3f7f11f15f19f23f27f31f4⊕d4f8f12f16f20f24f28f32).經(jīng)這一步篩選后平均剩余 2n+61×2?16=2n+45個數(shù)據(jù)對.

(3) 猜測第 13 輪子密鑰K12.對于剩余的數(shù)據(jù)對, 篩選出差分滿足 ?L12=(d1000 0000d2000 0000d3000 0000d4000 0000) 的數(shù)據(jù)對, 其中R12=L13>>> 7,L12=PS(R12⊕K12)⊕R13, 經(jīng)這一步過濾大約剩余 2n+45×2?28= 2n+17個數(shù)據(jù)對.這一步驟使用 “早夭技術(shù)”, 分步猜測密鑰篩選數(shù)據(jù)對.首先猜測密鑰部分解密第 13 輪變換, 判斷 ?L12第 8, 16, 24, 32 比特是否都為 0, 利用此條件篩除不符合要求的數(shù)據(jù).對保留下來的數(shù)據(jù)對再猜測判斷 ?L12第 7, 15, 23, 31 比特是否都等于 0, 篩除不符合要求的數(shù)據(jù)對.以此類推, 最后猜測不同于前 7 個半字節(jié)的密鑰猜測的是, 因?yàn)??L12第 1, 9, 17, 25 比特為不確定差分, 故無需篩選數(shù)據(jù)對.從而, 這一步驟總的計算量約為2×(2n+45×24+2n+41×28+2n+37×212+···+2n+21×228+2n+17×232)/8 =2n+50次一輪加密運(yùn)算.

(4) 已知第 13 輪子密鑰K12的取值, 由密鑰編排算法可推導(dǎo)出故對于(L12,R12) 向上解密一輪, 只需猜測子密鑰即可.對于剩于數(shù)據(jù)對, 篩選出差分滿足?L11=(0000 0000 0000 0000 0000 0100 0000 0000) 的數(shù)據(jù)對.這一步驟同樣使用 “早夭技術(shù)”, 分步猜測密鑰篩選數(shù)據(jù)對.首先根據(jù)推導(dǎo)出的判斷 ?L11[6,14,22,30,8,16,24,32]=(00100000) 是否成立, 利用此條件篩除不符合要求的數(shù)據(jù)對.其次猜測子密鑰判斷?L11[2,10,18,26,4,12,20,28]= (00000000) 是否成立, 進(jìn)一步刪選不符合要求的數(shù)據(jù)對.經(jīng)這一步過濾大約剩余2n+17×2?16=2n+1個數(shù)據(jù)對, 其計算量約為2×(2n+17×232+2n+9×232×28)/4=2n+49次一輪加密運(yùn)算.

(5) 已知第 13 輪子密鑰K12的取值, 由密鑰編排算法可推導(dǎo)出根據(jù)推導(dǎo)出的判斷?L10的第8, 16, 24, 32 比特是否全為0, 利用此條件篩除不符合要求的數(shù)據(jù)對.經(jīng)這一步過濾大約剩余 2n+1×2?4=2n?3個數(shù)據(jù)對, 其計算量約為 2×(2n+1×232×28)/8=2n+39次一輪加密運(yùn)算.

(6) 已知第 13 輪子密鑰K12的取值, 由密鑰編排算法可推導(dǎo)出故對于 (L0,R0) 向下加密一輪, 只需猜測子密鑰K25?280即可.對于剩余的數(shù)據(jù)對, 篩選出差分滿足?R1=(0000 000a1a2a3a41a5a6a700000 0000 00000000) 的數(shù)據(jù)對, 其中R1=PS(R0⊕K0)⊕L0<<< 7, 經(jīng)這一步過濾大約剩余 2n?3× 2?12= 2n?15個數(shù)據(jù)對.這一步驟的計算量約為2×2n?3×232×28×24÷2=2n+41次一輪加密運(yùn)算.

(7) 已知第 13 輪子密鑰K12的取值, 由密鑰編排算法可推導(dǎo)出故對于 (L1,R1)向下加密一輪, 只需猜測子密鑰即可.這一步驟同樣使用 “早夭技術(shù)”, 分步猜測密鑰篩選數(shù)據(jù)對.首先根據(jù)推導(dǎo)出的判斷 ?R2[2,10,18,26,3,11,19,27]= (00000000) 是否成立,利用此條件篩除不符合要求的數(shù)據(jù)對, 平均剩余 2n?15× 2?8= 2n?23.其次猜測子密鑰判斷 ?R2[4,12,20,28]= (0000) 是否成立, 經(jīng)該半字節(jié)解密后以 2?4的概率得到不可能差分區(qū)分器的輸入, 此時所猜測的密鑰是錯誤密鑰.這一步總的計算量約為2×(2n?15×232×28×24÷4+2n?23×232×28×24×24÷8)≈2n+28次一輪加密運(yùn)算.

定理 2利用8 輪不可能差分區(qū)分器對13 輪ESF 算法進(jìn)行不可能差分分析, 恢復(fù)80 比特主密鑰, 其時間復(fù)雜度為277.39次13 輪ESF 算法加密, 數(shù)據(jù)復(fù)雜度為261.99個選擇明文.

證明:上述攻擊過程中, 共猜測了 48 比特子密鑰, 經(jīng)第 7 步排除錯誤密鑰后大約剩余ε=248×(1 ? 2?4)2n?23個候選密鑰.由子密鑰可得 31 比特主密鑰k4,k3,k2,k1,k0,k79,··· ,k54,故經(jīng)第 7 步排除錯誤密鑰后, 主密鑰k4,k3,k2,k1,k0,k79,··· ,k54剩余ε種可能取值.再窮舉恢復(fù)k4,k3,k2,k1,k0,k79,··· ,k54這ε種可能取值和剩余 49 比特主密鑰, 便可唯一確定主密鑰, 其計算量為ε×249.攻擊過程中的時間復(fù)雜度主要集中在第3 步, 故當(dāng)n≈30.99 時, 13 輪ESF 算法不可能差分分析總時間復(fù)雜度約為 2n+50/13+ε× 249= 2n+50/13+248× (1 ?2?4)2n?23×249≈ 277.39次 13 輪ESF 算法加密, 數(shù)據(jù)復(fù)雜度為231+30.99=261.99個選擇明文.

5 結(jié)論

本文首先給出了ESF 算法的一些新的8 輪截斷不可能差分區(qū)分器.其次, 基于得到的8 輪不可能差分區(qū)分器, 并利用密鑰編排算法部分子密鑰間存在的依賴關(guān)系, 給出了對ESF 算法的13 輪不可能差分分析, 恢復(fù)了 80 比特主密鑰, 時間復(fù)雜度為 277.39次 13 輪 ESF 算法加密, 數(shù)據(jù)復(fù)雜度為 261.99個選擇明文.本文給出的ESF 算法不可能差分分析結(jié)果與現(xiàn)有結(jié)果對比, 如表3 所示, 其中 ID 表示不可能差分分析.

表3 ESF 算法的不可能差分分析結(jié)果對比Table 3 Comparison of impossible differential attacks on ESF