對PICO算法基于可分性的積分攻擊

劉宗甫，袁 征，趙晨曦，朱 亮

（1.北京電子科技學院密碼科學與技術系，北京 100070；2.西安電子科技大學通信工程學院，西安 710071）

（*通信作者電子郵箱zyuan@tsinghua.edu.cn）

0 引言

輕量級分組密碼以實現效率高、加密速度快、軟硬件占用資源少而成為最近幾年密碼領域的研究熱點，在計算能力有限，資源受限的環境下被廣泛地應用，其中近些年的輕量級分組密碼有GIFT［1］、Midori［2］、LED［3］、SKINNY［4］等。因此，對分組密碼的安全性分析成為了密碼學研究的重要方向之一。

積分分析在2002 年FSE（Fast Software Encryption）會議上被提出，作為與差分分析相對應的一種分析方法，它對某些結構和算法的分析有時比差分和線性分析更有效。積分分析結合了Square 攻擊［5］、Multiset攻擊［6］和Saturation 攻擊［7］的思想，主要是考慮特定輸入對應密文某些位置的零和性質，早期主要局限于以字節為單位的密碼算法。2008 年的FSE 會議上，Z’aba 等［8］提出了基于比特模式的積分攻擊。2015 年歐洲密碼會議上，Todo［9］提出了可分性的概念，來描述介于“活躍”和“零和”之間的隱含性質。在之后的美洲密碼會議上，Todo 提出將可分性與S 盒的代數標準型進行結合，可分性將發揮更大的優勢。基于這一猜想，Todo 首次給出了MISTY1 算法［10］的全輪破解。比特級可分性質作為可分性的一種特殊情況，可以對算法結構在比特級進行更加精準的刻畫。可分性質剛提出來時，由于復雜度的限制，無法在大分組、長輪數算法中應用。為了解決這一問題，2016 年亞洲密碼會議上，Xing等［11］把追蹤可分性的問題轉化為基于混合整數線性規劃的問題，調用已有的求解器進行基于比特級可分性的自動化搜索，基于混合整數線性規劃（Mixed-Integer Linear Programming，MILP）的方法在一定程度上解決復雜度的問題。隨后，該方法在積分分析方面得到了廣泛應用［12-14］，并取得了顯著成效。

對于PICO 算法，馬楚焱等［15-16］利用MILP 方法構造了7輪多維零相關線性區分器，并對10 輪PICO 算法進行密鑰恢復攻擊，但目前為止尚沒有該算法在積分分析下的安全性評估結果。本文采用MILP 搜索工具對PICO 算法進行積分區分器的搜索，搜索得到了輪數最長的10 輪積分區分器，但由于輸入活躍比特數太多，可利用的明文數太少，不利于密鑰恢復。本文選擇搜索到的9 輪積分區分器向后攻擊兩輪，對PICO 算法進行11 輪的積分攻擊。根據現有研究，這是目前為止首次評估PICO 算法在積分攻擊方面的安全性。同時，近年來對于密碼分析方法之間聯系的研究也得到了越來越多的關注，Bogdanov 等［17］研究了零相關線性分析和積分分析之間的聯系，并從理論上證明了零相關線性區分器可以和積分區分器相互轉化。

1 PICO算法

1.1 PICO算法加密過程

PICO 算法是2016 年Bansod 等［18］設計的混淆擴散網絡（Substitution Permutation Network，SPN）結構的超輕量級分組密碼，它采用64 比特明文，128 比特主密鑰，共迭代32 輪，在每一輪輪函數中將64比特明文和64比特輪密鑰逐位異或，然后進行列替換和比特置換操作，具體結構如圖1 所示。算法的64 比特明文被排列成4 行16 列的二維數組形式，具體形式可以用矩陣P來表示，其中第i行第j列的元素記為pi，j。

圖1 PICO算法結構Fig.1 Structure of PICO

PICO算法的每一輪包含以下3個步驟：密鑰加、列替換和置換層，在最后一輪僅有輪密鑰加。

1）密鑰加：64 比特中間狀態矩陣P和64 比特輪密鑰的對應位置進行異或操作。

P→P⊕Ki

2）列替換：對狀態矩陣的每一列進行S 盒操作，當一個S盒的列輸入為C(i)=p3，i||p2，i||p1，i||p0，i時，經過S 盒的輸出為S(C(i))=q3，i||q2，i||q1，i||q0，i，其中0 ≤i≤15。PICO 算法S 盒如表1所示。

