改進的SMBA 算法不可能差分分析*

李艷俊, 李寅霜, 汪 振, 劉 健

1.中國電子科技集團公司第十五研究所, 北京100191

2.桂林電子科技大學 廣西密碼學與信息安全重點實驗室, 桂林541004

3.北京電子科技學院, 北京100070

1 引言

2018 年中國密碼學會舉辦全國密碼設計競賽, 分組密碼方向收到30 余項參賽算法, 經過兩輪評估,2020 年1 月公布了最終入選算法1https://www.cacrnet.org.cn/site/content/854.html.SMBA[1]成為勝出的10 個算法之一, 設計者給出了較為清晰的安全界, 有效評估了算法抵抗差分攻擊、線性攻擊、不可能差分攻擊、積分攻擊等已知攻擊的強度, 其中根據基于字的自動化搜索工具給出了SMBA-128 的5 輪不可能差分路徑和SMBA-256 的1 條8 輪不可能差分路徑.目前自動化搜索工具與理論推導方法相比速度快且效率高[2–4], 但是初始建模階段非常重要, 建立模型不完善或者不正確都會導致最終搜索結果出錯或者不充分.此外, 基于比特進行自動化搜索時, 若分組長度較大或者非線性部件規模較大(如8×8 的S 盒), 則搜索的效率會急速降低.所以自動化搜索工具有其自身的局限性, 需要結合理論證明相互補充.

不可能差分分析方法[5]自1999 年Biham 于歐密會上提出之后, 被廣泛運用于各種結構分組密碼算法的安全性評估中[6–10], 分析效果較為突出.尋找不可能差分區分器是不可能差分分析的關鍵步驟, 一般采用的是中間相遇產生矛盾的方法, 即采用相反方向概率為1 的兩條截斷差分路徑, 使之無法相遇, 由此構建概率為0 的差分區分器.對于輪函數F為隨機置換的Feistel 結構算法, 1998 年Knudsen 證明至少存在5 輪不可能差分區分器[11], 但是實際中F函數無法做到真隨機, 所以基于Feistel 結構設計的算法往往存在大于5 輪的不可能差分區分器, 如2007 年Shirai 等對CLEFIA 首次提出的9 輪不可能差分區分器[12], 2007 年Wu 等人對Camellia 提出的8 輪不可能差分區分器[13]等.同樣, 對于SMBA 算法,其輪函數F不滿足隨機函數所有性質, 所以可能存在大于5 輪的不可能差分區分器.

本文對SMBA-128 算法進行了6 輪不可能差分區分器的推導和證明, 基于此區分器結合提前拋棄技術, 首次給出了9 輪密鑰恢復攻擊, 攻擊的數據復雜度和時間復雜度分別為2104.2和2121; 同理, 對SMBA-256 找到8 輪不可能差分區分器, 12 輪密鑰恢復攻擊過程類似于SMBA-12, 攻擊的數據復雜度和時間復雜度分別為2248.2和2227.6.與設計者提出的結果相比, 如表1 所示.

表1 SMBA 不可能差分分析攻擊結果比較Table 1 Comparison of SMBA impossible differential analysis attack results

2 SMBA 算法簡介

SMBA 算法基于廣義Feistel 結構設計, 創新性在于融合了SP、Feistel 和MISTY 三種結構, 分組長度支持128 比特和256 比特, 密鑰長度支持128 比特和256 比特, 算法分組長度和密鑰長度對應的迭代輪數如表2 所示.

表2 SMBA 算法的三個版本和迭代輪數Table 2 Three versions of SMBA algorithm and number of iteration rounds

2.1 符號說明

2.2 加密變換

SMBA 算法的輪函數F采用Li ?S ?Pi結構,i=64,128, 即先進行拉線變換Pi, 再按字節查詢S盒, 最后進行線性變換Li.SMBA-128 使用拉線變換P64和線性變換L64(如圖1 所示), SMBA-256 使用拉線變換P128和線性變換L128(如圖2 所示).

