李曉丹 吳文玲 張 麗

1(中國(guó)科學(xué)院軟件研究所可信計(jì)算與信息保障實(shí)驗(yàn)室 北京 100190) 2(中國(guó)科學(xué)院大學(xué) 北京 100049) 3(中國(guó)星網(wǎng)網(wǎng)絡(luò)系統(tǒng)研究院有限公司 北京 100083)

在分組密碼的設(shè)計(jì)和分析中，整體結(jié)構(gòu)是首要的研究對(duì)象.作為分組密碼的重要特征，整體結(jié)構(gòu)對(duì)于分組密碼的輪數(shù)選取、軟硬件實(shí)現(xiàn)性能都有非常大的影響.常用的分組密碼整體結(jié)構(gòu)有：Feistel結(jié)構(gòu)、SP結(jié)構(gòu)、廣義Feistel結(jié)構(gòu)、MISTY結(jié)構(gòu)、Lai-Massey結(jié)構(gòu)以及由上述結(jié)構(gòu)彼此嵌套形成的細(xì)化整體結(jié)構(gòu).其中，SP結(jié)構(gòu)非常清晰，是直接基于香農(nóng)的“混淆”和“擴(kuò)散”原則實(shí)現(xiàn)的整體結(jié)構(gòu)，通常包含一個(gè)可逆的非線性函數(shù)S和一個(gè)可逆線性變換P，其中S層起混淆作用，線性層P起擴(kuò)散作用.當(dāng)給定S層和P層的某些密碼指標(biāo)，設(shè)計(jì)者可給出SP密碼抵抗差分分析和線性分析的可證明安全.相較于Feistel結(jié)構(gòu)，SP結(jié)構(gòu)擴(kuò)散速度更快，但是為達(dá)到加密和解密的相似性需要合理設(shè)計(jì)密碼部件.SP結(jié)構(gòu)的分組密碼算法有：AES[1],ARIA[2]和Serpent等.其中AES無(wú)疑是目前最重要的分組密碼，它的擴(kuò)散層由2部分組成，也被稱為兩級(jí)擴(kuò)散層，一部分是選取分支數(shù)最大的MDS矩陣作為列混淆，另一部分是行移位操作.特別地，許多分組密碼和雜湊函數(shù)的設(shè)計(jì)都是從AES的初始設(shè)計(jì)結(jié)構(gòu)開始，對(duì)一個(gè)或多個(gè)部件進(jìn)行調(diào)整以滿足其設(shè)計(jì)要求，如Anubis[3]，LED[4]，Midori[5]，PHOTON[6]，QARMA[7]，SKINNY[8]和Whirlpool[9].此類算法的線性層本身由2部分組成:一部分類似于AES的列混合操作，另一部分類似于AES行移位操作，我們稱這類密碼算法為類AES密碼算法.列混合操作是對(duì)狀態(tài)列的矩陣乘法，行移位操作是對(duì)狀態(tài)字的置換.對(duì)于前者，研究結(jié)果較多，只需要保證其具有高的分支數(shù)，分支數(shù)越高，對(duì)應(yīng)的活躍S盒數(shù)越多，則抵抗差分分析和線性分析的能力越強(qiáng).AES選取的列混合操作為分支數(shù)最大的MDS矩陣，而出于輕量化考慮的一些算法，如Midori，SKINNY等，則采用非最優(yōu)分支數(shù)的二元矩陣.而對(duì)于字換位操作，當(dāng)僅考慮超過2輪的情形時(shí)，字換位的選取極大影響活躍S盒的數(shù)量，因此，對(duì)于好的設(shè)計(jì)來說，精心選擇字換位操作至關(guān)重要.對(duì)于AES，得益于寬軌跡設(shè)計(jì)策略[10]，可以獲得數(shù)學(xué)上可證明的最小活躍S盒數(shù)的界限，保證4輪后至少有25個(gè)活躍S盒.Midori算法設(shè)計(jì)的初衷是減少硬件資源損耗，它采用類似于AES算法的結(jié)構(gòu)，與SKINNY算法類似，它們都屬于類AES算法，但是在列混淆部分選用非最優(yōu)分支數(shù)的矩陣.Midori設(shè)計(jì)者發(fā)現(xiàn)使用分支數(shù)為4的二元矩陣時(shí)，4輪后活躍S盒數(shù)下降到16個(gè)，但改變字換位操作可顯著提高活躍S盒數(shù).2015年，文獻(xiàn)[11]證明了對(duì)于選用最優(yōu)分支數(shù)的列混合操作的算法，用任意置換替換字換位操作不能增加活躍S盒的數(shù)量.2016年，文獻(xiàn)[12]給出，用B表示矩陣的分支數(shù)，對(duì)于經(jīng)典字換位操作，則對(duì)于列混合為MDS矩陣的，4輪后至少有B2個(gè)活躍S盒；對(duì)于列混合為二元矩陣的，4輪后活躍S盒的下界可能大于B2，且對(duì)于某些二元矩陣，下界可達(dá)到B(B+2).2018年，文獻(xiàn)[13]提出一種加速搜索字換位操作的技術(shù)，并應(yīng)用于Midori和SKINNY算法，尋找使得整體擴(kuò)散性更好的字換位操作.這也是現(xiàn)在輕量級(jí)分組密碼的一個(gè)設(shè)計(jì)趨勢(shì)，擴(kuò)散層選擇非MDS矩陣，雖然擴(kuò)散效果沒有MDS矩陣好，但是實(shí)現(xiàn)效率會(huì)有很大提高,這在資源受限的環(huán)境下有很大優(yōu)勢(shì)，而且在結(jié)合合適的向量置換操作后，整體算法也可以達(dá)到較好的擴(kuò)散性和安全性.因此，使用類AES結(jié)構(gòu)來設(shè)計(jì)輕量級(jí)分組密碼是一個(gè)不錯(cuò)的選擇，特別是列混合操作選用最優(yōu)二元擴(kuò)散層,并結(jié)合恰當(dāng)?shù)南蛄恐脫Q，可以很好地平衡安全性和實(shí)現(xiàn)代價(jià)，然而在選定列混合操作后，搜索合適的向量置換并不容易，這也是這類算法在設(shè)計(jì)時(shí)需要花費(fèi)大量精力的部分.

