李艷俊，李寅霜，楊明華，張黎仙，劉 健

1.中國電子科技集團(tuán)公司 第十五研究所 信息產(chǎn)業(yè)信息安全測評中心，北京 100083

2.北京電子科技學(xué)院，北京 100070

3.北京工商大學(xué)，北京 100048

隨著網(wǎng)絡(luò)、通信與微電子技術(shù)的迅猛發(fā)展，物聯(lián)網(wǎng)[1]這一新興事物逐漸被廣泛應(yīng)用于多種工業(yè)領(lǐng)域。密碼技術(shù)是保障信息安全的核心技術(shù)，其中的分組密碼算法是保障信息安全傳輸?shù)闹髁髅艽a算法，它可以提供信息的機(jī)密性。同時，廣泛應(yīng)用于物聯(lián)網(wǎng)工業(yè)中的典型設(shè)備主要是無線傳感器、RFID（radio frequency identification）標(biāo)簽、智能卡等體積較小的微電子產(chǎn)品。這些設(shè)備具有體積小、要求能耗低、軟硬件計算資源受限[2]、電池難以續(xù)航等特點。正由于這些原因，使得傳統(tǒng)的高復(fù)雜度的分組密碼算法不能直接應(yīng)用于具有低功耗要求的物聯(lián)網(wǎng)設(shè)備中。由此，設(shè)計出具有較高安全性的輕量級分組密碼算法對于實現(xiàn)物聯(lián)網(wǎng)的更廣泛應(yīng)用具有非常重要的理論意義和工程價值。

近些年，一大批輕量級分組密碼被廣泛提出，如LBlock、PRESENT、Midori、LED、ZORRO、PFP[3-8]等，輕量級分組密碼在正式投入使用之前，非常有必要對它們進(jìn)行精確的安全性分析，分析成果既可以為輕量級密碼的應(yīng)用提供參考，也可以為新的輕量級密碼算法設(shè)計提供相應(yīng)的參考價值。其中PFP 算法是2017年黃玉劃等人[8]為了解決面向無線終端資源受限問題設(shè)計的超輕量級分組密碼算法。算法借鑒了國際標(biāo)準(zhǔn)PRESENT算法的設(shè)計思想，整體結(jié)構(gòu)采用了Feistel 結(jié)構(gòu)，具有更高效的軟硬件實現(xiàn)效率。

針對分組密碼，目前最有效的攻擊方法是差分分析[9]、截斷差分分析、不可能差分分析[10]、線性分析[11]、積分分析和中間相遇攻擊等。其中差分分析是由Biham等人[12]于1991 年針對DES 提出的，本質(zhì)上是尋找密碼算法中存在的高概率差分特征或差分路徑來恢復(fù)密鑰。隨著技術(shù)的發(fā)展，為了能夠快速有效找到高概率且更長的差分路徑，基于混合整數(shù)線性規(guī)劃（mixed integer linear program，MILP）、布爾可滿足性問題（Satisfiability，SAT）等數(shù)學(xué)工具的自動化差分搜索技術(shù)逐漸成熟。2014 年，Sun 等人在文獻(xiàn)[13]中通過SAGE 工具來刻畫產(chǎn)生S盒差分分布特性的線性不等式集合，并利用這些不等式構(gòu)建了搜索差分特征的MILP模型。由于搜索程序是啟發(fā)式的，得到的結(jié)果不一定是最優(yōu)，為了克服這一問題，Sun等人在文獻(xiàn)[14]中提出了一種貪心算法，將啟發(fā)式的搜索算法轉(zhuǎn)變?yōu)闇?zhǔn)確且可以實際應(yīng)用的搜索方法。

算法設(shè)計者在文獻(xiàn)[8]提出PFP算法時，對其抗差分能力、不可能差分能力也進(jìn)行了安全性評估，給出了PFP算法20輪差分活動S盒的個數(shù)，通過計算PFP算法的15輪差分概率為2-106，從而推斷PFP算法沒有明顯的15輪差分特征；同時設(shè)計者也找到了PFP算法的5輪不可能差分區(qū)分器，進(jìn)行了6 輪的攻擊。2020 年沈璇等人[15]推導(dǎo)出了PFP的7輪不可能差分區(qū)分器，并進(jìn)行了9輪的攻擊；2022 年黃思佳等人[16]利用MILP 自動化搜索工具找到了12 497 個9 輪不可能差分區(qū)分器并進(jìn)行了13輪的不可能差分攻擊，表1給出了PFP算法攻擊結(jié)果比較。