圖1 SMBA-128 的輪函數Figure 1 Round function of SMBA-128

圖2 SMBA-256 的輪函數Figure 2 Round function of SMBA-256

圖3 SMBA-128 的密鑰擴展過程Figure 3 SMBA-128 key expansion process

P64是一個64 比特到64 比特的變換, 具體是將64 比特數劃分為8 個字節, 即x=x0‖x1‖···‖x7,令yi=xτ(i), 其中當0≤i ≤7 時,τ(i) 依次是: 3,4,5,6,0,1,2,7.P128是一個128 比特到128 比特的變換, 具體是將128 比特數劃分為16 個字節, 即x=x0‖x1‖···‖x15, 令yi=xπ(i), 其中當0≤i ≤15時,τ(i) 依次是: 3,4,5,6,10,11,12,13,8,9,14,15,0,1,2,7.

L32是32 比特到32 比特的線性變換, 具體為是將32 比特輸入X分為4 個字節, 即X=x0‖x1‖x2‖x3, 令

則得到輸出L32(X)=y0‖y1‖y2‖y3.L64含2 個L32, 是64 比特到64 比特的變換, 具體是將64 比特數分為2 個32 比特數, 即X=XH‖XL, 令

則L64(X0‖X1)=Y0‖Y1.L128含2 個L64, 是一個128 比特到128 比特的變換, 具體是將128 比特數分為2 個64 比特數, 經過兩次L64后合并得到128 比特輸出.

2.3 密鑰擴展

密鑰擴展算法基于廣義Feistel 結構設計, 由主密鑰Key 生成N個大小為BL/2 的加密子密鑰RKi,其中0≤i ≤N ?1,N為加密輪數, BL 為分組長度.下面以算法1 SMBA-128 子密鑰生成算法為例介紹子密鑰生成.

算法1 SMBA-128 子密鑰生成算法1 U0 = MSB64(Key), V0 = LSB64(Key), 其中MSBt(x) 由x 的最左(即最高) t 比特組成的t 比特數; LSBt(x)由x 的最右(即最低) t 比特組成的t 比特數.2 D = N‖BlockLen‖KeyLen‖040, BlockLen = BL/8 為分組長度, KeyLen = BL/8 為密鑰長度, N、BlockLen、KeyLen 都用8 比特表示.3 C0 = MSB64(C)⊕D;4 進行N 個密鑰擴展輪變換(如圖3 所示), 即for i = 0 到N ?1 do 5 Xi = Ui ⊕Ci;6 Yi = α64(Xi);7 Zi = γ64(Yi);8 EKi = DKN?i?1 = Zi;9 Ui+1 = Zi ⊕Vi;10 Vi+1 = β64(Ui);11 Ci+1 = Ci ?23;12 end

常數C為自然對數的底e的小數部分的前 128 比特, 用 16 進制表示為C= 0xb7e15162,0x8aed2a6a, 0xbf715880, 0x9cf4f3c7.

變換α、β、γ對SMBA-128 來說, 使用α64、β64、γ64.α64、β64、γ64都是64 比特到64 比特的變換, 分別如下:

(1)α64是換位變換.把64 比特數x分為8 個8 比特數xi, 其中0≤i ≤7, 即x=x0‖x1‖···‖x7.令α64(x)=xψ(i), 其中當0≤i ≤7 時,ψ(i) 依次是: 2,7,1,4,6,3,5,0.

(2)β64是循環左移16 比特, 即β64(x)=x?16.

(3)γ64是S 盒變換.把64 比特數x分為8 個8 比特數xi, 其中0≤i ≤7, 即x=x0‖x1‖···‖x7.γ64(x)=Simod2(xi).

SMBA-256 的密鑰生成與SMBA-128 類似, 有興趣者可以參考算法設計文檔[1].

2.4 等價結構