uBlock算法[14]是全國(guó)密碼算法設(shè)計(jì)競(jìng)賽中的獲勝算法.該算法是經(jīng)典的SP結(jié)構(gòu)，是一種典型的類AES算法，線性層選用的是16維的最優(yōu)二元擴(kuò)散層與向量置換的組合，擴(kuò)散速度快且可以在各種軟硬件平臺(tái)上高速實(shí)現(xiàn).受文獻(xiàn)[13]的啟發(fā)，本文研究了uBlock類結(jié)構(gòu)的擴(kuò)散性，并給出了尋找最優(yōu)置換的搜索策略.通過對(duì)uBlock類結(jié)構(gòu)中二元擴(kuò)散層性質(zhì)的研究，我們給出uBlock類結(jié)構(gòu)全擴(kuò)散輪數(shù)的下界.根據(jù)結(jié)構(gòu)特點(diǎn)，我們揭示了uBlock類結(jié)構(gòu)等價(jià)類的劃分準(zhǔn)則，并基于此給出了uBlock類結(jié)構(gòu)最優(yōu)向量置換的搜索策略.最后根據(jù)128 b和256 b分組的uBlock類結(jié)構(gòu)的特點(diǎn)，進(jìn)一步優(yōu)化了搜索策略，并依據(jù)全擴(kuò)散輪數(shù)、性能和超級(jí)擴(kuò)散層的分支數(shù)3個(gè)指標(biāo)，給出了128 b和256 b分組的uBlock類結(jié)構(gòu)的一系列最優(yōu)向量置換.我們的方法可以大幅度降低需要測(cè)試的置換對(duì)，為后續(xù)uBlock類算法的設(shè)計(jì)提供技術(shù)支持.

