Subterranean-SAE 算法的條件立方攻擊*

劉 勇, 陳思維, 張莎莎, 向澤軍, 曾祥勇

湖北大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院 應(yīng)用數(shù)學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室, 武漢 430062

1 引言

隨著物聯(lián)網(wǎng)應(yīng)用等的大規(guī)模普及, 許多密碼算法需要應(yīng)用于低功耗、少存儲(chǔ)的應(yīng)用環(huán)境, 如射頻識(shí)別卡標(biāo)簽(RFID tag)、傳感器網(wǎng)絡(luò)(sensor network) 和智能卡(smart cards) 等, 這催生了輕量級(jí)密碼的研究與應(yīng)用. 美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院(NIST) 于2018 年開(kāi)始征集輕量級(jí)密碼算法加密標(biāo)準(zhǔn), 該活動(dòng)共接收到57 個(gè)算法. 截至2021 年3 月, 分別有56 和32 個(gè)算法成功進(jìn)入第一輪和第二輪, 第三輪的10 個(gè)候選算法也已公布. Daemen、Massolino 和Rotella 設(shè)計(jì)的Subterranean 2.0 密碼套件[1]是第二輪的32 個(gè)候選算法之一, 它包含哈希算法、認(rèn)證加密算法和消息認(rèn)證碼等多種工作模式. 本文研究的Subterranean-SAE 是Subterranean 2.0 密碼套件中的一種認(rèn)證加密算法[1].

立方攻擊(cube attack)[2]是Dinur 和Shamir 在2009 年EUROCRYPT 上首次提出的一種攻擊方法, 它是高階差分分析(higher-order differential cryptanalysis)[3]的一種變體, 被成功應(yīng)用于分析各種對(duì)稱密碼[4–6]. 立方攻擊主要分析輸出比特在選定立方下的超級(jí)多項(xiàng)式(superpoly), 并從包含密鑰信息的低次超級(jí)多項(xiàng)式中恢復(fù)密鑰信息. 條件立方攻擊(conditional cube attack)[7]是黃森洋等人在2017年EUROCRYPT 上提出的一種立方攻擊變體, 該攻擊的核心是尋找只有在所有條件等式成立時(shí)才為0的超級(jí)多項(xiàng)式. 無(wú)論是立方攻擊還是條件立方攻擊, 分析超級(jí)多項(xiàng)式是此類攻擊的關(guān)鍵. 可分性(division property)[8]是目前恢復(fù)超級(jí)多項(xiàng)式的主要方法之一. Todo 于2015 年在EUROCRYPT 上首次提出基于字的可分性[8], 隨后基于字的可分性被進(jìn)一步精確為基于比特的可分性[9]. 緊接著, Todo 等人將比特可分性引入立方攻擊[10], 與傳統(tǒng)基于實(shí)驗(yàn)方法直接測(cè)試超級(jí)多項(xiàng)式不同, 可分性可以從理論上分析超級(jí)多項(xiàng)式的性質(zhì), 故基于可分性的立方攻擊[10]不再受限于立方維數(shù). 然而利用可分性進(jìn)行密碼分析需要刻畫(huà)并搜索可分性傳播, 向澤軍等人在2016 年ASIACRYPT 上首次將混合整數(shù)線性規(guī)劃(mixed integer linear programming, MILP) 引入可分性[11]. 該方法通過(guò)提出可分跡(division trail)[11]的概念解決了可分性傳播的刻畫(huà),并將可分性的傳播用一組線性不等式刻畫(huà),從而將可分性搜索轉(zhuǎn)化成一個(gè)MILP 問(wèn)題.相比于二子集可分性, 三子集可分性能更精確地描述可分性的傳播. 王森鵬等人在2019 年ASIACRYPT上提出了三子集可分性的MILP 模型,并利用該模型進(jìn)行了基于三子集可分性的立方攻擊[12]. 隨后,郝泳霖等人在2020 年EUROCRYPT 上研究了無(wú)未知子集的三子集可分性(three-subset division property without unknown subset), 提出了一種精確計(jì)算超級(jí)多項(xiàng)式的方法并成功應(yīng)用于Trivium 等算法[13]. 胡凱等人在2020 年ASIACRYPT 上運(yùn)用單項(xiàng)式跡(monomial trail) 的概念給出了三子集可分性的另一種刻畫(huà)方法, 并成功恢復(fù)了842 輪Trivium 算法一個(gè)78 維立方的超級(jí)多項(xiàng)式[14].