表1 PFP算法攻擊結(jié)果比較Table 1 Comparison of PFP algorithm attack results

1 PFP算法

PFP 算法采用經(jīng)典的二分支Feistel結(jié)構(gòu)，通過借鑒PRESENT算法的輪函數(shù)從而設(shè)計的。算法的分組長度為64 bit，密鑰長度為80 bit，迭代輪數(shù)為34。

1.1 常用的符號和術(shù)語

M：明文；

Ki：第i輪子密鑰；

Li：第i輪輸入的左分支64 bit；

Ri：第i輪輸入的右分支64 bit；

⊕：按位異或。

1.2 加密變換

把輸入的64 bit的分組明文M分為長度為32 bit的左右兩分支L0和R0，即M=L0||R0。

對i=0,1,2,…,33，進(jìn)行如下第i輪變換計算：

Li+1=Ri,Ri+1=Li⊕F(Ri,Ki)

34 輪迭代后輸出密文C=L34||R34。加密流程如圖1所示。

圖1 加密流程圖Fig.1 Encryption flow chart

1.3 密鑰擴(kuò)展算法

將主密鑰K=k79k78…k0存儲在一個80 bit 的密鑰寄存器中，取寄存器K的最左邊32 bit作為當(dāng)前輪的子密鑰。因此在第i輪，有Ki=ki31ki30…ki0=k79k78…k48。提取子密鑰Ki后，對當(dāng)前的密鑰寄存器K=k79k78…k0進(jìn)行以下更新操作，其中rc為當(dāng)前的輪次數(shù)，S[K]表示對K進(jìn)行S盒變換。

（1）[k79k78…k0]=[k18k17…k20k19]

（2）[k79k78k77k76]=[k79k78k77k76]

（3）[k19k18k17k16k15]=[k19k18k17k16k15]⊕rc

1.4 輪函數(shù)設(shè)計

PFP 算法的輪函數(shù)F由子密鑰加、S 盒及P 置換3個部分組成。

子密鑰加。將右分支Ri與第i輪的子密鑰Ki進(jìn)行按位異或，即對Ri=b31b30…b0，進(jìn)行如下變換：R′i=Ri⊕Ki。

S盒。PFP算法使用了PRESENT算法的S盒，如表2所示。加密時，8個相同的4 bit的S盒并行加密。

表2 S盒Table 2 S-box

P 置換。采用位排列置換，數(shù)據(jù)經(jīng)過P 置換后第i比特移動到第P(i)比特。用公式可以表示為：

2 自動化搜索差分特征MILP模型

在PFP 算法中，共涉及到3 種操作：XOR（異或）操作、P置換、S盒。其中RP置換，可以根據(jù)相應(yīng)的比特位置給出等式的約束，重點考慮另外2個操作。

2.1 XOR操作的約束

假設(shè)XOR（異或）操作的輸入差分為Δa=(Δa0,Δa1,…,Δa31) 和Δb=(Δb0,Δb1,…,Δb31) ，輸出差分為Δc=(Δc0,Δc1,…,Δc31)。對0 ≤i≤31，滿足Δai⊕Δbi=Δci。由此構(gòu)建異或操作的差分約束為：

其中，di是假設(shè)的0－1 變量，且0 ≤i≤31。

2.2 S盒操作的約束

Sun 等人在文獻(xiàn)[14]中提出了S 盒所有可能差分模式的凸閉包H表示方法，利用線性不等式來描述S盒的差分性質(zhì)，使得刻畫的S 盒差分性質(zhì)更加精確，但對每個S 盒，此方法都會產(chǎn)生大量的不等式，因此需要使用貪心算法來最大程度地減少不等式的數(shù)量。

首先需要根據(jù)S 盒的差分分布表得到PFP 算法的輸入-輸出差分分布。將輸入-輸出差分全部拆分成二進(jìn)制，得到表3。

表3 S盒的輸入-輸出差分分布表Table 3 Input-output differential distribution table for S-box