1 基礎(chǔ)知識(shí)

本節(jié)介紹相關(guān)的基礎(chǔ)概念和定義.

1.1 符號(hào)表示

表1給出了本文中使用的符號(hào):

Table 1 Symbols

1.2 分支數(shù)

M的線性分支數(shù)定義為

分支數(shù)反映了密碼方案的擴(kuò)散性，此外也與差分分析和線性分析相關(guān).分支數(shù)達(dá)到最大的矩陣稱為MDS矩陣，分支數(shù)達(dá)到次優(yōu)的矩陣稱為Near-MDS矩陣.基于分支數(shù)，密碼方案的設(shè)計(jì)者和分析者可以估計(jì)活躍S盒的下界，從而評(píng)估算法抵抗差分分析和線性分析的能力.

1.3 uBlock算法描述

uBlock算法的整體結(jié)構(gòu)采用PX(Pshufb-Xor)結(jié)構(gòu)(SP結(jié)構(gòu)的一種細(xì)化結(jié)構(gòu))，Pshufb和Xor分別是向量置換和異或運(yùn)算指令.算法設(shè)計(jì)采用S盒和分支數(shù)的理念，對(duì)差分分析和線性分析具有可證明的安全性，同時(shí)對(duì)于不可能差分分析、積分分析、中間相遇攻擊等分析方法具有相對(duì)成熟的分析評(píng)估理論支持.此外，uBlock算法適應(yīng)各種軟硬件平臺(tái)，充分考慮了微處理器的計(jì)算資源,可以利用SSE,AVX2和NEON等指令集高效實(shí)現(xiàn)；硬件實(shí)現(xiàn)簡(jiǎn)單而有效,既可以高速實(shí)現(xiàn)，滿足高性能環(huán)境的應(yīng)用需求,也可以輕量化實(shí)現(xiàn),滿足資源受限環(huán)境的安全需求.

uBlock是一族分組密碼算法，分組長(zhǎng)度和密鑰長(zhǎng)度支持128 b和256 b，分別記為uBlock128/128,uBlock128/256和uBlock256/256，迭代輪數(shù)分別為16,24和24.加密算法由輪迭代變換組成，輪變換如圖1所示:

圖1中，基本模塊為：

4 b的S盒如表2所示：

Table 2 The 4 bit S Box of uBlock Algorithm

Table 3 PLn and PRn

比如PL128表示為

PL128:({0,1}8)8→({0,1}8)8

(y0,y1,…,y7)→(z0,z1,…,z7)

z0=y1,z1=y3,z2=y4,z3=y6,

z4=y0,z5=y2,z6=y7,z7=y5.

2 uBlock類結(jié)構(gòu)

uBlock算法采用的整體結(jié)構(gòu)是PX結(jié)構(gòu)，其擴(kuò)散層由2部分組成：一部分是線性變換，即由Feistel結(jié)構(gòu)構(gòu)造的二元最優(yōu)擴(kuò)散層；另一部分是向量置換.在本節(jié)中，我們探索一類PX結(jié)構(gòu)的擴(kuò)散特性，即線性變換部分選取與uBlock算法相同的二元擴(kuò)散層，向量置換部分與uBlock算法不同的結(jié)構(gòu)，稱之為uBlock類結(jié)構(gòu)，形式如圖2所示：

此外，我們觀察到M16用矩陣形式表示出來，恰好為如下形式的分塊矩陣：

其中,

A=Circ(0,0,1,1,1,0,1,1),

B=Circ(1,1,0,1,0,1,1,1),

C=Circ(1,0,1,1,0,0,1,1).

由于

因此

