縮減輪的超輕量級分組密碼算法PFP的不可能差分分析

趙光耀，沈 璇，余 波，易晨暉，李 禎

（1.湖南信息學院 電子科學與工程學院，長沙 410151；2.國防科技大學 信息通信學院，武漢 430010）

0 引言

由于物聯(lián)網(wǎng)終端設備的便攜性要求及應用場景資源條件限制，傳統(tǒng)的分組密碼算法［1］不能很好地直接應用于這些設備。基于此，學者們提出PRESENT［2］、MIBS［3］、LED［4］、LBlock［5］、KLEIN［6］、SIMECK［7］等適用于資源受限環(huán)境的輕量級密碼算法。

超輕量級密碼算法PFP［8］借鑒了PRESENT 算法的設計思想，它的輪函數(shù)采用混淆-擴散（Substitution-Permutation，SP）結(jié)構，且使用與PRESENT 算法相同的S 盒，算法整體上采用Feistel 結(jié)構，可保持加解密一致，進一步減小內(nèi)存需求并提高硬件實現(xiàn)效率。在資源極端受限環(huán)境下，硬件實現(xiàn)密碼算法要求門電路數(shù)不超過2 000 個等效門（Gate Equivalences，GE）。文獻［8］中對PFP 算法分別進行了硬件與軟件實現(xiàn)，并對相關性能指標進行了測試。硬件實現(xiàn)方面，PFP 算法需要的門電路數(shù)約為1 335 GE，低于PRESENT算法的1 570 GE。軟件實現(xiàn)方面，基于同樣的平臺和編程語言，對PFP 與PRESENT 算法的加解密速度進行對比測試，在含密鑰編排與不含密鑰編排兩種模式下，PFP 算法的軟件加解密效率均為PRESENT 算法的1.5 倍。所以，PFP 算法能夠滿足物聯(lián)網(wǎng)無線終端設備等資源極端受限環(huán)境的應用需求。

在密碼算法安全性評估方面，差分分析［9］自提出后一直是分組密碼安全性分析的主要方法之一，在分組密碼分析領域產(chǎn)生了重大影響。在它的基礎上，還衍生出了如截斷差分分析［10］、多重差分分析［11］、不可能差分分析等［12］多種分析方法。不可能差分分析［12-13］利用概率為零的不可能差分將錯誤密鑰篩除，從而獲得正確密鑰。利用不可能差分對多種分組密碼算法的安全性分析［14-19］取得了較好的效果。

PFP 算法的不可能差分分析結(jié)果如下：2017 年，黃玉劃等［8］利用中間相錯技術構造了5 輪不可能差分區(qū)分器，并對6 輪PFP 算法進行分析，可恢復32 b 的種子密鑰，該方法僅利用了輪函數(shù)為雙射的性質(zhì)，并沒有充分利用輪函數(shù)的具體細節(jié)；2020 年，沈璇等［20］深入研究PFP 算法輪函數(shù)中S 盒的差分性質(zhì)，構造出7 輪不可能差分區(qū)分器，并利用該區(qū)分器分析了9 輪的PFP 算法，恢復了36 b 的種子密鑰，分析所需的數(shù)據(jù)復雜度為236個選擇明文、時間復雜度為258次9 輪加密。

本文基于文獻［20］深入分析了PFP 算法的輪函數(shù)，發(fā)現(xiàn)了S 盒的兩組概率為1 的差分；結(jié)合輪函數(shù)線性置換層的特性，構造出PFP 的一組7 輪不可能差分區(qū)分器；并基于新的7輪不可能差分區(qū)分器，對9 輪PFP 的不可能差分分析進行改進；進一步提出對10 輪PFP 算法的不可能差分分析方法。

1 PFP算法

1.1 PFP算法整體框架

PFP 算法［8］分組長度為64 b，密鑰長度為80 b，總輪數(shù)為34 輪。算法整體采用Feistel 結(jié)構，加密流程如圖1 所示。

圖1 PFP算法加密流程Fig.1 Encryption flow of PFP