目前, 已經(jīng)存在許多針對(duì)Subterranean 2.0 密碼套件安全性分析的公開(kāi)文獻(xiàn). Subterranean 2.0 密碼套件的設(shè)計(jì)文檔對(duì)該算法的密碼學(xué)性質(zhì)進(jìn)行了全面地評(píng)估, 包括差分分析(differential cryptanalysis)[15]、線性分析(linear cryptanalysis)[16]等. 2019 年, 劉富康等人分析了Subterranean-SAE 算法在三種攻擊場(chǎng)景下的安全性[17]. 首先是在nonce 重用場(chǎng)景下的全狀態(tài)恢復(fù)攻擊, 其數(shù)據(jù)復(fù)雜度為213, 時(shí)間復(fù)雜度的上界為216; 其次是在nonce 不重用場(chǎng)景下4 輪空白輪的區(qū)分攻擊, 該攻擊的數(shù)據(jù)和時(shí)間復(fù)雜度分別為233和233; 最后是在nonce 不重用場(chǎng)景下4 輪空白輪的條件立方攻擊, 其數(shù)據(jù)和時(shí)間復(fù)雜度分別為269.5和2122. 2020 年, 宋凌等人進(jìn)一步研究了Subterranean-SAE 算法密鑰流生成階段的密鑰流偏差、密鑰吸收階段的狀態(tài)碰撞和nonce 重用場(chǎng)景下的密鑰恢復(fù)攻擊[18]. 本文在上述研究工作的基礎(chǔ)上進(jìn)一步研究Subterranean-SAE 算法抗條件立方攻擊的安全性強(qiáng)度.

1.1 本文的貢獻(xiàn)

劉富康等人的條件立方攻擊首先構(gòu)造了一個(gè)65 維的條件立方, 并且假設(shè)當(dāng)條件變量滿足條件時(shí), 輸出代數(shù)次數(shù)為64; 否則為65[17]. 但是代數(shù)次數(shù)在不同情形下能否達(dá)到64 或65 并沒(méi)有被驗(yàn)證. 基于上述問(wèn)題, 本文首先研究了Subterranean-SAE 算法代數(shù)次數(shù)的評(píng)估方法, 提出了在初始狀態(tài)未知場(chǎng)景下評(píng)估輸出代數(shù)次數(shù)的新技術(shù). 利用該技術(shù), 本文成功評(píng)估得到4 輪空白輪Subterranean-SAE 算法的輸出代數(shù)次數(shù)上界為63, 因此劉富康等人構(gòu)造的條件立方攻擊輸出立方和恒為0, 即基于條件立方的密鑰恢復(fù)攻擊實(shí)際為區(qū)分攻擊.

為了進(jìn)一步構(gòu)造有效的條件立方攻擊, 本文提出了降低立方維數(shù)、擴(kuò)展立方變量選取范圍的立方搜索策略, 利用該策略本文共搜索得到24 組33 維立方. 由于本文構(gòu)造的條件立方攻擊的維數(shù)在實(shí)際可行的計(jì)算范圍內(nèi), 因此我們通過(guò)實(shí)驗(yàn)驗(yàn)證了所構(gòu)造條件立方攻擊的有效性. 通過(guò)猜測(cè)部分密鑰并利用構(gòu)造的條件立方, 我們能夠成功恢復(fù)剩余密鑰比特, 該攻擊的數(shù)據(jù)和時(shí)間復(fù)雜度分別為241.8和2124.

表1 給出了本文攻擊結(jié)果與已有結(jié)果的對(duì)比. 在nonce 不重用場(chǎng)景下, 文獻(xiàn)[17] 和本文均為4 輪空白輪(總共8 輪) Subterranean-SAE 算法的條件立方攻擊. 在nonce 不重用場(chǎng)景下, 這是首次實(shí)現(xiàn)4 輪縮減輪數(shù)Subterranean-SAE 算法的全密鑰恢復(fù)攻擊.

表1 本文結(jié)果與已有結(jié)果的對(duì)比Table 1 Comparison between proposed and known results

1.2 本文的結(jié)構(gòu)

第2 節(jié)首先進(jìn)行符號(hào)說(shuō)明, 然后簡(jiǎn)單介紹Subterranean 2.0 密碼套件的輪函數(shù)Subterranean-P 和Subterranean-SAE 認(rèn)證加密算法, 最后介紹立方攻擊、混合整數(shù)線性規(guī)劃和基于可分性的立方攻擊等相關(guān)知識(shí); 第3 節(jié)主要介紹Subterranean-P 可分性傳播的刻畫(huà)和評(píng)估4 輪空白輪Subterranean-SAE 算法輸出代數(shù)次數(shù)的方法; 第4 節(jié)提出Subterranean-SAE 算法改進(jìn)的條件立方攻擊并通過(guò)實(shí)驗(yàn)驗(yàn)證其有效性;第5 節(jié)對(duì)全文工作進(jìn)行總結(jié).