其中Am,Bm,Cm指對(duì)角線元素分別為A,B,C，而其余元素為零矩陣的m×m分塊矩陣，即有

我們的目標(biāo)是探索uBlock類結(jié)構(gòu)的擴(kuò)散性，并尋找最優(yōu)的向量置換使得整體結(jié)構(gòu)的擴(kuò)散性和安全性達(dá)到最優(yōu)，即我們需要考慮的指標(biāo)有3個(gè)：

1)全擴(kuò)散輪數(shù).全擴(kuò)散輪數(shù)越小，算法的擴(kuò)散性越強(qiáng)，且可以根據(jù)全擴(kuò)散輪數(shù)大致估計(jì)算法抵抗不可能差分、積分分析等結(jié)構(gòu)性分析方法的能力.因此，我們旨在尋找可以達(dá)到最小全擴(kuò)散輪數(shù)的置換.

2)實(shí)現(xiàn)性能.盡可能減少軟件實(shí)現(xiàn)中的指令數(shù).

3)4輪超級(jí)S盒下的分支數(shù).我們可以根據(jù)分支數(shù)的概念給出算法活躍S盒的下界，并基于此估計(jì)其抵抗差分和線性分析的能力.因此，我們希望分支數(shù)越大越好.

2.1 全擴(kuò)散輪數(shù)

擴(kuò)散最初是由香農(nóng)在文獻(xiàn)[15]中定義的，意思是一個(gè)子塊的輸入影響全部子塊的輸出.文獻(xiàn)[16]證明了抵抗飽和攻擊和不可能差分攻擊的輪數(shù)與稱之為全擴(kuò)散輪數(shù)的概念相關(guān),用DR表示全擴(kuò)散輪數(shù).同時(shí)，證明了給定的結(jié)構(gòu)需要至少2DR+1輪來抵抗上述攻擊.因此，在設(shè)計(jì)分組密碼時(shí),全擴(kuò)散輪數(shù)是一個(gè)重要的參考指標(biāo).接下來,我們研究uBlock類結(jié)構(gòu)全擴(kuò)散輪數(shù)的下界,首先給出M16的擴(kuò)散性質(zhì)：

性質(zhì)1.輸入向量的漢明重量為1時(shí),經(jīng)過M16均可擴(kuò)散到11個(gè)位置.

性質(zhì)2.輸入向量的漢明重量為2時(shí)，有如下8種情形在經(jīng)過M16后可全擴(kuò)散：

(1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0),

(0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1),

(0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0),

(0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0),

(0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0),

(0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0),

(0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0),

(0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0).

性質(zhì)3.輸入向量的漢明重量為3時(shí),有400種輸入在經(jīng)過M16后可全擴(kuò)散,剩余160種輸入均可擴(kuò)散到15個(gè)位置.

性質(zhì)4.輸入向量的漢明重量為4時(shí),有1 740種輸入在經(jīng)過M16后可全擴(kuò)散,剩余80種輸入均可擴(kuò)散到15個(gè)位置.

性質(zhì)5.輸入向量的漢明重量為5時(shí),有4 352種輸入在經(jīng)過M16后可全擴(kuò)散,剩余16種輸入均可擴(kuò)散到15個(gè)位置.

性質(zhì)6.輸入向量的漢明重量大于5時(shí),經(jīng)過M16后均可全擴(kuò)散.

根據(jù)上述6個(gè)性質(zhì)可知,要使經(jīng)過M16后全擴(kuò)散,輸入向量的漢明重量至少為2.則對(duì)于uBlock類結(jié)構(gòu),假定輸入向量的漢明重量為1,則經(jīng)過1輪輪函數(shù)后可擴(kuò)散到11個(gè)位置,這11個(gè)位置經(jīng)過2輪至多可擴(kuò)散到16×5+11=91個(gè)位置,經(jīng)過3輪至多可擴(kuò)散到45×16+11=731個(gè)位置.因此,我們可以給出一系列uBlock類結(jié)構(gòu)的全擴(kuò)散輪數(shù)下界,如表4所示.表4顯示了uBlock類結(jié)構(gòu)具有極強(qiáng)的擴(kuò)散性.