64 b 的分組數(shù)據(jù)分為各32 b 的左右兩個分支，若記一輪迭代的輸入為（Li，Ri），輸出為（Li+1，Ri+1），則有：

其中：F表示輪函數(shù)；Ki表示第i輪的輪密鑰。Li、Ri及Ki均為32 b。明文P=(L0，R0)，經(jīng)過34 輪迭代后得到密文C=(L34，R34)，最后一輪左右兩支不交換。

1.2 PFP算法輪函數(shù)

PFP 算法的輪函數(shù)采用SP 結(jié)構，主要包含輪密鑰加、S層變換及P 置換三個操作。輪函數(shù)結(jié)構如圖2 所示。

圖2 輪函數(shù)F的加密流程Fig.2 Encryption flow of round function F

輪密鑰加：Ri與輪密鑰Ki逐比特異或。

S 層變換：由8 個相同的4 b 的S 盒并置組成，其中S 盒與輕量級分組密碼國際標準算法PRESENT 的S 盒相同，如表1所示。記S 層輸入為，輸出為則 有Bi=S(Ai)，Ai和Bi（i=0，1，…，7）均為4 b，“|”表示比特串間的聯(lián)結(jié)。

表1 PFP算法的S盒Tab.1 S-box of PFP

P 置換：采用比特拉線設計，32 b 數(shù)據(jù)按照如下規(guī)律進行比特置換，即輸入的第i比特經(jīng)過P 置換后變?yōu)榈赑(i)比特。

2 7輪不可能差分區(qū)分器構造

沈璇等［20］分析S 盒的差分性質(zhì)，構造出PFP 算法的一個7 輪不可能差分區(qū)分器，該區(qū)分器的長度比設計者構造的長2 輪。本章進一步分析輪函數(shù)中P 置換的特點，對文獻［20］中的7 輪不可能差分區(qū)分器進行拓展。

表2 為S 盒的差分分布表，數(shù)值為滿足該輸入輸出差分方程對應的解的個數(shù)，H 代替數(shù)字16，值為0 說明對應的輸入差分經(jīng)過S 盒后不能產(chǎn)生該輸出差分。

表2 PFP算法S盒的差分分布表Tab.2 Differential distribution table of S-box of PFP

通過分析S 盒的差分分布表，可得以下性質(zhì)：

性質(zhì)1 當PFP 算法的S 盒的輸入差分滿足a00(a⊕1)或b00b的形式（a和b均為0 或1）時，它們經(jīng)過S 盒后，輸出差分的最低比特確定，即有如下2 條差分以概率1 成立：

其中，*表示該比特差分不確定，可能為0 或1。

PFP 算法采用Feistel 結(jié)構，令032表示連續(xù)32 b 為0，αi、βj均為32 b（i=0，1，2，3，j=0，1，2），ΔFr(αi)（或ΔFr(βj)）表示當輸入差分為αi（或βj）時經(jīng)過連續(xù)r輪F函數(shù)后所有可能輸出差分的集合，則差分傳播規(guī)律如表3 所示。

表3 PFP算法的差分傳播規(guī)律Tab.3 Differential propagation rules of PFP

由表3 可知：(α0，032) →(032，β0)是PFP 算法的7 輪可能差分的必要條件是α2=β2；若α2≠β2，則(α0，032) →(032，β0)一定是PFP 算法的7 輪不可能差分。

基于性質(zhì)1，可構造PFP 算法的7 輪不可能差分區(qū)分器。

定理1 在PFP 算法中，當輸入差分為(α0，032)，輸出差分為(032，β0)，α0滿足(?16|a00(a⊕b)|c00c|d00d|(b⊕1)00*)，且β0滿足(?16|016)的形式時，(α0，032) →(032，β0)是PFP 算法的7 輪不可能差分區(qū)分器。其中，α0和β0均為32 b 的差分；*表示該位置的比特差分不確定；?i表示連續(xù)i比特為*；0i表示連續(xù)i比特為0；a，b，c，d均為0 或1。