對于S 盒的輸入差分(x0x1x2x3) ，輸出差分(y0y1y2y3)，可以用向量{x0x1x2x3y0y1y2y3} 表示這種對應(yīng)關(guān)系。為了便于描述，將向量{x0x1x2x3y0y1y2y3}寫為{x0x1x2x3x4x5x6x7}的形式。由此，可以把該S 盒的輸入特征和輸出特征看作?4+4上的一個點，用集合T表示S 盒所有的輸入輸出形式向量，然后使用SAGE工具生成集合T的凸包不等式組表示H，從而得到327 個線性不等式，最后利用文獻(xiàn)[14]中提出的貪婪算法將不等式的數(shù)量化簡到23 個，化簡后的不等式如下所示：

除了所列出的約束，對于S 盒的操作還需要另外3個約束。首先假設(shè)S 盒操作的輸入差分為Δx=(x0,x1,…,x31)，輸出差分為Δy=(y0,y1,…,y31)，PFP 算法每個S盒的輸入輸出長度都為4 bit，每一輪有8個S盒，設(shè)二進(jìn)制變量Ai為第i個S 盒的活躍標(biāo)記，即當(dāng)?shù)趇個S盒活躍時，Ai=1，否則Ai=0。

約束1 輸入差分不可以全為0，用不等式刻畫為：

約束2 當(dāng)Ai的輸入差分不為0時，Ai為活躍的S盒，即對i=0,1,…,7：

然后利用MILP 進(jìn)行建模搜索，最終搜索得到了PFP算法的一個良好4輪迭代差分路徑，如表4所示。

表4 4輪迭代差分路徑Table 4 4-round iterative differential path

2.3 PFP算法的22輪差分區(qū)分器

可以迭代五次表4 所示的4 輪概率為2-11的迭代差分路徑，從而構(gòu)造出概率為2-55的20 輪差分路徑，然后再分別向前后擴(kuò)展1輪概率為2-2的差分路徑，最終構(gòu)建出有效的22輪差分區(qū)分器如圖2所示。

圖2 22輪差分區(qū)分器Fig.2 22-round differential differentiator

3 PFP算法的密鑰編排特點

通過研究PFP算法的密鑰擴(kuò)展算法，可以發(fā)現(xiàn)每一輪只有子密鑰的[31-28]比特位經(jīng)過了S盒變換和異或操作，其比特值發(fā)生改變；而其他位置的比特僅僅發(fā)生了移位，通過觀察這種規(guī)律，在密鑰恢復(fù)階段，就可以避免猜測重復(fù)的密鑰。

如圖3所示，顯然K0,[26-24]（K0的[26-24]比特位）與K1,[7-5]重復(fù)，如果先猜測了第0輪的K0,[26-24]，則第1輪的K1,[7-5]便已知，不需要再重復(fù)猜測，同樣的，顯然K24,[27-24,19]與K25,[8-5,0]相同。

圖3 PFP算法的密鑰編排特點Fig.3 Key scheduling features of PFP algorithm

當(dāng)已經(jīng)猜測了K1,[7-5]和K0,[27]時，由于這4 bit在第4 輪會一同經(jīng)過S 盒和異或操作（可計算具體值），從而得到K4,[30-28]，其值等價于K25,[31-29]，所以可以說K1,[7-5]與K25,[31-29]經(jīng)過變換后等價；同樣的，當(dāng)已經(jīng)猜測了K0,[19-16]時，這4 bit會在第12輪經(jīng)過S盒和異或操作得到K12,[31-28]，其值等價于K25,[24-21]，所以可以說K25,[23-21]與K0,[18-16]經(jīng)過變換后等價；K25,[24]與K0,[19]經(jīng)過變換后等價。

4 PFP算法的26輪密鑰恢復(fù)攻擊

根據(jù)圖2所示的22輪差分路徑，可以在區(qū)分器的前后分別添加兩輪進(jìn)行26輪的密鑰恢復(fù)攻擊，如圖4。此時，左輸入差分為[000000E0⊕P(0*0*0*0*)]，右輸入差分為[P(000000*0)⊕07000000]，其中“*”表示任意非零字節(jié)，“？”表示任意字節(jié)。

圖4 26輪密鑰恢復(fù)攻擊Fig.4 26-round key recovery attacks