Table 4 Lower Bound of Full Diffusion Round for uBlock-like Structures

2.2 超級(jí)S盒

為了進(jìn)一步估計(jì)算法抵抗差分和線性分析的能力，我們引入超級(jí)S盒的概念.uBlock類結(jié)構(gòu)連續(xù)4輪輪函數(shù)作用在中間狀態(tài)X上可以表示為

P°T2°M°T1°S°P°T2°M°T1°S°P°T2°

M°T1°S°P°T2°M°T1°S(X).

(1)

注意到S和T1,T2,P可以交換位置，因此式(1)等價(jià)于

P°T2°S°M°S°T1°P°T2°M°T1°P°T2°

S°M°S°T1°P°T2°M°T1(X),

相應(yīng)的Msuper=T1°P°T2°M°T1°P°T2為超級(jí)線性層.因此，可以通過Msuper的分支數(shù)來估計(jì)算法的活躍S盒數(shù)，進(jìn)而估計(jì)其抵抗差分和線性分析的能力，即

Msuper=T1·P·T2·M·T1·P·T2=

(2)

因此，我們可以直接通過式(2)來計(jì)算Msuper的分支數(shù).

2.3 等價(jià)類劃分準(zhǔn)則

為了減少搜索空間，我們進(jìn)一步探索uBlock類結(jié)構(gòu)的等價(jià)類劃分準(zhǔn)則，并給出最優(yōu)向量置換的搜索策略.首先，uBlock類結(jié)構(gòu)可用圖3描述：

顯然，圖4(a)和4(b)兩種形式是等價(jià)的，此時(shí)假若MQ=QM，則圖4(c)與圖4(a)和4(b)也是等價(jià)的，即可得到圖4(d)與4(a)等價(jià)，即假若MQ=QM，則P與QPQ-1在uBlock類結(jié)構(gòu)中具有相同的密碼學(xué)性質(zhì).

于是，我們可以給出如下搜索策略：

策略1.uBlock類結(jié)構(gòu)最優(yōu)向量置換的搜索策略.

步驟1.確定使得MQ=QM的所有置換Q；

步驟2.對(duì)得到的所有置換Q，則P與QPQ-1屬于同一個(gè)等價(jià)類.

步驟3.對(duì)每一個(gè)等價(jià)類中的代表元，測(cè)試算法整體的全擴(kuò)散輪數(shù).

步驟4.對(duì)全擴(kuò)散輪數(shù)最小的置換，檢測(cè)Msuper及其逆變換的分支數(shù).

3 應(yīng) 用

我們將第2節(jié)的搜索策略應(yīng)用于128 b分組和256 b分組的uBlock類結(jié)構(gòu)中，尋找最優(yōu)向量置換.對(duì)于128 b和256 b分組的uBlock類結(jié)構(gòu)，我們選擇與uBlock算法中的結(jié)構(gòu)相同，即P層是PL和PR的并置，且均為面向字節(jié)的向量置換，因此我們可以進(jìn)一步優(yōu)化搜索策略1.

3.1 128 b分組

128 b分組的uBlock類結(jié)構(gòu)的擴(kuò)散層描述如圖5所示:

其中

則

其中，I為單位矩陣，O為零矩陣.

由表3可知，128 b分組的uBlock類結(jié)構(gòu)至少需要2輪全擴(kuò)散.因此，我們僅需要尋找2輪全擴(kuò)散下的最優(yōu)向量置換.出于性能的考慮，若PL或PR是恒等變換，則輪函數(shù)少一個(gè)指令，此時(shí)算法軟件性能會(huì)有所提升.使用等價(jià)類劃分技術(shù)，我們發(fā)現(xiàn)PL和PR是恒等變換時(shí)均有27個(gè)等價(jià)類滿足2輪全擴(kuò)散.部分具體實(shí)例在附錄中給出.