證明只需證明當α0滿足(?16|a00(a⊕b)|c00c|d00d|(b⊕1)00*)，且β0滿足(?16|016)的差分形式時，α2≠β2。

β0為(?16|016)時，解密方向經(jīng)過連續(xù)兩輪輪函數(shù)后的差分形式ΔF2(β0)為(?0)16，因此β2=ΔF2(β0)⊕β0的最低比特一定為0。差分傳播過程如圖3（b）所示。所以只需證明α2=ΔF2(α0)⊕α0的最低比特一定為1，即可證得定理。

圖3 兩輪輪函數(shù)的差分傳播Fig.3 Differential propagation of 2-round round function

對于加密方向連續(xù)兩輪差分傳播，α0中的(c00c|d00d)部分對應S2和S1的輸入差分。由性質(zhì)1 可知，S2和S1輸出差分均為***0，因此輸入差分的中間兩比特為0。

下面根據(jù)b的取值進行討論：

1）當b為 0 時，則差分α0的形式為(?16|a00a|c00c|d00d|100*)。對照圖3（a）可知，a00a為S3的輸入差分。由性質(zhì)1 可知，S3輸出差分的最低比特一定為0，因此輸入差分最高比特一定為0。100*為S0的輸入差分，有以下兩種情形：

2）當b為 1 時，則差分α0的形式為(?16|a00(a⊕1) |c00c|d00d|000*)。同上分析，考慮a00(a⊕1)為S3的輸入差分，由性質(zhì)1 及P 置換可得的輸入差分最高比特一定為1。000*為S0的輸入差分，當000*為0000 時，的輸入差分為1000，輸出差分為***1，因此α2=ΔF2(α0)⊕α0最低比特為1；當000*為0001 時的輸入差分為1001，輸出差分為***0，也能滿足α2=ΔF2(α0)⊕α0最低比特為1。證畢。

文獻［20］中構造的不可能差分區(qū)分器是本文不可能差分區(qū)分器的特例，對應a=b=c=d=0 的情形。當a，b，c，d取不同值時，對應不同的7 輪不可能差分區(qū)分器，具體來說，定理1 實際包含16 個不同的不可能差分區(qū)分器。

引理1 在PFP 算法中，當輸入差分為(α0，032)，輸出差分為 (032，β0)，并且α0滿足 (?16|016)，β0滿足(?16|a00(a⊕b)|c00c|d00d|(b⊕1)00*)的形式時，則(α0，032) →(032，β0)是PFP 算法的7 輪不可能差分區(qū)分器。各標記與符號的含義同定理1。

證 明α2=ΔF2(α0)⊕α0，β2=ΔF2(β0)⊕β0，當α2≠β2時，(α0，032) →(032，β0)一定是PFP 算法的7 輪不可能差分；當交換α0和β0時，α2和β2也同時交換，由定理1 可知結(jié)論成立。證畢。

3 PFP算法改進的9輪不可能差分分析

在本文構造的7 輪不可能差分區(qū)分器前后各加1 輪，可對9 輪PFP 算法進行分析。

選用引理1 中的區(qū)分器，并取b，c，d=0，即α0滿足(?16|016)，β0滿足(?16|a00a|08|100*)。與文獻［20］中的區(qū)分器相比，這個不可能差分區(qū)分器的形式更豐富（a可取0 或1），分析過程中可涉及更多輪密鑰。9 輪不可能差分分析如圖4 所示，可以恢復K8的24 b 和K0的16 b（共40 b）密鑰信息。詳細分析過程如算法1 所示。

圖4 PFP算法的9輪不可能差分分析Fig.4 9-round impossible differential cryptanalysis of PFP

算法1 9 輪PFP 算法不可能差分分析。

步驟1 選取2n個明文結(jié)構，對于每個明文結(jié)構中任意選擇的明文P，都有P'使下式成立：

