NORX算法中非線性組件的移位參數(shù)選取準(zhǔn)則研究*

沈 璇,何 俊

(國(guó)防科技大學(xué) 信息通信學(xué)院，湖北 武漢 430010)

凱撒競(jìng)賽(Competition for Authenticated Encryption:Security,Applicability,and Robustness，CAESAR)[1]是由著名密碼學(xué)家Bernstein發(fā)起的一項(xiàng)尋求安全高效認(rèn)證加密算法的全球性活動(dòng)。該競(jìng)賽得到了美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所 (National Institute of Standard and Technology,NIST)的大力支持。CAESAR于2014年開(kāi)始，第一輪共收到了來(lái)自全球各個(gè)密碼團(tuán)隊(duì)提交的57個(gè)候選算法，其中有29個(gè)候選算法進(jìn)入了第二輪，15個(gè)候選算法進(jìn)入了第三輪，并最終在2018年針對(duì)不同的應(yīng)用場(chǎng)景評(píng)選出了7個(gè)獲勝算法。NORX算法[2]是進(jìn)入該競(jìng)賽第三輪的候選算法。

自NORX算法發(fā)布以來(lái)，許多密碼學(xué)者從不同角度對(duì)其安全性進(jìn)行了研究。Aumasson等[3]在Latincrypt 2014上首先分析了其內(nèi)部置換函數(shù)的差分特性。進(jìn)一步，Das等[4]給出了內(nèi)部置換函數(shù)的高階差分特性。接著，Bagheri等[5]在FSE 2016上給出了NORX置換函數(shù)縮減到2輪的密鑰恢復(fù)攻擊。后來(lái)，Biryukov等[6]在2017年給出了NOXR置換函數(shù)的一些非隨機(jī)特性。最近，Chaigneau等[7]利用NORX算法置換函數(shù)的對(duì)稱性質(zhì)構(gòu)造了唯密文偽造攻擊和密鑰恢復(fù)攻擊。

在密碼算法中，非線性組件的選擇對(duì)于密碼算法的安全強(qiáng)度具有至關(guān)重要的作用[8]。為了提高硬件的實(shí)現(xiàn)效率，NORX算法的唯一非線性組件采用異或、與和移位操作的組合來(lái)代替模加操作。在這種組合中,移位參數(shù)的選取具有十分重要的作用。為了研究的方便，稱NORX算法中非線性組件移位參數(shù)任取的函數(shù)為可變移位函數(shù)。在NORX算法的設(shè)計(jì)文檔中，設(shè)計(jì)者將移位參數(shù)選取為1，但是并沒(méi)有從算法安全性的角度進(jìn)行說(shuō)明。因此，本文通過(guò)研究可變移位函數(shù)的密碼學(xué)性質(zhì)來(lái)探討NORX算法中非線性組件移位參數(shù)的選取準(zhǔn)則。

模加操作是密碼算法常用的非線性組件，它具有良好的密碼學(xué)性質(zhì)。因此，本文將研究可變移位函數(shù)對(duì)模加函數(shù)的非線性逼近性質(zhì)。當(dāng)可變移位函數(shù)取不同移位參數(shù)時(shí)，若其逼近概率越高，則說(shuō)明它越接近模加操作，其非線性逼近性質(zhì)也越好。此外，循環(huán)分析方法[9-10]是近些年來(lái)針對(duì)模加循環(huán)異式(Addition,Rotation,XDR,ARX)型密碼算法十分有效的一種分析方法，它對(duì)包括BLAKE2[11]、Keccak[12]、Skein[13]等在內(nèi)的許多Hash函數(shù)具有十分顯著的攻擊效果。不僅如此，由循環(huán)分析方法發(fā)展而來(lái)的循環(huán)異或分析方法[14-15]也是最近針對(duì)ARX型密碼算法進(jìn)行安全性分析的熱點(diǎn)。循環(huán)分析方法的關(guān)鍵是研究循環(huán)對(duì)通過(guò)算法非線性組件的循環(huán)概率。因此，本文還將研究可變移位函數(shù)的循環(huán)概率表達(dá)式。若其最大循環(huán)概率越低，則它抵抗循環(huán)攻擊的能力越強(qiáng)。

