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

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

2.北京電子科技學院，北京 100070

3.北京工商大學，北京 100048

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

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

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

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

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

1 PFP算法

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

1.1 常用的符號和術語

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，進行如下第i輪變換計算：

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

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

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

1.3 密鑰擴展算法

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

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

（2）[k79k78k77k76]=[k79k78k77k76]

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

1.4 輪函數(shù)設計

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

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

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

表2 S盒Table 2 S-box

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

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

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

2.1 XOR操作的約束

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

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

2.2 S盒操作的約束

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

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

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

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

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

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

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

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

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

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

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

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

3 PFP算法的密鑰編排特點

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

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

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

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

4 PFP算法的26輪密鑰恢復攻擊

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

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

步驟1 構造2n個明文結構，每個差分的結構形式如：

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

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

步驟3 猜測K1,[7-4]，由密鑰編排特點可知K1,[7-5]與K0,[26-24]重復，所以這一步只需要猜測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]經過變換后等價，所以只需要猜測1 bit 的K25,[28]；然后猜測K25,[23-20]，同樣的K25,[23-21]與K0,[18-16]經過變換后等價，所以僅猜測1 bit的K25,[20]；接著猜測K25,[27-24]，同樣的K25,[24]與K0,[19]經過變換后等價，所以僅猜測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個明密文對留下來。

復雜度分析：

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

步驟2 需要進行以下次S盒查詢：

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

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

步驟5 需要進行242×27×27=256次S盒查詢。

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

5 結束語

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