可知每個結(jié)構能夠提供216+16=232個明文和232×232/2=263組明文對，2n個此類結(jié)構總共能夠提供2n+32個明文，2n+63組明文對。對所有的明文進行9 輪加密，選取密文差分滿足以下形式的明文對：

在上述密文差分中共23 b 差分為確定值（兩個比特a值相同），所以滿足上述密文差分形式的概率為2-23。因此，可得滿足要求的明密對數(shù)目約為：2n+63× 2-23=2n+40。

步驟2 對于滿足要求的明密對，猜測輪密鑰K8中的高20 比特及最低4 比特密鑰：K8，31，K8，30，…，K8，12和K8，3，K8，2，…，K8，0使它對應的6 個S盒差分方程成立。經(jīng)過該步驟后，剩余明密對的數(shù)目約為2n+40×(2-4)6=2n+16。

步驟3 對于剩余的明密對，猜測輪密鑰K0的高16 比特，即K0，31，K0，30，…，K0，16。這16b 的密鑰共涉及4個S盒差分方程，平均意義下它們同時成立的概率為2-4×4=2-16。注意到中間的7 輪差分不可能差分，滿足它輸入輸出差分形式的猜測密鑰（共24+16=40 b）必定是錯誤的，剔除該候選密鑰，跳轉(zhuǎn)至步驟4。

在分析完步驟2 剩余的2n+16組明密對后，錯誤密鑰仍被保留下來的數(shù)目為：

步驟4 如果猜測的40 b 密鑰K8，31，K8，30，…，K8，12、K8，3，K8，2，…，K8，0及K0，31，K0，30，…，K0，16仍有多個候選值，跳至步驟2 繼續(xù)篩選；如果可以唯一確定，算法結(jié)束。

復雜度分析 當n=5 時，式（2）結(jié)果小于1，此時可將錯誤密鑰全部淘汰，唯一確定正確密鑰；數(shù)據(jù)復雜度為2n+32=237個選擇明文，時間復雜度主要由步驟2、3 提供。PFP 算法1 輪加密或解密（加解密相同）共涉及8 個S 盒，在步驟2 解密過程中涉及6 個S 盒，因此這一步時間復雜度為2 ×224× 2n+40× 6/8 ≈269次1 輪解密；在步驟3 加密過程中涉及4 個S 盒，這一步時間復雜度為2 × 240× 2n+16× 4/8 ≈2n+56=261次1 輪加密；總的時間復雜度為269+261≈269次1輪加密，即269× 1/9 ≈266次9 輪PFP 算法加密。

4 PFP算法的10輪不可能差分分析

選用合適的7 輪不可能差分區(qū)分器，在它的前面加1 輪，后面加2 輪，可對10 輪PFP 算法進行分析。本章選用定理1中的區(qū)分器，并取a=b=c=d=0，即α0滿 足(?16| 012|100?)，β0滿足(?16|016)的形式。實際上，此區(qū)分器與文獻［20］中進行9 輪分析時所用區(qū)分器相同，基于同一區(qū)分器進行10 輪不可能差分分析，如圖5 所示。

圖5 PFP算法的10輪不可能差分分析Fig.5 10-round impossible differential cryptanalysis of PFP

詳細分析過程如算法2 所示。此分析可恢復52 b 密鑰信息，包括K9中的16 b、K8中的16 b 以及K0中的20 b。

算法2 10 輪PFP 算法不可能差分分析。

步驟1 選取2n個明文結(jié)構，對于每個明文結(jié)構中任意選擇的明文P，都有P'滿足：

每個明文結(jié)構能夠提供2(20+17)=237個明文和237×237/2=273組明文對，則2n個結(jié)構共能提供2n+37個明文，2n+73組明文對。對這些明文進行10 輪加密后，選擇密文差分滿足以下形式的密文對

在上述密文差分中共24 b 差分為確定值，故滿足上述密文差分形式的概率為2-24。因此，滿足要求的明密對數(shù)目約為：2n+73× 2-24=2n+49。