在SMBA-128 算法結構中, 函數F=P64?S ?L64, 進一步我們將整體結構進行了等價變換, 即圖4(a) 和圖4(b) 等價.

圖4 等價結構Figure 4 Equivalent structure

這是因為圖4(a) 中

而圖4(b) 中

所以二者等價.

將函數F中拉線操作P64和線性變換L64的復合表示為P, 即P=L64?P64, 函數F就是一個SP結構.不失一般性, 在之后的不可能差分區分器構建和密鑰恢復攻擊中我們忽略結構兩端的置換操作P64和.

3 SMBA-128 的不可能差分分析

本節通過分析SMBA-128 算法整體和輪函數結構, 推導并證明了SMBA-128 至少存在6 輪不可能差分區分器, 最后進行了9 輪密鑰恢復攻擊, 數據復雜度和時間復雜度分別為2104.2和2121.

3.1 SMBA-128 的6 輪不可能差分區分器

證明: 此處采用反證法, 即如果不存在6 輪不可能差分區分器, 那么如圖5 所示, 在第4 輪和第5 輪之間的?處將有ΔY ⊕P{S{P[S(ΔY)]}}=P[S(ΔX)] 成立, 我們對等式兩邊進行P?1變換之后為:

P?1ΔY=S(ΔX)⊕S{P[S(ΔY)]}.

第一步, 取ΔY= 0000 000b, 那么P[S(ΔY)] =P(0000 000a) =P64[L64(0000 000a)], 其中字節a=S1(b)?=0, 此處a和b都指的是差分值.

L64(0000 000a) = [(L32(0000)⊕L32(000a) ?9)⊕L32(0000)]‖[(L32(0000)⊕L32(000a) ?9)⊕L32(000a)].

由L32的性質知,L32(0000) = (0000),L32(000a) = (aa0a), 故L64(0000 000a) = [((aa0a) ?9)]‖[((aa0a) ?9)⊕(aa0a)].設非零差分字節a= (x1x2···x8), 得(aa0a) ?9 = (x2x3···x80;0000 000x1;x2x3···x8x1;x2x3···x8x1), 然后得

遍歷a=(x1x2···x8), 得到P[S(ΔY)] 全部取值, 進而得到S{P[S(ΔY)]}全部取值:

(1) 當x1=0 時,x2x3···x8不可能同時為0, 此時S{P[S(ΔY)]}=(*****0**);

(2) 當x1=x2=···=x8=1,S{P[S(ΔY)]}=(*******0);

(3) 當x1=1,x2=x3=···=x8=0,S{P[S(ΔY)]}=(****0***);

(4) 其他情況, 易知S{P[S(ΔY)]}=(********).

僅考慮b的最高位比特y1是0 的情形, 容易得到L?164[P?164(0000 000b)] = (***0 ****).我們發現P?1(ΔY) 出現差分為0 的位置是第4 字節, 而在這個位置處S{P[S(ΔY)]}⊕S(ΔX) 的差分不可能為0, 故出現矛盾, 即P?1(ΔY)?=S{P[S(ΔY)]}⊕S(ΔX), 也即(ΔY)⊕P{S{P[S(ΔY)]}}?=P[S(ΔX)].

綜上所述, SMBA-128 存在6 輪不可能差分區分器, 輸入輸出為[0000**0*0000 0000]→[0000 000b0000 0000], 其中“*” 為非0 字節,b為最高比特為1 的非0 字節.同理可證[0000 000b0000 0000]→[0000**0*0000 0000] 也為6 輪不可能差分區分器, 符號“*” 與b滿足的條件同上.

3.2 SMBA-128 的9 輪密鑰恢復攻擊

選取6 輪不可能差分區分器的輸入差分為[0000 **0* 0000 0000], “*” 表示任意非零字節, “?” 表示任意字節, 輸出差分為[0000 000b0000 0000],b的最高比特為0 其余7 比特任意非零.在區分器之前加1 輪, 之后加2 輪, 如圖6 所示, 可以進行9 輪恢復密鑰攻擊.

