一種大狀態輕量級密碼S盒的設計與分析

樊 婷,馮 偉,韋永壯

(1.桂林電子科技大學 廣西密碼學與信息安全重點實驗室,廣西壯族自治區 桂林 541004;2.廣西網信信息技術有限公司,廣西壯族自治區 南寧 530000)

1 引 言

隨著后量子密碼、認證加密算法等研究的發展,為了提高密碼算法的安全性以及適用于更廣闊的物聯網應用環境,需要對輕量級分組密碼算法的分組長度和密鑰長度提出新的安全需求。2018年,美國國家標準與技術研究院啟動輕量級密碼算法征集計劃,接受軟硬件性能突出且適用于資源受限環境中的輕量級認證加密方案和哈希算法,2021年宣布10個算法入圍最終輪[1]。2018年8月,我國面向全國的密碼研究團隊,啟動了分組密碼算法設計競賽[2]。2019年8月公布了進入第二輪的10個候選算法,10月進入最終評選,uBlock[3]和Ballet算法[4]獲得了一等獎。在許多輕量級密碼競賽中,越來越多的方案采用大狀態置換,規模為256 bit甚至512 bit的大狀態分組密碼或內部置換被提出,如KNOT[5]、Gimli[6]和SPARKLE[7]等。葉濤等[8]于2021年基于“標志位”技術,通過構建密碼S盒的新可分性模型,搜索到KNOT-256密碼算法的30輪零和區分器。2022年,譚豪等[9]首先根據“與操作”的差分傳播規律,為Gimli置換設計了一個差分傳播系統,找到了7輪不可能差分區分器。然后向前擴展4輪,實現了11輪Gimli認證加密方案的狀態恢復攻擊。SPARKLE作為入圍NIST輕量級密碼競賽的10個最終候選算法之一,由于非線性部件采用64 bit S盒-Alzette[10],其安全性同樣備受業界關注。

Alzette是由BEIERLE等[10]提出的一種新型大狀態輕量級S盒,模加是唯一的非線性部件,循環移位量也經過了特殊選取,整個結構提供了強大的安全性來抵御許多經典攻擊。Alzette作為S盒來構造密碼算法,其安全性問題引起了眾多密碼學者的關注。2022年,許崢等[11]將 Lipmaa-Moriai限制條件與符號差分相結合,提出了一種基于可滿足性問題來搜索Alzette不可能差分區分器的自動化分析工具。在旋轉異或分析方面,HUANG等[12]擴展了模加運算中旋轉異或密碼分析的概率傳播公式,給定任意旋轉參數,能夠實現Alzette的旋轉異或差分概率的計算。LIU等[13]在2021年歐密會上發表的文章中將差分-線性密碼分析中的差分部分替換為旋轉異或差分,對4輪Alzette展開了分析。盡管如此,如何計算任意輸出掩碼的旋轉差分-線性相關性仍然未知。2022年美密會,NIU等[14]針對此問題給出一種計算任意線性輸出掩碼的 (旋轉) 差分-線性相關性的有效算法,并基于該算法推導出一種評估ARX密碼(旋轉)差分線性相關性的技術,得到了Alzette更精確的旋轉差分-線性相關性的值。2023年,LIU等[15]推廣了MORAWIECKI等[16]分析Keccak[17]的技術,找到了Alzette相關性為2-0.27的4輪差分-線性區分器和相關性為2-11.37的4輪旋轉差分-線性區分器。很顯然,對于Alzette安全性分析大多處于低輪次的研究。這是由于Alzette是一個大狀態的S盒,通過直接計算差分分布表 (Difference Distribution Table,DDT) 和線性逼近表 (Linear Approximation Table,LAT) 來評估其抗差分類/線性類分析的能力是無法實現的,突出了Alzette安全高效的特點。然而迄今為止,基于ARX結構的64 bit輕量級S盒并不多,是否存在基于ARX結構的新型大狀態輕量級S盒,如何設計出性能與安全都達到最優的大狀態輕量級S盒,也是研究的熱點。

鑒于上述存在的問題,筆者提出了一種“層次篩選法”。通過提前設置最優差分特征/線性逼近的概率值,結合混合整數線性規劃 (Mixed Integer Linear Programming,MILP) 技術構建了差分/線性密碼分析的自動化分析模型,確定了最佳循環移位參數,設計了一種基于ARX結構的64 bit輕量級密碼S盒。結果表明:當迭代輪數R=5時,新密碼S盒的最優差分特征 (線性逼近) 的概率為2-17(2-8),而此時Alzette最優差分特征 (線性逼近) 概率為2-10> 2-17(2-5> 2-8),表明了新密碼S盒抵抗差分和線性密碼分析的能力都達到了最佳。迭代6輪,新密碼S盒的最優差分特征概率為2-17;迭代 7輪,新密碼S盒的最優線性逼近概率為2-17,在抗差分/線性密碼分析方面表現出更卓越的性能。