步驟2 對于滿足要求的明密對，猜測輪密鑰K9中的16比特密鑰 ：K9，31，K9，30，…，K9，28；K9，23，K9，22，…，K9，20；K9，15，K9，14，…，K9，12；K9，7，K9，6，…，K9，4，使對應的4個S盒差分方程成立。經(jīng)過該步驟后，剩余明密對的數(shù)目約為2n+49×2-16=2n+33。

步驟3 對于經(jīng)過上述步驟后的剩余明密對，猜測K8的高16比特，即K8，31，K8，30，…，K8，16。經(jīng)過該步驟后，剩余明密對的數(shù)目約為2n+33× 2-16=2n+17。

步驟4 對于剩余的明密對，繼續(xù)猜測K0的高16 比特及最 低4 比特，即K0，31，K0，30，…，K0，16和K0，3，K0，2，…，K0，0。這20 b 的密鑰共涉及5 個S 盒差分方程，平均意義下它們同時成立的概率為2-4×5=2-20。當猜測的16+16+20=52 b 候選密鑰滿足不可能差分區(qū)分器的輸入輸出差分時，則剔除該候選密鑰，跳轉(zhuǎn)至步驟5。

在分析了剩余的約2n+17組明密對后，錯誤密鑰仍然能夠保留下來的數(shù)目為：

步驟5 如果猜測的52 b 密鑰（K9，31，K9，30，…，K9，28；K9，23，K9，22，…，K9，20；K9，15，K9，14，…，K9，12；K9，7，K9，6，…，K9，4；K8，31，K8，30，…，K8，16及K0，31，K0，30，…，K0，16和K0，3，K0，2，…，K0，0）仍有多個候選值，跳至步驟2 繼續(xù)篩選；如果可唯一確定，算法結(jié)束。

復雜度分析 當n=9 時，式（3）的結(jié)果小于1。所有的錯誤密鑰被淘汰，剩下唯一的正確密鑰，數(shù)據(jù)復雜度為2n+37=246個選擇明文；時間復雜度主要由步驟2～4 提供。在步驟2 解密過程中涉及4 個S 盒，時間復雜度約為2 × 216×2n+49× 4/8=2n+65=274次1 輪解密；步驟3 解密過程中涉及4 個S 盒，時間復雜度約為2 × 232× 2n+33× 4/8=2n+65=274次1 輪解密；步驟4 加密過程中涉及5 個S 盒，時間復雜度約為2 × 252× 2n+17× 5/8 ≈2n+69=278次1 輪加密；故總的時間復雜度約為(278+274+274) × 1/10 ≈275次10 輪加密。

5 結(jié)果對比

本文充分利用輪函數(shù)的具體細節(jié)，特別是利用S 盒的差分分布及P 置換的信息，給出了一類7 輪不可能差分區(qū)分器的一般形式。使用新的不可能差分區(qū)分器改進了9 輪PFP算法的不可能差分分析，可恢復40 b 密鑰信息，分析的數(shù)據(jù)復雜度為237個選擇明文，時間復雜度為266次9 輪算法加密。進一步，給出了10 輪PFP 算法的不可能差分分析，可恢復52 b 密鑰信息。本文結(jié)果與文獻［8，20］中的研究比較如表4所示。從表4 中可以看出，本文構造的區(qū)分器形式更豐富，對9 輪PFP 算法分析可恢復更多的密鑰比特，且將不可能差分分析輪數(shù)擴展到10 輪。

表4 PFP算法不可能差分分析對比Tab.4 Comparison of impossible differential cryptanalysis of PFP

6 結(jié)語

目前，無論是區(qū)分器形式，還是分析輪數(shù)及可恢復密鑰比特數(shù)，本文結(jié)果均優(yōu)于已有結(jié)果。后續(xù)將考慮在復雜度方面繼續(xù)優(yōu)化，將本文構造不可能差分區(qū)分器的方法應用于其他輕量級分組密碼算法，尤其是整體采用Feistel 結(jié)構、輪函數(shù)為SP 結(jié)構的密碼算法的安全性分析。