表1 PICO的S盒Tab.1 S-box of PICO

PICO 算法的非線性層由16 個相同的S 盒并置而成，當S盒的輸入為x=(x3，x2，x1，x0)，輸出為y=(y3，y2，y1，y0)時，S盒的代數表達式為：

3）置換層：PICO算法通過64比特置換表將狀態矩陣的第i行第j列的元素pi，j移動到表2 中對應的位置上，例如BP(p0，0)→p0，10，其中置換表如表2所示。

表2 PICO的P盒Tab.2 P-box of PICO

1.2 PICO算法的密鑰擴展方案

PICO 的密鑰規模為128 比特，密鑰擴展的設計與SPECK算法類似，主密鑰Key=k127k126…k1k0存儲在密鑰寄存器中，首先提取子密鑰K0和L1，擴展算法可以表示為：

在得到K0和L1后，子密鑰K1到K32的生成過程如下：

其中j從0 到31 遍歷。重復Step1～Step3，便得到了32 輪的全部輪密鑰。

2 基于比特可分性質的MILP建模

2.1 基于比特的可分性質

比特乘積函數πu(x)和πU(X)：對于任意，πu(x)是滿足u[i]=1的所有x[i]的與，定義為：

令πU(X)是一個到F2的函數，對于任意的，關于輸入的比特乘積函數πU(X)為：

定義1可分性［9］。記X為空間上的多重集，如果集合X滿足下面的條件稱X具有可分性：

其中：k表示一個m維向量；K表示m維向量集合（第i個元素取0 到li之間的值）。進一步，當考慮比特可分性時，l0，l1，…，lm-1全被限制為1，可分性質可表示為。

定義2可分路徑［11］。令輸入多重集滿足可分性，通過i輪加密后，其中間狀態滿足可分性，那么可分性質的傳遞路徑為：

{k}?K0→K1→…→Kr

對于任意的向量ki∈Ki(i≥1)，必定存在向量ki-1∈Ki-1使得ki-1能夠傳遞到ki，其中i∈{0，1，…，r}，則存在一條r輪的可分路徑(k0，k1，…，kr)。

2.2 比特可分性的MILP模型

基于MILP 搜索比特可分性的核心思想在于將可分性的傳遞規則轉化為一系列線性不等式，通過構建目標函數將積分區分器搜索問題轉化為MILP 求解問題。下面通過線性不等式對三種基本運算（復制、異或、與）和S盒模型進行描述。

1）模型1（復制）。假設用(a) →(b0，b1)來表示復制操作的一條可分路徑，下面的等式能夠有效地描述可分性的傳遞規則：

2）模型2（異或）。假設用(a0，a1) →(b)來表示異或操作的一條可分路徑，下面的等式能夠有效地描述可分性的傳遞規則：

3）模型3（與）。假設用(a0，a1) →b來表示與操作的一條可分路徑，下面的不等式能夠有效地描述可分性的傳遞規則：

4）S盒模型。為了得到S盒的線性不等式組，首先利用文獻［11］提到的算法2 得到一個可分路徑的完整列表，接下來調用SageMath 軟件生成刻畫S盒的線性不等式集合。通常這個不等式集合規模很大，直接調用Gurobi求解器會使得MILP問題在計算上不可解。為了能夠降低計算的復雜度，Sun等［19］提出了貪婪算法（文獻［19］中的算法1），調用該算法對S盒的線性不等式集合進行化簡，能夠顯著地降低了S 盒不等式的數量。

對于基于復制、異或、與這三種基本操作和S 盒的算法，能夠構建線性不等式集合來刻畫一輪可分性的傳遞規律。把這種過程迭代r次，將得到一個線性不等式系統來描述r輪可分性質，該系統的所有可行解對應所有r輪可分路徑。

初始條件和終止規則：

通過設置限制條件L和目標函數Obj便得到了一個完整的MILP 模型，令表示i輪加密后的輸出可分性質，當Kr+1首次包含所有n個單位向量，可分性質停止傳遞，由搜索得到一個r輪的積分區分器。

3 PICO算法的建模過程

3.1 比特可分性的MILP模型

PICO 算法采用SPN 結構，輪密鑰加操作并不影響可分性質的傳遞，因此不將其考量在本文的分析當中。首先應用S盒傳遞規則，計算得到通過每個S 盒的49 條可分路徑，如表3所示。