2 預(yù)備知識(shí)

2.1 符號(hào)說(shuō)明

2.2 Subterranean-P

Subterranean 2.0 密碼套件采用一個(gè)內(nèi)部狀態(tài)為257 比特的公開(kāi)置換作為其輪函數(shù), 本文記為Subterranean-P. Subterranean-P 總共包含四個(gè)操作, 其中χ操作為Subterranean-P 的非線性部件,ι、θ、π操作均為Subterranean-P 的線性部件, 記L=π?θ?ι?χ, 則有如下表示:

其中, 當(dāng)i=0 時(shí),δ[i]=1; 否則δ[i]=0.

2.3 Subterranean-SAE 認(rèn)證加密算法

首先介紹Subterranean-SAE 算法的兩個(gè)核心函數(shù).

吸收函數(shù)(duplex call, duplex(S,σ)): 首先對(duì)257 比特狀態(tài)S執(zhí)行一次Subterranean-P, 然后將不超過(guò)32 比特的信息流σ填充為33 比特(先填充1 個(gè)1, 再填充若干個(gè)0), 最后將σ[i] 異或到S[G[i]],其中G[i] 表示G的第i個(gè)元素, 如表2 所示.

表2 G 表格的取值Table 2 Details of G

返回函數(shù)(extracted output, extract(S)): 返回32 比特?cái)?shù)據(jù)S[G[i]]⊕S[G[i+32]](0≤i ≤31).

Subrranean-SAE 是Subrranean 2.0 密碼套件中以Subrranean-P 為底層置換的一種認(rèn)證加密算法,其密鑰K、nonceN、認(rèn)證標(biāo)簽(tag)T都為128 比特, 關(guān)聯(lián)數(shù)據(jù)(associated date)A和明文P的長(zhǎng)度不固定. 如圖1 所示, 算法流程共包含如下7 個(gè)階段, 算法詳情見(jiàn)文獻(xiàn)[1].

圖1 Subterranean-SAE 的結(jié)構(gòu)Figure 1 Structure of Subterranean-SAE

(1) 吸收密鑰K階段: 首先將128 比特的密鑰K分成4 個(gè)32 比特密鑰塊K0,K1,K2,K3, 然后利用duplex(S,σ) 將這些密鑰塊吸收到狀態(tài)中, 最后需要執(zhí)行1 次duplex(S,NULL) 更新內(nèi)部狀態(tài), 其中NULL 表示長(zhǎng)度為0 的塊;

(2) 吸收nonceN階段: 首先將128 比特的nonceN分成4 個(gè)32 比特nonce 塊N0,N1,N2,N3,然后利用duplex(S,σ) 將這些nonce 塊吸收到狀態(tài)中, 最后需要執(zhí)行1 次duplex(S,NULL) 更新內(nèi)部狀態(tài);

(3) 空白輪階段: 執(zhí)行8 次duplex(S,NULL) 更新內(nèi)部狀態(tài);

(6) 空白輪階段: 執(zhí)行8 次duplex(S,NULL) 更新內(nèi)部狀態(tài);

(7) 返回認(rèn)證標(biāo)簽T階段: 利用extract(S) 返回32 比特認(rèn)證標(biāo)簽T0,T1,T2,T3, 在每次返回32 比特認(rèn)證標(biāo)簽Ti(0≤i ≤3) 之間, 都需要執(zhí)行1 次duplex(S,NULL) 更新內(nèi)部狀態(tài).

2.4 立方攻擊與混合整數(shù)線性規(guī)劃

其中q(x,v) 的每一個(gè)單項(xiàng)式不含集合{vi0,vi1,··· ,vi|I|-1}中至少一個(gè)元素. 定義立方CI是遍歷立方變量{vi0,vi1,··· ,vi|I|-1}的2|I|種取值的集合, 則f(x,v) 關(guān)于CI求和滿足:

條件立方攻擊是立方攻擊的變體, 此攻擊主要分為預(yù)處理階段和在線階段. 攻擊者在預(yù)處理階段通過(guò)選取合適的立方和條件變量構(gòu)造有效的條件立方區(qū)分器, 使其滿足當(dāng)條件變量滿足條件時(shí)立方和為0, 否則立方和不為0; 在攻擊的在線階段, 攻擊者遍歷預(yù)處理階段選定立方變量的所有可能取值從而求得立方和, 并通過(guò)立方和是否為0 判斷條件變量的取值. 若這些條件變量涉及秘密變量, 則可恢復(fù)部分秘密變量信息. 在實(shí)際進(jìn)行立方攻擊或條件立方攻擊時(shí), 分析超級(jí)多項(xiàng)式為核心步驟.

可分性是目前恢復(fù)超級(jí)多項(xiàng)式的有效方法之一. 基于字的可分性是Todo 在2015 年提出的一種一般化的積分性質(zhì)[8], 可用于構(gòu)造對(duì)稱密碼更長(zhǎng)的積分區(qū)分器. 隨后, Todo 等人在2016 年提出基于比特的可分性, 并且將比特可分性分為二子集可分性和三子集可分性[9].

MILP 是一類特殊的線性規(guī)劃, 能用于高效搜索密碼算法的相關(guān)密碼學(xué)性質(zhì). Mouha 等人在2011 年將MILP 運(yùn)用在搜索基于字的對(duì)稱密碼算法活躍S 盒的下界[19]. 隨后, MILP 被應(yīng)用于差分分析[20,21]、線性分析[21]、不可能差分分析[22,23]、零相關(guān)線性分析[22]和積分攻擊[11,24]等. 利用MILP 搜索密碼算法的相關(guān)密碼學(xué)性質(zhì)時(shí)首先需要將密碼學(xué)性質(zhì)的傳播用一組線性不等式進(jìn)行刻畫(huà); 然后通過(guò)選取合適的目標(biāo)函數(shù)構(gòu)造一個(gè)完整的MILP 模型; 最后借助公開(kāi)的自動(dòng)求解優(yōu)化器Gurobi[25]搜索密碼算法的相關(guān)密碼學(xué)性質(zhì).

2.5 基于可分性的立方攻擊

文獻(xiàn)[10] 首次提出基于可分性的立方攻擊, 建立了二子集可分性和立方攻擊之間的聯(lián)系. 由于三子集可分性描述可分性的傳播更精確, 文獻(xiàn)[12] 建立了三子集可分性和立方攻擊之間的聯(lián)系, 并提出了如下定理:

由推論1 可知, 可分性可用于精確恢復(fù)超級(jí)多項(xiàng)式的代數(shù)正規(guī)型(ANF), 進(jìn)而推斷出該超級(jí)多項(xiàng)式的代數(shù)次數(shù). 在文獻(xiàn)[13] 中, 作者提出了可分性關(guān)于復(fù)制、與和異或的可分性傳播規(guī)則, 并用不等式組分別刻畫(huà)了三個(gè)基本操作的MILP 模型. 此外, 文獻(xiàn)[26] 研究了異或常數(shù)1 的可分性傳播規(guī)則, 并用不等式組刻畫(huà)了異或常數(shù)1 的MILP 模型. 在本文中:

不等式組COPY(b,a0,a1,··· ,am-1) 表示將變量b復(fù)制成m個(gè)變量a0,a1,··· ,am-1(即b=a0=a1=···=am-1) 的MILP 模型.

不等式組AND(a0,a1,··· ,am-1,b) 表示將m個(gè)變量a0,a1,··· ,am-1進(jìn)行與操作得到變量b(即b=a0·a1·····am-1) 的MILP 模型.

不等式組XOR(a0,a1,··· ,am-1,b) 表示將m個(gè)變量a0,a1,··· ,am-1進(jìn)行異或操作得到變量b(即b=a0⊕a1⊕···⊕am-1) 的MILP 模型.

行臺(tái)，即行尚書(shū)臺(tái)。霸府行臺(tái)，是由控制朝政的強(qiáng)臣組建的行臺(tái)。霸府行臺(tái)實(shí)際上是不受皇權(quán)約束、駕凌于皇權(quán)之上的，是為強(qiáng)臣控制政權(quán)服務(wù)的。北魏霸府行臺(tái)從孝莊帝建義元年（528年）爾朱榮擔(dān)任北道大行臺(tái)開(kāi)始，先后經(jīng)歷了爾朱仲遠(yuǎn)、爾朱兆、爾朱天光等爾朱氏霸府行臺(tái)，高歡霸府行臺(tái)和宇文泰霸府行臺(tái)。下面討論一下這些論霸府行臺(tái)首長(zhǎng)的特征

不等式組XOR(a,1,b) 表示將變量a和常數(shù)1 進(jìn)行異或操作得到變量b(即b=a ⊕1) 的MILP 模型.