此外，我們考慮4輪超級(jí)S盒下，擴(kuò)散層的分支數(shù)達(dá)到最優(yōu)的情形.由于

我們可將擴(kuò)散層看作一個(gè)2×2的分塊矩陣，考慮其為MDS矩陣，即分支數(shù)為3.此時(shí)，根據(jù)超級(jí)S盒和分支數(shù)的概念，可知其4輪至少有24個(gè)活躍S盒(與uBlock-128中選擇的向量置換在4輪時(shí)的活躍S盒數(shù)一致).

Q1A2=A2Q1,Q2C2=C2Q2,

Q1B2=B2Q2,Q2B2=B2Q1.

策略2.uBlock-128最優(yōu)向量置換的搜索策略.

步驟1.尋找使得Q3·A2=A2·Q3的所有置換Q3，記為集合SQ3；

步驟2.尋找使得Q4·C2=C2·Q4的所有置換Q4，記為集合SQ4；

步驟4.使用集合對(duì)SQ1,Q2中的置換，對(duì)P的全空間做等價(jià)類劃分，若

則

步驟5.對(duì)每一個(gè)等價(jià)類中的代表元，輸出4輪超級(jí)S盒下擴(kuò)散層的分支數(shù)為3的置換P.

此時(shí)，當(dāng)PL,PR其中一個(gè)為恒等置換時(shí)，不存在MDS矩陣.所以我們進(jìn)一步將PL,PR其中一個(gè)放寬為循環(huán)移位，此時(shí)，滿足2輪全擴(kuò)散且超級(jí)擴(kuò)散層為MDS時(shí)的等價(jià)類共有3 556個(gè).部分具體實(shí)例在附錄中給出.這一結(jié)果顯示uBlock-128算法選擇的向量置換是最優(yōu)的，不存在可進(jìn)一步減少指令數(shù)的最優(yōu)向量置換對(duì).受益于我們的等價(jià)類劃分方法，最優(yōu)向量置換對(duì)的數(shù)量大幅減少，這對(duì)后續(xù)進(jìn)一步篩選滿足其他安全性指標(biāo)時(shí)提供了便利.

3.2 256 b分組

256 b分組的uBlock類結(jié)構(gòu)的擴(kuò)散層描述如圖6所示.其中，

T1=(1,5,2,6,3,7,4,8),

T2=(1,3,5,7,2,4,6,8)，

我們首先關(guān)注256 b分組的uBlock類結(jié)構(gòu)的全擴(kuò)散輪數(shù)，得到定理1.

定理1.對(duì)于256 b分組的uBlock類結(jié)構(gòu)，PL,PR選擇基于字節(jié)的向量置換時(shí)，其全擴(kuò)散輪數(shù)的下界為3.

證明.將256 b分組的uBlock類結(jié)構(gòu)看作是8個(gè)分支的輸入，從左到右依次是第1到第8個(gè)分支，每個(gè)分支都為8 b.我們假定輸入向量漢明重量為1，為(0,1,0,…,0)，則經(jīng)過一輪輪函數(shù)的輸出為：

第1個(gè)分支為(a1,a2,a3,a4)，其中

a1=(0,0),a3=(0,1),a2=a4=(1,1).

第5個(gè)分支為(b1,b2,b3,b4)，其中

b1=b2=(1,1),b3=b4=(1,0).

其余分支的漢明重量均為零.注意到，(a1,a2,a3,a4)中的元素只能置換到下一輪M16輸入的左半支，(b1,b2,b3,b4)中的元素只能置換到右半支.然而，要使2輪全擴(kuò)散，進(jìn)入下一輪4個(gè)M16的向量漢明重量只能為(2,2,3,4)和(2,3,3,3)，且漢明重量為2的部分只能有4種搭配，即(a1,b1),(a1,b2),(a3,b3)和(a3,b4).然而由第2節(jié)可知，對(duì)于M16，輸入向量漢明重量為2時(shí)，只有8種情形可以全擴(kuò)散，這8種情形左右半支漢明重量均為1，且非零位置只有(1,0)與(1,0)搭配和(0,1)與(0,1)搭配.因此，256 b分組的uBlock類結(jié)構(gòu)至少需要3輪全擴(kuò)散.