2 基本知識介紹

2.1 符號說明

文章使用的符號如下所示:

2.2 Alzette簡介

BEIERLE等提出的Alzette對64 bitX=(X1‖X0)輸入狀態進行置換,其中,X1=(x63,…,x32),X0=(x31,…,x0),如圖1所示,分為左右2部分進行操作,每部分長度為32 bit。Alzette包括模加、異或和循環移位3種運算,c是輪常數。Alzette實例運算如算法1所示。圖1為Alzette實例結構圖示。

圖1 Alzette實例

算法1Alzette實例。

①X0←X0(X131)

③X0←X0⊕c

④X0←X0(X117)

⑥X0←X0⊕c

⑦X0←X0(X10)

⑨X0←X0⊕c

⑩X0←X0(X124)

2.3 預備知識

xy=x⊕y⊕carry(x,y) ,

(1)

(2)

(3)

(4)

(5)

cor+(Γi,Ai,Bi)=LMkn-1Mkn-2…Mk1Mk0C,

(6)

其中,Mr(0≤r≤7)表示2×2的矩陣,且

L=(1,0)是行向量,C=(1,1)T是列向量。

(7)

|cor+(Γi,Ai,Bi)=2-#{0

(8)

3 基于MILP面向ARX密碼算法的差分/線性分析模型

混合整數線性規劃問題是運籌學中的一類優化問題。目前,解決該優化問題最常見的求解器是Gurobi[22]軟件。在密碼分析領域,往往使用不等式來刻畫密碼算法的各個操作,目的是先將密碼分析問題轉化為運籌學中的MILP問題,然后進行求解,代替傳統的手工推導。為了抵抗差分/線性密碼分析,通常要求最優差分/線性特征概率要遠遠大于隨機置換概率。Alzette算法不包含S盒操作,唯一的非線性操作是模加。因此,只需要對Alzette的線性操作和模加操作構建模型,即可實現對Alzette算法抵抗差分/線性能力的評估。本節中,分別闡述最優差分特征和線性逼近自動化搜索模型的構建過程。

3.1 差分特征的自動化搜索模型

(1) XOR操作:對于a⊕b=c(a、b、c都表示單比特),用以下約束條件表示:

(9)

(10)

(3) 分支操作:對于三分支操作,假設輸入輸出差分分別為a、b、c,則約束條件為a=b=c。

(4) 模加操作:使用文獻[21]提出的針對ARX算法異或差分特征的MILP模型。主要思想是將定理1和定理2進行刻畫,轉化為不等式約束條件。用(αi,βi,γi,αi+1,βi+1,γi+1,eq(αi,βii,γi))刻畫第i與第i+1比特差分值之間的關系,其中eq(αi,βi,γi)用來計算差分概率。令eq(αi,βi,γi)=pi,用以下13個線性不等式即可表示出所有可能的56種差分模式。

(11)

(5) 額外條件:限制輸入差分只有1bit活躍,保證輸入差分非零,即(x0,x1,...,xn-1)≠0。其中,n為分組長度。

(12)

3.2 線性逼近的自動化搜索模型

與差分特征模型構建過程類似,假設模加操作的兩個輸入與連續的兩輪之間都是獨立的。

(1) 分支操作:對于三分支操作,假設輸入掩碼和輸出掩碼分別為a和b,c,用以下約束條件表示:

(13)

(2) XOR操作:對于a⊕b=c(a,b,c都表示單比特),則約束條件為a=b=c。

(3) 循環移位:與差分特征的自動化搜索模型中的循環移位操作約束條件相同。

(4) 模加操作:使用文獻[21]提出的針對ARX算法線性逼近的自動化搜索技術。主要思想是將定理3和定理4進行刻畫,轉化為不等式約束。用(si+1,Γi,Ai,Bi,si)表示狀態εi+1跳轉到εi過程,如果εi=e0,si=0;εi=e1,si=1,其中si用來計算相關系數的絕對值。用以下8個線性不等式可表示出13種所有可能的模式:

(14)

(5) 額外條件:需要添加2個額外約束條件,首先限制輸入掩碼只有1 bit活躍,保證輸入掩碼非零,即(x0,x1,…,xn-1)≠0。其中,n為分組長度。其次,設置sn=0,保證初始狀態εn=e0。

(15)

4 新密碼S盒的設計與安全性分析