3 評(píng)估4 輪空白輪Subterranean-SAE 算法輸出的代數(shù)次數(shù)上界

由于文獻(xiàn)[17] 的條件立方攻擊假設(shè)當(dāng)條件變量滿足條件時(shí), 輸出代數(shù)次數(shù)為64; 否則為65. 為了驗(yàn)證該條件立方攻擊的有效性, 本節(jié)研究4 輪空白輪Subterranean-SAE 算法的輸出代數(shù)次數(shù)評(píng)估.

3.1 構(gòu)建4 輪空白輪Subterranean-SAE 算法的MILP 模型

利用2.5 節(jié)給出的可分性傳播規(guī)則, 可將刻畫(huà)Subterranean-P 可分性傳播的MILP 模型分為以下三個(gè)部分, 具體細(xì)節(jié)如圖2 所示:

圖2 Subterranean-P 和吸收nonce N 的MILP 模型Figure 2 MILP model for Subterranean-P and absorbing nonce N

由算法流程可知, 在進(jìn)行4 輪空白輪之前, 內(nèi)部狀態(tài)需以異或的方式對(duì)nonce 信息(N0,N1,N2,N3)進(jìn)行吸收. 由于本節(jié)是對(duì)4 輪空白輪輸出比特關(guān)于nonce 變量(N1,N2,N3) 的代數(shù)次數(shù)進(jìn)行評(píng)估(見(jiàn)圖3), 因此需要考慮(N1,N2,N3) 的可分性對(duì)整體可分性傳播的影響. 另外, 在吸收nonce 的同時(shí), 狀態(tài)的某個(gè)比特還需要與常數(shù)1 異或. 令向量nr= (n0r,n1r,··· ,n31r) 表示nonceNr+1的可分性, 其中0≤r ≤2, 則刻畫(huà)吸收nonceNr+1可分性傳播的MILP 模型為:

圖3 Subterranean-SAE 算法條件立方攻擊的攻擊區(qū)域Figure 3 Attack areas of conditional cube attacks for Subterranean-SAE

3.2 評(píng)估4 輪空白輪Subterranean-SAE 算法輸出的代數(shù)次數(shù)上界

由于劉富康等人攻擊區(qū)域的初始狀態(tài)S′0(如圖3) 的257 比特均包含密鑰信息(即未知), 且本文利用已有的技術(shù)無(wú)法在有限計(jì)算資源下評(píng)估出輸出代數(shù)次數(shù), 故本文提出定理2, 用于初始狀態(tài)未知場(chǎng)景下的輸出代數(shù)次數(shù)評(píng)估.

證明: 由于MILP 模型中刻畫(huà)可分性u(píng)的約束條件的取值區(qū)間完全包含刻畫(huà)可分性u(píng)′的約束條件的取值區(qū)間, 所以u(píng)f→1 的可分跡條數(shù)一定大于等于u′f→1 的可分跡條數(shù). 故若無(wú)未知子集三子集可分性滿足uf→1 的可分跡條數(shù)為0, 則滿足u′f→1 的可分跡條數(shù)也一定為0.

假設(shè)固定立方變量不變, 對(duì)于MILP 模型中未知比特的可分性無(wú)任何約束條件時(shí)模型無(wú)解, 即可分性跡條數(shù)為0, 那么由定理2 可知, 無(wú)論初始狀態(tài)未知比特的真實(shí)取值如何, 其對(duì)應(yīng)輸入可分性傳播到特定輸出可分性的可分跡條數(shù)也一定為0. 類似的, 在其他狀態(tài)位不變的情況下, 假設(shè)MILP 模型中對(duì)于nonce的非立方變量可分性無(wú)任何約束得到模型無(wú)解, 那么無(wú)論nonce 中非立方變量真實(shí)取值如何, 其對(duì)應(yīng)的可分跡條數(shù)也一定為0.