由表3可知，若256 b分組的uBlock類結(jié)構(gòu)的P層使用更加細(xì)粒度的置換，則可能會(huì)在2輪達(dá)到全擴(kuò)散.考慮到在算法實(shí)現(xiàn)時(shí)大置換實(shí)現(xiàn)效率不佳，因此我們并未嘗試尋找大置換下2輪達(dá)到全擴(kuò)散的情形.

接下來，我們?cè)噲D尋找3輪全擴(kuò)散下256 b分組的uBlock類結(jié)構(gòu)的最優(yōu)向量置換.對(duì)于PL和PR，我們與uBlock-256一樣，考慮面向字節(jié)的向量置換.考慮到軟件性能的提升，我們假定PL或PR其中一個(gè)為恒等變換，此時(shí)我們找到大量滿足3輪全擴(kuò)散的置換，在附錄中我們給出了部分實(shí)例.

此外，我們考慮4輪超級(jí)S盒下，擴(kuò)散層的分支數(shù)為4的情形.由于

我們可將擴(kuò)散層看作一個(gè)4×4的分塊矩陣，考慮其分支數(shù)為4的情形.此時(shí)，根據(jù)超級(jí)S盒和分支數(shù)的概念，可知其4輪至少有32個(gè)活躍S盒(與uBlock-256算法中的置換在4輪時(shí)的活躍S盒一致).

Q1A2=A2Q1,Q2A2=A2Q2,

Q3C2=C2Q3,Q4C2=C2Q4,

Q1B2=B2Q3,Q2B2=B2Q4,

Q3B2=B2Q1,Q4B2=B2Q2.

因此，我們給出如下搜索策略3:

策略3.uBlock-256最優(yōu)向量置換的搜索策略.

步驟1.尋找使得Q3·A2=A2·Q3的所有置換Q3，記為集合SQ3；尋找使得Q4·C2=C2·Q4的所有置換Q4，記為集合SQ4.

步驟2.尋找集合對(duì)SQa,Qb，使得Qa∈SQ3,Qb∈SQ4滿足Qa·B2=B2·Qb；尋找集合對(duì)SQc,Qd，使得Qc∈SQ3,Qd∈SQ4滿足Qd·B2=B2·Qc.

步驟3.取(Q1,Q2)∈SQa,Qb,(Q3,Q4)∈SQc,Qd,對(duì)P的全空間做等價(jià)類劃分，即若

步驟4.對(duì)每一個(gè)等價(jià)類中的代表元，輸出3輪全擴(kuò)散且4輪超級(jí)S盒下擴(kuò)散層的分支數(shù)為4的置換P.

經(jīng)過實(shí)驗(yàn)，當(dāng)PL和PR其中一個(gè)為恒等變換時(shí)，我們并未找到3輪全擴(kuò)散且在4輪超級(jí)擴(kuò)散層分支數(shù)為4的置換對(duì).對(duì)于PL和PR均為一般置換時(shí)，存在大量3輪全擴(kuò)散且在4輪超級(jí)擴(kuò)散層分支數(shù)為4的置換對(duì)，部分具體實(shí)例在附錄中給出.

在僅考慮全擴(kuò)散輪數(shù)、性能和超級(jí)擴(kuò)散層的分支數(shù)這3個(gè)指標(biāo)時(shí)，我們的結(jié)果與uBlock-256使用的向量置換是一致的.然而，本文中給出的等價(jià)類劃分規(guī)則可以將滿足條件的置換對(duì)縮小到較小的范圍，這將為后續(xù)進(jìn)一步測(cè)評(píng)其抵抗其他分析方法時(shí)提供便利.