圖6 SMBA-128 的9 輪密鑰恢復攻擊Figure 6 Attack on SMBA-128

攻擊步驟如下:

(1) 選擇2n個明文結構, 每個差分的結構形式: ΔX0=P(0000 **0*), ΔX1= (0000 **0*), 每個“*” 位可選擇28?1 個值, 共組成約2n+95個明文對, 對這些明文進行9 輪加密, 得到相應的2n+95密文對.

(2) 在得到的2n+95個密文對中, 選擇滿足差分結構形式為ΔX9=P(0000 000*), ΔX10= (????????), 篩選后剩下密文對2n+95?56=2n+39.

(3) 根據P[S(X9⊕RK9)]⊕X10=X8, 有S(X9⊕RK9)⊕P?1[X10] =P?1[X8], 先猜測16 比特RK9, 再分步猜RK9剩余的每個密鑰字節, 解密計算密文對是否符合P?1[X8] 對應的差分, 篩選后剩下2n+39?57=2n?18密文對.

(4) 猜測RK8的1 個字節值, 計算P[S(X8⊕RK8)]⊕X9⊕P[S(X′8⊕RK8)]⊕X′9, 判斷是否符合ΔX7, 篩選后剩下2n?18?8=2n?26密文對.

(5) 分步猜測RK1的3 個字節值, 計算P[S(X1⊕RK1)]⊕P[S(X′1⊕RK1)] 是否符合差分P(0000**0*), 若符合, 則拋棄對應密鑰.

(6) 重復上述(1)–(5) 步驟, 直到剩下唯一正確的密鑰.

上述攻擊中錯誤密鑰被留下的概率為(1?2?24)2n?26, 上述一共猜測了96 比特的密鑰值, 故留下(296?1)×(1?2?24)2n?26個錯誤密鑰.取n=56.2 時, (296?1)×(1?2?24)2n?26＜2?4, 可認為錯誤密鑰全部被淘汰.此時攻擊的數據復雜度為248×256.2= 2104.2個選擇明文; 假設每進行8 次S 盒查詢的時間與加密一輪SMBA-128 算法等價, 整個9 輪密鑰恢復攻擊過程采用了提前拋棄技術[14], 時間復雜度是(216×(296.2+28×(288.2+28×(280.2+28×(272.2+28×(264.2+28×(256.2+28×(248.2+28×(239.2+224×231.2)))))))))÷72≈2121次9 輪加密.

4 SMBA-256 的不可能差分分析

相較于SMBA-128, SMBA-256 拉線變換更復雜, 并且線性部分使用了L128, 但是二者整體結構類似, 按照相似的方法可以證明SMBA-256 至少存在8 輪不可能差分區分器.選取8 輪不可能差分區分器的輸入差分[0000 0000 0000 *000 0000 0000 0000 0000], 輸出差分為[0000 0000 0000 0000 0000 0000 0000 0*00] (其中“*” 為任意非零字節); 基于此不可能差分區分器向前加兩輪、向后加兩輪, 如圖7 所示, 進行12 輪密鑰恢復攻擊.其中X11,[13]表示X11的第13 個字節, RK12,[4,5,6,7,8,9,10,11]表示RK12的第4,5,6,7,8,9,10,11 個字節.

圖7 SMBA-256 的12 輪密鑰恢復攻擊Figure 7 Attack on SMBA-256

攻擊步驟如下:

(1) 選擇2n個明文結構, 每個差分的結構形式: ΔX0=P(0000 ???? ???? ?000), ΔX1=P(0000 0000 0000 *000), 每個“*” 位可選擇28?1 個值, 每個“?” 位可選擇28個值, 共組成約2n+159個明文對, 對這些明文進行12 輪加密, 得到相應的2n+159密文對.