通過(guò)以上分析, 構(gòu)建用于評(píng)估4 輪空白輪Subterranean-SAE 算法代數(shù)次數(shù)上界的MILP 模型具體流程如算法1 所示. 在算法1 中, 第1–11 行約束N1,N2和N3中立方變量的可分性為1, 非立方變量無(wú)任何約束條件; 第12–13 行約束輸出可分性的漢明重量為1, 且輸出可分性為1 的比特索引為op; 第15行表示利用3.1 節(jié)給出的MILP 模型對(duì)第i輪Subterranean-P 和吸收nonceN進(jìn)行刻畫(huà); 第18 行表示模型的優(yōu)化狀態(tài)為Status. 若Status = 2, 表示模型有解; 若Status = 3, 表示模型無(wú)解; 若Status 為其他值, 表示模型報(bào)錯(cuò). 在選定立方變量后, 若模型無(wú)解, 由定理2 可知輸出比特SR[G[op]]⊕SR[G[op+32]]中對(duì)應(yīng)的超級(jí)多項(xiàng)式為0, 進(jìn)一步可推斷輸出比特SR[G[op]]⊕SR[G[op+32]] 的ANF 中不存在以立方變量乘積構(gòu)成的單項(xiàng)式.

算法1 返回MILP 模型的優(yōu)化狀態(tài)Input: 輪數(shù)R, N1,N2 和N3 中立方變量索引集I0,I1 和I2, 輸出比特索引op, 空MILP 模型M.Output: 模型的優(yōu)化狀態(tài)Status.1 for 0 ≤i ≤31 do 3 2 if G[i] ∈I0 then M.con ←ni0 = 1 4 end 5 if G[i] ∈I1 then M.con ←ni1 = 1 7 end 8 if G[i] ∈I2 then 6 M.con ←ni2 = 1 ?約束N1,N2 和N3 中立方變量的可分性為1, 非立方變量無(wú)任何約束條件.10 end 11 end 12 M.con ←uG[op]9 R +uG[op+32]R = 1 13 M.con ←Σi∈{0,1,···,256}uiR = 1 14 for i = 0 to R-1 do 15 刻畫(huà)第i 輪Subterranean-P 和異或nonce N 的可分性傳播16 end 17 M.optimize()18 Status = M.Status()19 return Status ?當(dāng)Status = 2 時(shí), 模型有解; 當(dāng)Status = 3 時(shí), 模型無(wú)解; 當(dāng)Status 為其他值時(shí), 模型報(bào)錯(cuò).

為了評(píng)估輸出代數(shù)次數(shù)上界, 需要多次調(diào)用算法1. 記N1,N2和N3中的立方索引集合分別為I0,I1和I2, 假設(shè)初始的立方變量數(shù)為n, 即|I0|+|I1|+|I2|=n, 若算法返回值為2, 停止調(diào)用算法1 且可推斷代數(shù)次數(shù)上界為n; 若算法返回值為3, 則說(shuō)明代數(shù)次數(shù)小于n, 此時(shí)需要從立方集合中移除1 個(gè)立方變量, 使得|I0|+|I1|+|I2|=n-1, 更新I0,I1和I2并繼續(xù)運(yùn)行算法1. 對(duì)于()種新立方集合, 如果至少存在1 種情況使得算法1 返回值為2, 停止調(diào)用算法1 且可推斷代數(shù)次數(shù)上界為n-1, 否則代數(shù)次數(shù)小于n-1, 此時(shí)繼續(xù)從立方集合中移除1 個(gè)立方變量, 重復(fù)以上步驟, 直到模型無(wú)解為止.

3.3 代數(shù)次數(shù)評(píng)估結(jié)果

記Ii0,Ii1和Ii2(0≤i ≤21) 分別表示文獻(xiàn)[17] 的第i個(gè)立方中N1,N2和N3的立方變量索引集. 本文利用算法1 對(duì)4 輪空白輪Subterranean-SAE 算法輸出代數(shù)次數(shù)的評(píng)估結(jié)果如表3 所示.

(1) 表3 中第2 行表示: 對(duì)于除第7 個(gè)之外的立方變量索引集, 32 個(gè)輸出比特關(guān)于立方變量的代數(shù)次數(shù)上界為62;

(2) 表3 中第3 行表示: 對(duì)于第7 個(gè)立方變量索引集I70,I71,I72, 輸出第0,2,3,4,6,7,9,11,13,16,17,18,19,20,21,22,23,24,25,26,29,31 比特關(guān)于立方變量的代數(shù)次數(shù)上界為62;

(3) 表3 中第4 行表示: 對(duì)于第7 個(gè)立方變量索引集I70,I71,I72, 輸出第1,5,8,10,12,14,15,27,28,30比特關(guān)于立方變量的代數(shù)次數(shù)上界為63.

表3 算法1 的實(shí)驗(yàn)結(jié)果Table 3 Experimental results of Algorithm 1