4 總 結(jié)

在本文中，我們探索uBlock類結(jié)構(gòu)最優(yōu)向量置換的選取.對(duì)于uBlock算法族，擴(kuò)散層分為2部分：一部分是由Feistel結(jié)構(gòu)構(gòu)造的16維最優(yōu)二元擴(kuò)散層，另一部分為2個(gè)向量置換的并置.我們的目標(biāo)是在二元擴(kuò)散層固定的前提下，尋找最優(yōu)向量置換來提升算法整體的安全性和實(shí)現(xiàn)效率.本文中，我們主要的評(píng)價(jià)指標(biāo)為算法的全擴(kuò)散輪數(shù)、軟件性能和4輪超級(jí)S盒下擴(kuò)散層的分支數(shù).

首先，我們探索uBlock類結(jié)構(gòu)的擴(kuò)散性，給出了不同規(guī)模下uBlock類結(jié)構(gòu)全擴(kuò)散輪數(shù)的下界.其次，為了減少搜索復(fù)雜度，基于uBlock類結(jié)構(gòu)的特點(diǎn)，我們提出了等價(jià)類劃分技術(shù).進(jìn)一步，基于全擴(kuò)散輪數(shù)最優(yōu)、軟件性能優(yōu)良和超級(jí)擴(kuò)散層的分支數(shù)，我們?cè)O(shè)計(jì)了uBlock類結(jié)構(gòu)最優(yōu)向量置換的搜索策略.最后，將搜索策略應(yīng)用于128 b和256 b分組的uBlock類結(jié)構(gòu)中.在具體應(yīng)用時(shí)，結(jié)合不同分組長(zhǎng)度下算法的特點(diǎn)，我們進(jìn)一步優(yōu)化了最優(yōu)向量置換的搜索策略，并給出具體實(shí)例.

對(duì)于128 b分組的uBlock類結(jié)構(gòu)，若PL和PR其中一個(gè)為恒等變換時(shí)，存在滿足2輪全擴(kuò)散的置換對(duì)；然而，不存在2輪全擴(kuò)散且超級(jí)擴(kuò)散層分支數(shù)最優(yōu)的置換對(duì).因此，我們將PL或PR放寬到循環(huán)移位后，給出了全擴(kuò)散輪數(shù)及超級(jí)擴(kuò)散層分支數(shù)均最優(yōu)的置換對(duì).對(duì)于256 b分組的uBlock類結(jié)構(gòu)，我們證明了其最優(yōu)全擴(kuò)散輪數(shù)為3輪，若PL或PR其中一個(gè)為恒等變換時(shí)，存在3輪全擴(kuò)散的置換對(duì)，然而不存在全擴(kuò)散輪數(shù)為3且超級(jí)擴(kuò)散層的分支數(shù)為4的置換對(duì).與uBlock算法相比，在僅考慮全擴(kuò)散輪數(shù)這一指標(biāo)時(shí)，算法所需的向量置換指令更少，從而有更高的軟件實(shí)現(xiàn)效率.在考慮全擴(kuò)散輪數(shù)和超級(jí)擴(kuò)散層分支數(shù)2個(gè)指標(biāo)后，我們的結(jié)果與uBlock算法中使用的向量置換是一致的，表明uBlock算法選擇的向量置換是最優(yōu)的，不存在可進(jìn)一步減少指令數(shù)的向量置換對(duì)，但是我們提出的等價(jià)類劃分規(guī)則可以將置換對(duì)的數(shù)量大幅減少，為后續(xù)uBlock類算法的設(shè)計(jì)提供技術(shù)支持.

作者貢獻(xiàn)申明：李曉丹提出了算法思路，撰寫論文；吳文玲提出指導(dǎo)意見并修改論文；張麗提出修改意見.