密碼算法設計與評估相互促進,不可分割。在分組密碼算法的設計過程中,首先要選擇算法結構,然后再選擇各個部件的參數,比如S盒規模、循環移位量和輪常數等。當結構和篩選的參數進行優化組合后,最終需要對設計的算法進行最后的軟硬件性能評估和安全性評估。軟硬件性能指標評估一般包括吞吐量、時延和硬件面積等,而安全性評估中最經典的是差分密碼分析和線性密碼分析?？傊?設計算法的最終目標是選擇一組最優的參數,能同時保證算法的安全性和軟硬件實現效率。

4.1 新密碼S盒的設計

4.1.1 結構設計

Alzette是以ARX結構為基礎構造的S盒,可以用較低的硬件代價實現,對于一些資源受限的應用,此種低實現成本的S盒更容易構造滿足物存聯網終端設備需求的輕量級分組密碼算法。在安全性方面,S盒的規模越大,隨機產生的密碼S盒的密碼性能就越好,即具有高非線性度和低差分均勻性。為抵御差分密碼分析和線性密碼分析,同時也考慮到上述硬件實現成本,新密碼S盒仍然基于ARX結構。新密碼S盒結構如圖2所示,圖中給出的是4輪結構,每4輪稱為一個“step”,每個step中包括4個模加操作、8個循環移位、4個異或、8個分支和4個輪常數加操作。由圖可知,新密碼S盒中每個step的硬件實現成本與Alzette是保持一致的。

圖2 新密碼S盒結構圖

4.1.2 循環移位量

循環移位相當于擴散層,它的作用是將輸出打亂、混合。循環移位量的選取不僅會影響軟件實現成本,而且直接影響新密碼S盒抵抗差分/線性密碼分析的能力;如果擴散足夠好,則抵抗差分/線性密碼分析的能力則越強。這里,循環移位量的選取準則是以最小化軟件實現成本、最大化安全界為目標。出于效率的考慮,引用文獻[10]中測試Alzette實例的每個循環移位量所需要的軟件實現成本,旨在當軟件實現成本與Alzette相同時,尋找能夠更好抵抗差分/線性密碼分析的ARX盒。

表1 循環移位量的軟件實現成本

為了減少搜索空間,首先要根據軟件實現成本,計算循環移位量的可行方案。對比文獻[10]中的軟件實現成本表,當軟件實現成本14≤cost≤15,且8個循環移位量對應的軟件實現成本為(2.66,2.66,2,2.66,2.66,0,2,0)時,軟件實現成本與Alzette相同,相應的循環移位量的取值如表1所示。將所有的情況進行排列組合,循環移位量的選取共有4 096種可行方案。然后將可行方案劃分為兩類:參數重復選取和非重復選取。例如,(t0,t1,t2,t3,t4,t5,t6,t7)=(1,1,15,17,31,24,0,16)為參數重復選取,因為該方案中t0,t1都為1;而(t0,t1,t2,t3,t4,t5,t6,t7)=(1,8,15,31,16,24,17,0),由于每個參數的取值都不同,屬于參數非重復選取。經過計算,參數非重復選取的方案共有96種,如表2所示。然后,需要對96種方案進行安全性測試,節4.2給出了具體過程。

表2 96組參數

4.1.3 輪常數

添加輪常數目的是消除算法結構的對稱性,保證輪與輪之間具有一定的獨立性。文中構建的差分/線性分析的自動化搜索模型,不涉及異或輪常數的操作。因此,添加輪常數對實驗結果無影響。圖2中,c(rmod 8)表示新密碼S盒的輪常數,其中r表示輪數,c0～c7取值為c0=b7e15162,c1=bf715880,c2=38b4da56,c3=324e7738,c4=bb1185eb,c5=4f7c7b57,c6=cfbfa1c8,c7=c2b3293d.

4.2 新密碼S盒的安全性分析

新密碼S盒包含4種操作:模加、循環移位、異或和分支。在差分密碼分析中,分支操作對差分狀態無影響,因此只需要對模加、循環移位和異或操作進行建模。在線性密碼分析中,異或操作對線性掩碼無影響,只需要對模加、循環移位和分支操作進行建模。利用前面提出的自動化搜索模型,對參數非重復選取的96種方案進行測試。由于搜索空間大、耗時較長,為了提高區分器搜索概率,使用“層次篩選法”,并調用“回調函數”,測試新密碼S盒的每輪最優差分特征/線性逼近。