從表3 中的實(shí)驗(yàn)結(jié)果可知, 任意選取文獻(xiàn)[17] 中的立方變量集, 32 個(gè)輸出比特關(guān)于立方變量的代數(shù)次數(shù)上界為63, 而文獻(xiàn)[17] 中條件立方攻擊的立方變量總數(shù)為65, 因此輸出立方和恒為0. 此外, 文獻(xiàn)[17]中第3 個(gè)立方索引集的I31包含{30,111,137,223},I32包含{2,4,11,15,17,22,30,35,64,70,95,111,128,134,137,140,165,169,176,184,190,197,211,213,223,225,234,241,249}, 與其區(qū)分攻擊模型中的33 維立方區(qū)分器所選立方索引集完全一致, 而該區(qū)分攻擊已通過(guò)實(shí)驗(yàn)驗(yàn)證其正確性. 所以文獻(xiàn)[17] 中利用I30,I31,I32構(gòu)造條件立方攻擊時(shí), 無(wú)論條件變量取值如何, 其輸出立方和恒為0. 該結(jié)果從側(cè)面印證了本文算法1 評(píng)估代數(shù)次數(shù)上界的正確性.

4 Subterranean-SAE 算法改進(jìn)的條件立方攻擊

由于文獻(xiàn)[17] 的條件立方攻擊被證實(shí)為區(qū)分攻擊, 本節(jié)繼續(xù)深入研究并提出4 輪空白輪Subterranean-SAE 算法可被實(shí)驗(yàn)證實(shí)有效的條件立方攻擊.

本節(jié)采用降低立方維數(shù)、擴(kuò)展立方變量選取范圍的策略, 實(shí)現(xiàn)對(duì)4 輪空白輪Subterranean-SAE 算法條件立方攻擊的改進(jìn). 本節(jié)通過(guò)在N2和N3中共挑選33 維立方構(gòu)造4 輪空白輪Subterranean-SAE 算法條件立方攻擊, 其中挑選的33 維立方要求當(dāng)條件滿足時(shí), 立方和恒為0; 否則立方和取值不定. 通過(guò)分析Subterranean-P 不難發(fā)現(xiàn), 經(jīng)Subterranean-P 更新后狀態(tài)的二次項(xiàng)由上一輪兩個(gè)相鄰狀態(tài)相乘產(chǎn)生,所以為了降低輸出關(guān)于立方變量的代數(shù)次數(shù), 本節(jié)選擇不相鄰且在經(jīng)過(guò)一輪狀態(tài)更新后仍不相鄰的狀態(tài)比特作為立方變量, 而條件變量的選取則取決于立方變量. 如圖3 所示, 搜尋立方變量及對(duì)應(yīng)條件的具體步驟如下:

(1) 選擇N2中的n2個(gè)比特N2[i0],N2[i1],··· ,N2[in2-1] 作為立方變量, 其他變量設(shè)為常數(shù), 其中ij ∈{G[0],G[1],··· ,G[31]}(j ∈{0,1,··· ,n2-1}), 這些比特在S2互不相鄰;

(2) 選擇N3中的n3個(gè)比特N3[i0],N3[i1],··· ,N3[in3-1] 作為立方變量, 其他變量設(shè)為常數(shù), 其中ij ∈{G[0],G[1],··· ,G[31]}(j ∈{0,1,··· ,n3-1}), 這些比特在S3互不相鄰;

(3) 選擇S2中的1 個(gè)變量S2[condition] 作為條件變量. 當(dāng)條件變量S2[condition] 滿足條件f(S2[condition]) = 0 (f(S2[condition]) =S2[condition] 或S2[condition]⊕1) 時(shí),N2中的n2個(gè)立方變量經(jīng)一輪傳播后在S3互不相鄰, 并且與N3中的n3個(gè)立方變量在S3不相鄰; 當(dāng)S2[condition] 不滿足條件f(S2[condition])=0 時(shí),S3一定存在相鄰的立方變量.

通過(guò)重復(fù)以上步驟, 本文共搜索到24 組33 維立方, 如附錄中表5 所示, 其中立方變量索引集I0和I1分別表示N2和N3的狀態(tài)位. 需要注意的是, 本文的立方變量在N2和N3中選取, 文獻(xiàn)[17] 的立方變量在N1,N2和N3中選取. 通過(guò)對(duì)比發(fā)現(xiàn), 本文找到的24 組立方中有17 組立方的立方變量索引與文獻(xiàn)[17] 中N1和N2的立方變量索引一致, 但挑選這些立方的nonce 塊有區(qū)別. 此外, 本文在搜索立方的過(guò)程中增加了立方變量的選取范圍, 即當(dāng)條件滿足時(shí),N2和N3的立方變量在S2和S3都不相鄰, 輸出的代數(shù)次數(shù)最高為32; 但是當(dāng)條件不滿足時(shí),N2的立方變量經(jīng)1 輪傳播后在S3相鄰, 并與N3的立方變量在S3不相鄰, 輸出的代數(shù)次數(shù)最高為33.