步驟1 構(gòu)造2n個明文結(jié)構(gòu)，每個差分的結(jié)構(gòu)形式如：

其中，每個“*”位可選擇24-1 個值，共組成2n+39個明文對，對這些明文加密26 輪，得到相應(yīng)的2n+39個密文對。在得到的2n+39個密文對中，選擇差分形式結(jié)構(gòu)為L26=000000A0⊕P(0*0*000*)，R26=????????的，篩選后剩下密文對的個數(shù)為2n+39－20。由于R0=P(000000*0)⊕07000000 的“*”所對應(yīng)比特位的值需要與“E”經(jīng)過S盒變換后的8 個值相同，L1=000000E0⊕P(0*0*0*0*)的每個“*”需要與R0的“*”經(jīng)過擴(kuò)散后的對應(yīng)位置的8種情況抵消，篩選后剩下密文對2n+39－20－5。

步驟2 猜測K0,[27-24,19-16,11-8,3-0]總共16 bit，采用提前拋棄技術(shù)，先猜測其中的4 bit，再分三步猜測剩下的比特，計算P[S(R0⊕K1)]⊕L0，判斷是否符合R1，篩選后剩下2n+14－12個密文對。

步驟3 猜測K1,[7-4]，由密鑰編排特點可知K1,[7-5]與K0,[26-24]重復(fù)，所以這一步只需要猜測1 bit，計算P[S(R1⊕K2)]⊕L1，判斷是否符合R2，篩選后剩下2n+2－3個密文對。

步驟4 猜測K25,[31-0]全部的32 bit。先猜測K25,[31-28]，由密鑰編排特點可知，K25,[31-29]與已猜測的K1,[7-5]經(jīng)過變換后等價，所以只需要猜測1 bit 的K25,[28]；然后猜測K25,[23-20]，同樣的K25,[23-21]與K0,[18-16]經(jīng)過變換后等價，所以僅猜測1 bit的K25,[20]；接著猜測K25,[27-24]，同樣的K25,[24]與K0,[19]經(jīng)過變換后等價，所以僅猜測3 bit 的K25,[27-25]；最后，再分五步每次猜測4 bit 來猜測剩下20 bit的K25,[19-0]，計算P[S(R25⊕K26)]⊕R26，判斷是否符合L25，篩選后剩下2n－1－4－4－4－20個密文對。

步驟5 猜測K24,[27-24,19-16,3-0]，由密鑰編排特點可知，K24,[27-24,19]與已猜測的K25,[8-5,0]相同，所以這一步猜 測K24,[18-16,3-0]總 共7 bit，計 算P[S(R24⊕K25)]⊕R25，判斷是否符合L24，篩選后剩下2n－33－12=2n－45個密文對。

因此，選擇n=40，對于猜測正確的48 bit 密鑰而言，平均有1個明密文對留下來；對于錯誤的密鑰而言，平均有2-5個明密文對留下來。

復(fù)雜度分析：

步驟1 需要加密240×220=260個明文；

步驟2 需要進(jìn)行以下次S盒查詢：

步驟3 需要進(jìn)行216×21×240+5-3=259次S盒查詢；

步驟4 需要進(jìn)行的S盒查詢次數(shù)如下：

步驟5 需要進(jìn)行242×27×27=256次S盒查詢。

所以數(shù)據(jù)復(fù)雜度為260個明文，一輪PFP 輪函數(shù)加密的復(fù)雜度相當(dāng)于8 次S 盒查詢，時間復(fù)雜度為(258+259+260+261+259+257+256+256)÷26÷8 ≈254.3次26 輪加密。

5 結(jié)束語

本文對PFP 算法進(jìn)行了差分分析，通過MILP 工具搜索到了其4 輪迭代差分，從而構(gòu)造了22 輪差分路徑，進(jìn)行了26輪的密鑰恢復(fù)攻擊。攻擊過程運(yùn)用了PFP算法的密鑰編排特點，采用了提前拋棄技術(shù)，降低了計算復(fù)雜度，最終使得26 輪密鑰恢復(fù)攻擊的數(shù)據(jù)復(fù)雜度為260個明文，時間復(fù)雜度為254.3次26 輪加密。然而，如何搜索到更長的差分路徑，實現(xiàn)更多輪數(shù)的密鑰恢復(fù)攻擊則是下一步的工作。