在非線性逼近性質(zhì)方面，本文證明了隨著移位參數(shù)k的變化，可變移位函數(shù)的逼近概率是一個(gè)關(guān)于移位參數(shù)k的三值函數(shù)。其中：當(dāng)k=0時(shí)，逼近概率最?。划?dāng)k=1時(shí)，逼近概率最大；當(dāng)k≥2時(shí)，逼近概率是與移位參數(shù)k無(wú)關(guān)的常值。在循環(huán)性質(zhì)方面，本文從理論上給出了不同移位參數(shù)下可變移位函數(shù)循環(huán)概率的顯性表達(dá)式，并且證明了對(duì)于任意非零移位參數(shù)而言，可變移位函數(shù)均能夠取得相同的最大循環(huán)概率。這兩類密碼學(xué)性質(zhì)的研究在一定程度上揭示了移位參數(shù)的選取準(zhǔn)則，對(duì)設(shè)計(jì)類似非線性組件的算法具有較強(qiáng)的指導(dǎo)意義。

1 預(yù)備知識(shí)

1.1 符號(hào)標(biāo)記

表1給出了后文涉及的符號(hào)標(biāo)記。

表1 文中涉及的符號(hào)含義Tab.1 Some notations used in this paper

1.2 NORX算法簡(jiǎn)介

NORX算法是由密碼學(xué)者Aumasson等在2014年提交給CAESAR競(jìng)賽的一個(gè)輕量級(jí)認(rèn)證加密算法，該算法的整體框架采用海綿結(jié)構(gòu)。NORX算法的內(nèi)部置換函數(shù)是基于ARX設(shè)計(jì)的，它的算法設(shè)計(jì)思路來(lái)源于密碼算法ChaCha[16]和BLAKE2[17]。為了實(shí)現(xiàn)輕量化，NORX算法并沒(méi)有采用密碼學(xué)性能良好的模加操作，而是采用異或、與和移位操作的組合來(lái)代替，即用X⊕Y⊕XY?1代替X+Y?？紤]到本文的研究只涉及NORX算法中的非線性組件，有關(guān)算法其他細(xì)節(jié)的描述參見(jiàn)文獻(xiàn)[2]。另外，設(shè)計(jì)者在算法文檔中只給出了非線性組件X⊕Y⊕XY?1來(lái)源于等式

X+Y=(X⊕Y)+(XY)?1

但并未從密碼安全的角度對(duì)X⊕Y⊕XY?1中移位參數(shù)的選擇進(jìn)行說(shuō)明。本文主要從密碼學(xué)角度對(duì)NORX算法中非線性組件移位參數(shù)的選擇進(jìn)行探討。為了在后文中描述方便，令可變移位函數(shù)為：

fk(X,Y)=(X⊕Y)⊕((XY)?k)

注意到當(dāng)k=1時(shí)，f1(X,Y)即是NORX算法中的非線性組件X⊕Y⊕XY?1。

2 可變移位函數(shù)的非線性逼近性質(zhì)分析

本節(jié)主要研究了可變移位函數(shù)的非線性逼近性質(zhì)。在這一節(jié)中，先研究了可變移位函數(shù)與模加函數(shù)相等時(shí)的等價(jià)條件，然后利用該條件計(jì)算可變移位函數(shù)逼近模加函數(shù)的精確概率值，最后對(duì)本節(jié)進(jìn)行了總結(jié)。

首先，給出如下引理。

引理令X=(xn-1，xn-2，…，x1，x0),Y=(yn-1，yn-2，…，y1，y0),這里xi,yi∈F2。并且設(shè)g(X,Y)=X+Y,fk(X,Y)=(X⊕Y)⊕((XY)?k)，則有：

(1)

證明：因?yàn)間(X,Y)=X+Y=X⊕Y⊕C,這里C=(cn-1，…，c1，c0) 且有：

(2)