由于本文挑選的立方維數(shù)均為33, 因此對(duì)于條件立方攻擊的有效性, 可直接通過(guò)計(jì)算其在不同條件下輸出的立方和進(jìn)行驗(yàn)證. 對(duì)于附錄中表5 的每個(gè)立方變量集合, 在無(wú)關(guān)聯(lián)數(shù)據(jù)場(chǎng)景下(即關(guān)聯(lián)數(shù)據(jù)的長(zhǎng)度為0), 本文共選取22 組不同的密鑰K0,K1,K2,K3進(jìn)行立方求和實(shí)驗(yàn). 對(duì)于每1 組密鑰, 固定N3中非立方變量,N0,N1以及P0為常數(shù)0, 選取N2中非立方變量為任意常數(shù), 對(duì)條件變量S2[condition] 滿足和不滿足條件分別進(jìn)行64 次實(shí)驗(yàn). 實(shí)驗(yàn)結(jié)果表明,在22×64=1408 次實(shí)驗(yàn)中,當(dāng)條件變量S2[condition]滿足條件時(shí), 32 個(gè)輸出比特立方和都恒為0; 當(dāng)條件變量S2[condition] 不滿足條件時(shí), 32 個(gè)輸出比特立方和存在不為0 的實(shí)驗(yàn)次數(shù)和概率如表4 所示. 該實(shí)驗(yàn)結(jié)果證實(shí)本文構(gòu)造的條件立方攻擊有效.

表4 條件立方攻擊的實(shí)驗(yàn)結(jié)果Table 4 Experimental results of conditonal cube attacks

一旦構(gòu)造有效的條件立方攻擊后, 即可恢復(fù)條件變量(中間狀態(tài)). 由表4 可知, 當(dāng)條件不滿足時(shí), 立方和為1 依概率存在, 故需要進(jìn)行多次立方求和實(shí)驗(yàn)來(lái)確定條件變量的真實(shí)值. 在恢復(fù)條件變量的過(guò)程中,N3中非立方變量以及N0,N1固定為常數(shù)0, 而N2中非立方變量選取不同的常數(shù)值. 條件變量(中間狀態(tài)) 恢復(fù)后, 即可用以構(gòu)造方程恢復(fù)密鑰, 其具體步驟如下:

5 總結(jié)

在利用無(wú)未知子集三子集可分性評(píng)估輸出代數(shù)次數(shù)時(shí), 若攻擊模型中初始狀態(tài)的具體取值未知, 則構(gòu)建MILP 模型時(shí)無(wú)法給出初始狀態(tài)的約束條件. 本文首次提出一種在初始狀態(tài)未知時(shí)利用MILP 模型評(píng)估輸出代數(shù)次數(shù)的技術(shù), 并證明了通過(guò)該技術(shù)構(gòu)建的模型無(wú)解時(shí), 無(wú)論初始狀態(tài)的真實(shí)取值如何, 其對(duì)應(yīng)的MILP 模型也一定無(wú)解, 即輸出立方和為0, 由此可評(píng)估輸出關(guān)于立方變量的代數(shù)次數(shù)上界. 在劉富康等人對(duì)4 輪空白輪Subterranean-SAE 算法進(jìn)行的基于條件立方的密鑰恢復(fù)攻擊模型中, 初始狀態(tài)均涉及未知的密鑰信息. 我們成功將本文的代數(shù)次數(shù)評(píng)估技術(shù)運(yùn)用于Subterranean-SAE 算法并證實(shí)劉富康等人的攻擊實(shí)際為區(qū)分攻擊. 進(jìn)一步, 本文通過(guò)分析Subterranean-P, 提出了一種新的立方變量選取策略,并搜尋到了更多的條件立方. 利用這些條件立方, 可以對(duì)縮減至4 輪空白輪的Subterranean-SAE 算法進(jìn)行全密鑰恢復(fù)攻擊, 并且本文通過(guò)實(shí)驗(yàn)驗(yàn)證了該攻擊的有效性. 通過(guò)統(tǒng)計(jì)分析, 該攻擊的正確率不低于99.83%. 在nonce 不重用場(chǎng)景下,這是首次實(shí)現(xiàn)4 輪縮減輪數(shù)Subterranean-SAE 算法的全密鑰恢復(fù)攻擊.