表3 PICO S盒的可分路徑Tab.3 Division paths of PICO S-box

其中(a3，a2，a1，a0) →(b3，b2，b1，b0)表示一條可分路徑，這49 條可分路徑形成了一個點集，并將點集輸入到SageMath軟件中的inequality_generator（）函數中，將返回52個線性不等式集合，再利用貪婪算法化簡得到約束每個S 盒的15 個線性不等式組L，表示如下：

因此PICO 算法的非線性層可用15× 16=240 個線性不等式表示。

PICO算法的線性層通過64比特置換表進行比特移位，因此只需在下一輪可分性質傳遞過程中改變向量系數的位置。有了描述S 層和線性層的不等式組，便得到了一輪PICO 算法可分性傳遞的不等式組。迭代r輪之后，便可構造r輪具有可分性路徑的線性不等式組，將其作為MILP 模型的限制條件。只要給定初始可分性，便可求解該MILP模型是否存在積分區分器。

3.2 PICO算法的積分區分器

本節根據3.1 節建立的PICO 算法的MILP 模型，采用python 編程建模求解，首次給出了PICO 算法的兩個積分區分器。首先根據活躍比特數越多、搜索輪數越長的性質，設定活躍比特數為63，通過大量實驗搜索得到PICO 算法11 個10 輪積分區分器，這也是目前為止PICO 算法已知最長的積分區分器。但有些區分器平衡比特數太少，區分優勢不明顯，通過篩選給出了PICO 算法輸入63 個活躍比特、輸出26 個比特平衡的10 輪積分區分器。假設a 表示活躍，b 表示平衡，c 表示常數，“？”表示未知，目前搜索到PICO 算法最長的10 輪積分區分器輸入狀態可表示為：

aaaa，aaaa，aaaa，aaaa，aaaa，aaaa，aaaa，aaaa

acaa，aaaa，aaaa，aaaa，aaaa，aaaa，aaaa，aaaa

輸出可表示為：

？？？？，b？？？，b？b？，b？b？，b？b？，b？b？，b？？？，b？？？

b？b？，b？b？，？？b？，？？？？，b？b？，b？b？，bbb？，bbb？

但由于10 輪積分區分器輸入活躍比特數較多，最多可利用2 組明文，不利于密鑰恢復；同時，活躍比特數越多，意味著數據復雜度越大。因此，通過將對應于S盒的連續4位設置為常數值，其余位置設置為活躍，遍歷所有的情況，再次搜索得到PICO 算法13個9輪積分區分器。根據平衡比特數越多，區分優勢越明顯的性質。本文選擇如下的9 輪積分區分器，輸入60 個活躍比特，輸出33 個平衡比特，并根據此區分器對PICO 算法進行11 輪積分攻擊。9 輪積分區分器輸入狀態可表示為：

aaaa，aaaa，aaaa，aaaa，aaaa，aaaa，aaaa，cccc

aaaa，aaaa，aaaa，aaaa，aaaa，aaaa，aaaa，aaaa

輸出可表示為：

b？b？，b？？？，b？b？，b？？？，b？b？，b？b？，b？b？，b？b？

bbbb，b？b？，b？b？，b？b？，b？b？，b？b？，bbb？，b？b？

4 PICO算法的密鑰恢復攻擊

利用3.2 節給出的9 輪積分區分器，向后攻擊兩輪，對PICO 算法進行11 輪積分攻擊。首先，通過選取特定構造9 輪區分器所需要的明文，得到11 輪加密后的密文。然后，以平衡位置所在的列為單位進行篩選。每一次篩選中，需要猜測第11 輪的輪密鑰RK11及第10 輪的輪密鑰RK10的部分密鑰信息，其中已猜測的部分密鑰信息在之后的篩選過程中默認已經唯一確定。最后，對密文進行解密恢復出第9 輪的結果，通過驗證第9 輪輸出的對應位置比特是否平衡來篩選出正確密鑰。

平衡位置的選擇不同時，對應篩選出RK11和RK10的密鑰字（4 比特）也不同。通過16 次篩選后，便可得到平衡位置與第11 輪的輪密鑰密鑰RK11及第10 輪輪密鑰RK10之間的關系，具體如表4所示。

