輕量級(jí)PFP算法的差分攻擊

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

1.中國(guó)電子科技集團(tuán)公司 第十五研究所 信息產(chǎn)業(yè)信息安全測(cè)評(píng)中心，北京 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ī)密性。同時(shí)，廣泛應(yīng)用于物聯(lián)網(wǎng)工業(yè)中的典型設(shè)備主要是無(wú)線傳感器、RFID（radio frequency identification）標(biāo)簽、智能卡等體積較小的微電子產(chǎn)品。這些設(shè)備具有體積小、要求能耗低、軟硬件計(jì)算資源受限[2]、電池難以續(xù)航等特點(diǎn)。正由于這些原因，使得傳統(tǒng)的高復(fù)雜度的分組密碼算法不能直接應(yīng)用于具有低功耗要求的物聯(lián)網(wǎng)設(shè)備中。由此，設(shè)計(jì)出具有較高安全性的輕量級(jí)分組密碼算法對(duì)于實(shí)現(xiàn)物聯(lián)網(wǎng)的更廣泛應(yīng)用具有非常重要的理論意義和工程價(jià)值。

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

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

算法設(shè)計(jì)者在文獻(xiàn)[8]提出PFP算法時(shí)，對(duì)其抗差分能力、不可能差分能力也進(jìn)行了安全性評(píng)估，給出了PFP算法20輪差分活動(dòng)S盒的個(gè)數(shù)，通過(guò)計(jì)算PFP算法的15輪差分概率為2-106，從而推斷PFP算法沒有明顯的15輪差分特征；同時(shí)設(shè)計(jì)者也找到了PFP算法的5輪不可能差分區(qū)分器，進(jìn)行了6 輪的攻擊。2020 年沈璇等人[15]推導(dǎo)出了PFP的7輪不可能差分區(qū)分器，并進(jìn)行了9輪的攻擊；2022 年黃思佳等人[16]利用MILP 自動(dòng)化搜索工具找到了12 497 個(gè)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)，通過(guò)借鑒PRESENT算法的輪函數(shù)從而設(shè)計(jì)的。算法的分組長(zhǎng)度為64 bit，密鑰長(zhǎng)度為80 bit，迭代輪數(shù)為34。

1.1 常用的符號(hào)和術(shù)語(yǔ)

M：明文；

Ki：第i輪子密鑰；

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

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

⊕：按位異或。

1.2 加密變換

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

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

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

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

（2）[k79k78k77k76]=[k79k78k77k76]

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

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

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

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

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

表2 S盒Table 2 S-box

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

2 自動(dòng)化搜索差分特征MILP模型

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

2.1 XOR操作的約束

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

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

2.2 S盒操作的約束

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

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

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

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

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

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

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

然后利用MILP 進(jìn)行建模搜索，最終搜索得到了PFP算法的一個(gè)良好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算法的密鑰編排特點(diǎn)

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

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

圖3 PFP算法的密鑰編排特點(diǎn)Fig.3 Key scheduling features of PFP algorithm

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

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

根據(jù)圖2所示的22輪差分路徑，可以在區(qū)分器的前后分別添加兩輪進(jìn)行26輪的密鑰恢復(fù)攻擊，如圖4。此時(shí)，左輸入差分為[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個(gè)明文結(jié)構(gòu)，每個(gè)差分的結(jié)構(gòu)形式如：

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

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

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

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

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

因此，選擇n=40，對(duì)于猜測(cè)正確的48 bit 密鑰而言，平均有1個(gè)明密文對(duì)留下來(lái)；對(duì)于錯(cuò)誤的密鑰而言，平均有2-5個(gè)明密文對(duì)留下來(lái)。

復(fù)雜度分析：

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

步驟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個(gè)明文，一輪PFP 輪函數(shù)加密的復(fù)雜度相當(dāng)于8 次S 盒查詢，時(shí)間復(fù)雜度為(258+259+260+261+259+257+256+256)÷26÷8 ≈254.3次26 輪加密。

5 結(jié)束語(yǔ)

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