“層次篩選法”是指通過提前設置每輪的最優差分特征/線性逼近的上界,篩選滿足當前安全界的新密碼S盒方案。如表3所示,每輪設置的最優差分特征/線性逼近的上界稱為閾值,每兩輪的閾值是完全相同的。由于新密碼S盒的模加操作被包含在奇數輪中,因此只測試奇數輪,可得到每一輪的最優差分特征/線性逼近。但是,為了加快搜索進程,快速搜索到可滿足當前安全界的最優方案,采用圖3中的步驟進行篩選。如果滿足當前步驟設定的閾值,則保留該方案,繼續進行下一步測試,否則就從整個搜索空間中刪除該方案。其中,Q1～Q5代表執行每一步測試后剩余的候選方案集合。

表3 新密碼S盒最優差分特征/線性逼近的閾值

圖3 “層次篩選法”執行步驟

“回調函數”是Gurobi求解器中的一個函數,可以跟蹤優化過程的進度,在求解模型時提供了高級控制功能。有時候在求解過程中需要獲取一些信息、提前終止優化等,這些功能需要通過“回調函數”來實現。舉個例子,在進行安全性測試時候,需要運行一個MILP模型,當MILP模型在優化過程中顯示的當前最優值小于設定的閾值時,就可以調用“回調函數”來提前終止模型,啟動下一個模型。具體代碼如下所示。

算法2回調函數。

① def mycallback(model,where): //定義回調函數mycallback,model表示模型名,where表示回調函數觸發點

② if where == GRB.Callback.MIP: //當回調函數觸發點為當前MIP時

③ objval=model.cbGet(GRB.Callback.MIP_OBJBST) //令objval等于當前目標最優值

④ if objval <= threshold value://如果objval小于給定的閾值 threshold value

⑤ model.terminate() //終止模型

在自動化分析模型中,通過調用回調函數,可以提前終止不滿足要求的方案,縮短總體測試時間。圖4給出經過“層次篩選法”每個步驟后的剩余候選方案數量。由圖可知,執行第2步操作后,此時能滿足安全上界的方案較少,候選方案數量從96減少到16,篩除了80種不滿足的方案,為加快后續步驟的執行奠定了基礎。從第3步至第5步,候選方案數量繼續下降,保持遞減趨勢,表明了該方法是可靠的、有效的。進一步,為了體現“回調函數”對測試速度的影響,對比了使用回調函數和不使用回調函數2種情況下的測試時間,實驗平臺為Inter(R)Xeon(R)Gold 6148 CPU @ 2.40 GHz(內存224 GB),測試結果如表4所示。其中,T1表示不使用回調函數時的測試時間,T2的表示使用回調函數的測試時間。由于第1步測試時間較短,在不使用“回調函數”的情況下僅用11秒就可以完成測試,因此這里給出第2步至第5步的對比結果。由表4可知,無論執行第幾步,使用“回調函數”的情況下測試時間更短,尤其在執行第2步時,T2比T1提升了約5.4倍。

表4 測試時間對比

圖4 “層次篩選法”過程中候選方案數量變化

4.3 結果對比

經過測試,最終搜索到2種滿足條件的方案,具體結果見表5。這2種方案的8個循環移位量分別為(t0,t1,t2,t3,t4,t5,t6,t7)=(1,17,8,15,31,16,24,0)和(1,17,24,15,31,16,8,0)。與文獻[10]中Alzette的安全性進行對比,當R=5時,新密碼S盒的最優差分特征(線性逼近)的概率為2-17(2-8),而Alzette最優差分特征(線性逼近)概率為2-10>2-17(2-5>2-8);R=6時,新密碼S盒的最優差分特征概率為2-17,而此時Alzette最優差分特征概率為2-16>2-17;R=7時,新密碼S盒的最優線性逼近概率為2-17,而此時Alzette最優線性逼近概率為2-13>2-17。由此可見,與Alzette相比,新密碼S盒在第5輪就能夠更好地抵抗差分密碼分析和線性密碼分析,在第6輪和第7輪抵抗差分密碼分析和線性密碼分析的能力更出色。

表5 結果對比

5 結束語

筆者基于ARX結構,設計了一種64 bit的大狀態輕量級密碼S盒。針對循環移位量的選取,首先對候選方案進行分類,然后采用“層次篩選法”,結合MILP技術構建差分/線性密碼分析的自動化分析模型,最終搜索到2種最佳的候選方案。此外,在自動化分析模型中,通過調用“回調函數”來優化模型,將目標最優值不滿足給定條件的模型提前終止,大大縮短了運行時間,提高了搜索效率。新密碼S盒與文獻[10]的Alzette所需的軟硬件實現成本相當;在安全性分析方面,新密碼S盒在迭代5輪后比Alzette抗差分密碼分析和線性密碼分析的能力更強;隨著迭代輪數的增加,其抵抗差分/線性密碼分析的能力可以達到更高的水平。