表4 平衡位置與可篩選密鑰字的對應關系Tab.4 Relationship between balanced positions and nibbles of recovered round keys

本文選擇32、33、34、35 這四個平衡位置為例進行說明，攻擊流程如圖2 所示。圖2 內部結構與1.1 節給出PICO 算法的狀態矩陣相對應，該狀態矩陣的每一列都可以表示成一個向量，即可以表示成Q15、Q14、…、Q0共16 個向量，其中Qj=(p0，j，p1，j，p2，j，p3，j)T，0 ≤j≤15。下面給出攻擊的具體步驟：

Step1 根據輸入的初始狀態構造9 輪積分區分器，由于輸入狀態有4 比特為常數比特，因此將p0，8、p1，8、p2，8、p3，8對應位置取定為常數，其余60 個活躍位置遍歷{0，1}60，故每組包含260個明文，并對其進行11 輪加密，相應的密文記為C0、C1、…、。

Step2 通過猜測密鑰RK11的3 個密鑰字共12比特密鑰信息，對260個密文進行第11輪解密，計算得到第10 輪的12 比特輸出，其中計算表達式為，j∈{1，2，12}。

Step3 計算第10 輪通過S 盒后的中間狀態，即Ti=P-1(V(i))，猜測密鑰RK10的一個密鑰字，計算ti=。

Step5： 選擇另一組構造9 輪區分器時的明文，重復Step1～Step4，直到唯一確定。

復雜度分析：表4 利用區分器平衡位置由多到少依次對密鑰字進行篩選，即攻擊時共需要篩選16 次。RK11已確定的密鑰字在表4 中用粗體標注出來，在下次篩選時無需猜測已確定的密鑰字。為了唯一確定正確密鑰，即保證每一種情況下錯誤密鑰的期望值-N都小于1，因此需要選擇11 組明文進行分析。經過16 次篩選后，RK10的16 個子密鑰和RK11的16個子密鑰共128 比特密鑰信息將唯一確定。從而攻擊的數據復雜度為11 組(260× 11 ≈263.46)明文，低于明文直接窮舉量。每次篩選過程中猜測密鑰字的個數不同，其中需猜測5 個密鑰字的1 次、4 個密鑰字的3 次、2 個密鑰字的3 次、1 個密鑰字的9 次，所以處理11 組明文整個攻擊的時間復雜度共約需263.46×(24×5+3× 24×4+3× 24×2+9 × 24×1)≈283.46次S 盒查表，這相當于283.46/(11× 16) ≈276次11輪加密。此外，為了對猜測的密鑰字進行存儲，存儲復雜度為24×5+3× 24×4+3× 24×2+9 × 24×1≈220。

圖2 11輪PICO的積分攻擊Fig.2 Integral attack on 11-round PICO

下面將本文積分攻擊與零相關線性分析方法進行比較，結果如表5所示。

表5 本文方法與零相關攻擊方法的實驗結果對比Tab.5 Experimental results comparison of proposed method and zero correlation attack method

5 結語

PICO 算法能夠很好地抵抗差分攻擊［20］、線性攻擊［21］、biclique 攻擊［22］、零相關攻擊［23］和相關密鑰攻擊［24］，但迄今為止未有人對PICO 算法抵抗積分攻擊的能力進行研究。本文主要采用基于比特可分性的MILP 建模方法對PICO 算法進行積分分析，得到了輪數最長的10 輪積分區分器，但由于活躍比特數太多，可利用的明文數太少，不利于密鑰恢復。本文選擇搜索到的9 輪積分區分器進行11 輪的積分攻擊，該攻擊經過16 次的篩選能夠恢復PICO 算法128 比特密鑰信息。其中攻擊數據復雜度為263.46，時間復雜度為276次11 輪加密，存儲復雜度為220，本文首次給出攻擊11 輪PICO 算法的數據復雜度小于窮舉攻擊的有效攻擊。分析結果表明了11 輪PICO 算法不能抵抗積分攻擊，但由于在搜索中活躍比特數越多，搜索得到的積分區分器越長，因此使得選擇明文的數據量大大增加，如何能夠平衡活躍比特數和長輪數之間的關系將是進一步需要解決的問題；同時MILP搜索積分區分器的方法還有一定的局限性，采用文獻［11］方法產生的不等式不足以約束大規模的S盒，如8 進8出的S 盒，解決S 盒算法的適應性問題也將是下一步研究的主要方向。