因此，fk(X,Y)=g(X,Y)?C=(XY)?k。下面通過(guò)逐比特比較的方法，分k=0,k=1,k≥2三種情況進(jìn)行討論。

情形1：當(dāng)k=0時(shí),C=XY,即

(3)

則有xiyi=0,i=0,1,2,…,n-1。

情形2：當(dāng)k=1時(shí),C=(XY)?1,即

(4)

則有xiyi(xi+1⊕yi+1)=0,i=0,1,2,…,n-3。

情形3：當(dāng)2≤k≤n-1時(shí),C=(XY)?k,即

(5)

則有xiyi=0,i=0,1,2,…,n-2。因此，上述引理成立。

□

利用上述引理，可以得到如下定理。

(6)

則有

(7)

且

(8)

證明：根據(jù)引理得到如下情形。

情形1：當(dāng)k=0時(shí),X+Y=(X⊕Y)⊕XY?xiyi=0,i=0,1,2,…,n-1。對(duì)于任意的xiyi=0,(xi,yi)可取(0,0)、(0,1)、(1,0)這3種情況，因此

(9)

情形2：當(dāng)2≤k≤n-1時(shí),X+Y=(X⊕Y)⊕((XY)?k)?xiyi=0，這里i=0,1,…,n-2。當(dāng)0≤i≤n-2時(shí)，對(duì)于任意的xiyi=0,(xi,yi)可取(0,0)、(0,1)、(1,0)這三種情況。當(dāng)i=n-1時(shí)，xi、yi無(wú)限制，可取所有可能的4種情況。因此

(10)

情形3：當(dāng)k=1時(shí)，因?yàn)?/p>

(11)

令Fn(x0,…,xn-3,xn-2,y0,…,yn-3,yn-2)=0表示上述方程組，并且令

(12)

因?yàn)?⊕0=1⊕1,0⊕1=1⊕0,所以

(13)

記方程組Fn(x0,x1,…,xn-2,y0,y1,…,yn-2)=0解的數(shù)目為Nn，則有：

(14)

注意到 (xn-1,yn-1) 可以取 (0,0)、(0,1)、(1,0)、(1,1)這4種情況，因此有

(15)

因?yàn)镕n(x0,x1,…,xn-2,y0,y1,…,yn-2)=0當(dāng)且僅當(dāng)

(16)

所以

(17)

化簡(jiǎn)上述方程組得：

(18)

注意當(dāng)n=3時(shí),方程組即為x0y0(x1⊕y1)=0。因此

(19)

則

(20)

令

(21)

則有A=QΛQ-1。因此

(22)

則

(23)

□

從定理1中可得，對(duì)于任意n比特長(zhǎng)的兩個(gè)數(shù)據(jù)塊，能夠計(jì)算出不同移位參數(shù)k下可變移位函數(shù)的逼近概率，如表2所示。

表2 可變移位函數(shù)在不同移位參數(shù)下的逼近概率Tab.2 Approximation probability of variable shift function when k takes different values

從定理1和表2可知：當(dāng)k=1時(shí)，fk(X,Y)的逼近概率最大；當(dāng)k=0時(shí)，fk(X,Y)的逼近概率最小。此外，當(dāng)k≥2時(shí)，不管移位參數(shù)取何值，fk(X,Y)的逼近概率均相同，并且其概率大小為中間值。當(dāng)移位參數(shù)fk(X,Y)給定時(shí)，數(shù)據(jù)塊的規(guī)模n越大，fk(X,Y)的逼近概率越小?？紤]到逼近概率越高，非線性逼近的性質(zhì)越好，在NORX算法中移位參數(shù)取1達(dá)到了最佳的非線性逼近。

3 可變移位函數(shù)的循環(huán)性質(zhì)分析

上一節(jié)研究了可變移位函數(shù)的非線性逼近性質(zhì)，本節(jié)主要研究該函數(shù)的循環(huán)性質(zhì)。首先介紹關(guān)于函數(shù)的循環(huán)對(duì)概念，然后給出一個(gè)關(guān)于可變移位函數(shù)循環(huán)概率的定理，最后對(duì)本節(jié)進(jìn)行總結(jié)。