(2) 在得到的2n+159個密文對中, 選擇滿足差分結構形式為ΔX12=P(0000 0000 0000 0*00),ΔX13=P(0000 ???? ???? 0000)⊕(0000 0000 0000 0*00), 篩選后剩下密文對2n+159?8×22=2n?17.

(3) 猜測RK12,[4,5,6,7,8,9,10,11]8 個字節, 根據P[S(X12⊕RK12)]⊕X13=X11, 有S(X12⊕RK12)⊕P?1[X12] =P?1[X11], 先猜測16 比特RK12, 再分步猜RK12剩余的密鑰字節, 計算是否符合P?1[X11] 對應的差分, 篩選后剩下2n?17?8×8=2n?81密文對.

(4) 猜測RK12,[0,1,2,3]4 個字節值, 計算P[S(X12⊕RK12)] 的[13] 字節位置對應值, 與X13,[13]異或得X11,[13], 同理可得X′11,[13], 猜測RK11的1 個字節值, 計算P[S(X11⊕RK11)]⊕X12⊕P[S(X′11⊕RK11)]⊕X′12是否等于ΔX10, 篩選后剩下2n?81?8=2n?89密文對.

(5) 猜測RK1,[4,5,6,7,8,9,10,11]8 個字節值,計算S(X1⊕RK1)⊕S(X′1⊕RK1)的[4,5,6,7,8,9,10,11]字節位置處輸出差分是否等于P?1(X0) 中的8 個“?” 字節, 若符合, 則留下密文對, 篩選后剩下2n?89?64 =2n?153個密文對.

(6) 猜測RK1,[0,1,2,3]4 個字節值, 計算P[S(X1⊕RK1)] 的[12] 字節位置對應值, 與X0,[12]異或得X2,[12], 同理可得X′2,[12], 猜測RK2的1 個字節值, 計算其輸出差分是否等于P?1(X1) 中的“*” 字節, 若符合, 則拋棄對應的密鑰.

(7) 重復上述(1)–(6) 步驟, 直到剩下唯一正確的密鑰.

上述攻擊中錯誤密鑰被留下的概率為(1?2?8)2n?153, 上述一共猜測了26×8=208 比特的密鑰值,故留下(2208?1)×(1?2?8)2n?153個錯誤密鑰.取n=168.2 時, (2208?1)×(1?2?8)2n?153＜2?4, 可認為錯誤密鑰全部被淘汰.此時攻擊的數據復雜度為280×2168.2=2248.2個選擇明文; 假設每進行16 次S 盒查詢的時間與加密一輪SMBA-256 算法一致, 整個12 輪密鑰恢復攻擊過程采用了提前拋棄技術[14],時間復雜度是(216×(2151.2+28×(2143.2+28×(2135.2+28×(2127.2+28×(2119.2+28×(2111.2+28×(2103.2+232×(287.2+28×(287.2+216×(279.2+28×(271.2+28×(263.2+28×(255.2+28×(247.2+28×(239.2+28×(231.2+232×(215.2+28×215.2))))))))))))))))))÷(12×16)≈2227.6次12 輪加密.

5 結論

本文對SMBA 算法進行了不可能差分分析, 針對SMBA-128 算法, 相比于設計者提出的5 輪不可能差分區分器, 本文給出了6 輪并給出了理論證明, 進一步, 基于其中一條不可能差分區分器并結合提前拋棄技術給出了9 輪密鑰恢復攻擊, 數據復雜度和時間復雜度分別為2104.2和2121; 對于SMBA-256 算法,給出了12 輪密鑰恢復攻擊, 數據復雜度和時間復雜度分別為2248.2和2227.6.

對于Feistel 結構算法, 由于輪函數F無法設計為隨機函數, 所以存在長于5 輪的不可能差分區分器,輪函數F的擴散性越差則區分器長度越長, SMBA-256 與SMBA-128 相比, 擴散性更弱, 是否存在9 輪不可能差分區分器是我們下一步的工作.