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

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

1 引言

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

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

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

目前, 對于 ESF 算法有多個安全性分析結(jié)果.徐朋[11]給出了 ESF 算法的差分故障攻擊, 尹軍等人[12]給出了 ESF 算法的 13 輪相關(guān)密鑰差分分析.而ESF 算法的不可能差分分析結(jié)果相對較多, 最初劉宣等人[13]給出了 ESF 算法一條 8 輪不可能差分區(qū)分器, 并給出了 11 輪不可能差分分析, 之后陳玉磊等人[14]基于同一條 8 輪不可能差分區(qū)分器改進了 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)的符號進行說明及介紹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的二進制表示

?不確定的比特差分

∥二進制字符連接

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 比特的順序進行重新排列.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 比特, 密鑰擴展設(shè)計與 LBlock 算法類似.將主密鑰K=k79k78···k1k0存入密鑰寄存器, 每一輪取寄存器最左端32 比特作為子密鑰.對于0 ≤i≤31 , 擴展算法可表述為

在得到第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ī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)的順序.故需進一步分析S盒對子密鑰與對應(yīng)原始主密鑰比特之間關(guān)系的影響.根據(jù)密鑰編排算法, 可得如下密鑰關(guān)系

由上可知, 若已知子密鑰K12, 可逆推導(dǎo)出子密鑰及主密鑰k3,k2,k1,k0,k79, ··· ,k54的值.又因為K0=k79k78···k48, 故進一步得出子密鑰同樣若已知子密鑰可推導(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é)的密鑰猜測的是, 因為 ?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次一輪加密運算.

(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) 是否成立, 進一步刪選不符合要求的數(shù)據(jù)對.經(jīng)這一步過濾大約剩余2n+17×2?16=2n+1個數(shù)據(jù)對, 其計算量約為2×(2n+17×232+2n+9×232×28)/4=2n+49次一輪加密運算.

(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次一輪加密運算.

(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次一輪加密運算.

(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次一輪加密運算.

定理 2利用8 輪不可能差分區(qū)分器對13 輪ESF 算法進行不可能差分分析, 恢復(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