G(X,Y)??r=G(X??r,Y??r)

(24)

下面給出一個(gè)關(guān)于可變移位函數(shù)循環(huán)概率的定理。

定理2令X、Y是n比特串,移位參數(shù)k滿足0≤k≤n-1,循環(huán)參數(shù)r滿足1≤r≤n-1，并且fk(X,Y)=(X⊕Y)⊕((XY)?k)，則(X,Y)關(guān)于可變移位函數(shù)fk(X,Y)循環(huán)對(duì)的概率為：

(25)

證明：根據(jù)fk(X,Y)的具體形式知

fk(X,Y)??r=

((X??r)⊕(Y??r))⊕((XY)?k)??r

(26)

并且

fk(X??r,Y??r)=

(X??r)⊕(Y??r)⊕((X??r)(Y??r)?k)

(27)

因此

fk(X,Y)??r=fk(X??r,Y??r)?

((XY)?k)??r=(X??r)(Y??r)?k

(28)

令Z=XY,則

fk(X,Y)??r=fk(X??r,Y??r)?
(Z?k)??r=(Z??r)?k

(29)

當(dāng)k=0時(shí),

f0(X,Y)??r=f0(X??r,Y??r)

(30)

始終成立，即

P(f0(X,Y)??r=f0(X??r,Y??r))=1

(31)

當(dāng)1≤k≤n-1時(shí),分r≤k和r>k兩種情況進(jìn)行討論。

情形1：當(dāng)r≤k,則有

(32)

根據(jù)式(29)可得zj=0，這里

j=0,1,…,r-1,n-k,n-k+1,…,n-k+(r-1)

(33)

(34)

情形2：當(dāng)r>k,則有

(35)

根據(jù)式(29)可得zj=0，這里

j=r-k,r-k+1,…,r-1,n-k,…,n-1

(36)

P(fk(X,Y)??r=fk(X??r,Y??r))

(37)

因此，上述定理成立。

□

由定理2知：當(dāng)k=0時(shí),f0(X,Y)的循環(huán)概率為1；當(dāng)1≤k≤n-1時(shí),fk(X,Y)的循環(huán)概率在循環(huán)參數(shù)r=1時(shí)均能達(dá)到最大，并且最大概率均為9/16。注意到文獻(xiàn)[9]中引理11只是本文定理2中關(guān)于移位參數(shù)k=1時(shí)的推論。

在密碼算法中，非線性組件的循環(huán)概率越低，越有利于抵抗循環(huán)攻擊。因此，從循環(huán)概率值的分布情況看，移位參數(shù)取非零值時(shí)對(duì)應(yīng)的可變移位函數(shù)具有更好的循環(huán)性質(zhì)。進(jìn)一步，不管非零移位參數(shù)取何值，可變移位函數(shù)在循環(huán)參數(shù)r=1時(shí)均能達(dá)到相同的最大循環(huán)概率。

4 結(jié)論

本文從非線性逼近和循環(huán)分析兩方面研究了NORX算法中非線性函數(shù)的移位參數(shù)選取準(zhǔn)則。研究結(jié)果表明：從抵抗密碼攻擊的角度看，當(dāng)移位參數(shù)為0時(shí)，可變移位函數(shù)的非線性逼近和循環(huán)性質(zhì)均最差；當(dāng)移位參數(shù)為1時(shí)，其非線性逼近和循環(huán)性質(zhì)均最好；當(dāng)移位參數(shù)為其他值時(shí)，其具有相同效果的非線性逼近和循環(huán)性質(zhì)。因此，NORX算法中唯一非線性組件的移位參數(shù)取1時(shí)達(dá)到了最佳的非線性逼近和循環(huán)性質(zhì)。本文對(duì)NORX算法中非線性函數(shù)移位參數(shù)選取準(zhǔn)則的探討，不僅有助于提高NORX算法的安全性分析結(jié)果，而且還對(duì)設(shè)計(jì)類似組件函數(shù)的算法提供了理論指導(dǎo)。