對(duì)PICO算法基于可分性的積分攻擊

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

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

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

0 引言

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

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

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

1 PICO算法

1.1 PICO算法加密過程

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

圖1 PICO算法結(jié)構(gòu)Fig.1 Structure of PICO

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

1）密鑰加：64 比特中間狀態(tài)矩陣P和64 比特輪密鑰的對(duì)應(yīng)位置進(jìn)行異或操作。

P→P⊕Ki

2）列替換：對(duì)狀態(tài)矩陣的每一列進(jìn)行S 盒操作，當(dāng)一個(gè)S盒的列輸入為C(i)=p3，i||p2，i||p1，i||p0，i時(shí)，經(jīng)過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 個(gè)相同的S 盒并置而成，當(dāng)S盒的輸入為x=(x3，x2，x1，x0)，輸出為y=(y3，y2，y1，y0)時(shí)，S盒的代數(shù)表達(dá)式為：

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

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

1.2 PICO算法的密鑰擴(kuò)展方案

PICO 的密鑰規(guī)模為128 比特，密鑰擴(kuò)展的設(shè)計(jì)與SPECK算法類似，主密鑰Key=k127k126…k1k0存儲(chǔ)在密鑰寄存器中，首先提取子密鑰K0和L1，擴(kuò)展算法可以表示為：

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

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

2 基于比特可分性質(zhì)的MILP建模

2.1 基于比特的可分性質(zhì)

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

令πU(X)是一個(gè)到F2的函數(shù)，對(duì)于任意的，關(guān)于輸入的比特乘積函數(shù)πU(X)為：

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

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

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

{k}?K0→K1→…→Kr

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

2.2 比特可分性的MILP模型

基于MILP 搜索比特可分性的核心思想在于將可分性的傳遞規(guī)則轉(zhuǎn)化為一系列線性不等式，通過構(gòu)建目標(biāo)函數(shù)將積分區(qū)分器搜索問題轉(zhuǎn)化為MILP 求解問題。下面通過線性不等式對(duì)三種基本運(yùn)算（復(fù)制、異或、與）和S盒模型進(jìn)行描述。

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

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

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

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

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

初始條件和終止規(guī)則：

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

3 PICO算法的建模過程

3.1 比特可分性的MILP模型

PICO 算法采用SPN 結(jié)構(gòu)，輪密鑰加操作并不影響可分性質(zhì)的傳遞，因此不將其考量在本文的分析當(dāng)中。首先應(yīng)用S盒傳遞規(guī)則，計(jì)算得到通過每個(gè)S 盒的49 條可分路徑，如表3所示。

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

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

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

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

3.2 PICO算法的積分區(qū)分器

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

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 輪積分區(qū)分器輸入活躍比特?cái)?shù)較多，最多可利用2 組明文，不利于密鑰恢復(fù)；同時(shí)，活躍比特?cái)?shù)越多，意味著數(shù)據(jù)復(fù)雜度越大。因此，通過將對(duì)應(yīng)于S盒的連續(xù)4位設(shè)置為常數(shù)值，其余位置設(shè)置為活躍，遍歷所有的情況，再次搜索得到PICO 算法13個(gè)9輪積分區(qū)分器。根據(jù)平衡比特?cái)?shù)越多，區(qū)分優(yōu)勢(shì)越明顯的性質(zhì)。本文選擇如下的9 輪積分區(qū)分器，輸入60 個(gè)活躍比特，輸出33 個(gè)平衡比特，并根據(jù)此區(qū)分器對(duì)PICO 算法進(jìn)行11 輪積分攻擊。9 輪積分區(qū)分器輸入狀態(tài)可表示為：

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算法的密鑰恢復(fù)攻擊

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

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

表4 平衡位置與可篩選密鑰字的對(duì)應(yīng)關(guān)系Tab.4 Relationship between balanced positions and nibbles of recovered round keys

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

Step1 根據(jù)輸入的初始狀態(tài)構(gòu)造9 輪積分區(qū)分器，由于輸入狀態(tài)有4 比特為常數(shù)比特，因此將p0，8、p1，8、p2，8、p3，8對(duì)應(yīng)位置取定為常數(shù)，其余60 個(gè)活躍位置遍歷{0，1}60，故每組包含260個(gè)明文，并對(duì)其進(jìn)行11 輪加密，相應(yīng)的密文記為C0、C1、…、。

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

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

Step5： 選擇另一組構(gòu)造9 輪區(qū)分器時(shí)的明文，重復(fù)Step1～Step4，直到唯一確定。

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

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

下面將本文積分攻擊與零相關(guān)線性分析方法進(jìn)行比較，結(jié)果如表5所示。

表5 本文方法與零相關(guān)攻擊方法的實(shí)驗(yàn)結(jié)果對(duì)比Tab.5 Experimental results comparison of proposed method and zero correlation attack method

5 結(jié)語

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