NORX算法中非線性組件的移位參數選取準則研究*

沈 璇,何 俊

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

凱撒競賽(Competition for Authenticated Encryption:Security,Applicability,and Robustness，CAESAR)[1]是由著名密碼學家Bernstein發起的一項尋求安全高效認證加密算法的全球性活動。該競賽得到了美國國家標準技術研究所 (National Institute of Standard and Technology,NIST)的大力支持。CAESAR于2014年開始，第一輪共收到了來自全球各個密碼團隊提交的57個候選算法，其中有29個候選算法進入了第二輪，15個候選算法進入了第三輪，并最終在2018年針對不同的應用場景評選出了7個獲勝算法。NORX算法[2]是進入該競賽第三輪的候選算法。

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

在密碼算法中，非線性組件的選擇對于密碼算法的安全強度具有至關重要的作用[8]。為了提高硬件的實現效率，NORX算法的唯一非線性組件采用異或、與和移位操作的組合來代替模加操作。在這種組合中,移位參數的選取具有十分重要的作用。為了研究的方便，稱NORX算法中非線性組件移位參數任取的函數為可變移位函數。在NORX算法的設計文檔中，設計者將移位參數選取為1，但是并沒有從算法安全性的角度進行說明。因此，本文通過研究可變移位函數的密碼學性質來探討NORX算法中非線性組件移位參數的選取準則。

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

在非線性逼近性質方面，本文證明了隨著移位參數k的變化，可變移位函數的逼近概率是一個關于移位參數k的三值函數。其中：當k=0時，逼近概率最小；當k=1時，逼近概率最大；當k≥2時，逼近概率是與移位參數k無關的常值。在循環性質方面，本文從理論上給出了不同移位參數下可變移位函數循環概率的顯性表達式，并且證明了對于任意非零移位參數而言，可變移位函數均能夠取得相同的最大循環概率。這兩類密碼學性質的研究在一定程度上揭示了移位參數的選取準則，對設計類似非線性組件的算法具有較強的指導意義。

1 預備知識

1.1 符號標記

表1給出了后文涉及的符號標記。

表1 文中涉及的符號含義Tab.1 Some notations used in this paper

1.2 NORX算法簡介

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

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

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

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

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

2 可變移位函數的非線性逼近性質分析

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

首先，給出如下引理。

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

(1)

證明：因為g(X,Y)=X+Y=X⊕Y⊕C,這里C=(cn-1，…，c1，c0) 且有：

(2)

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

情形1：當k=0時,C=XY,即

(3)

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

情形2：當k=1時,C=(XY)?1,即

(4)

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

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

(5)

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

□

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

(6)

則有

(7)

且

(8)

證明：根據引理得到如下情形。

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

(9)

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

(10)

情形3：當k=1時，因為

(11)

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

(12)

因為0⊕0=1⊕1,0⊕1=1⊕0,所以

(13)

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

(14)

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

(15)

因為Fn(x0,x1,…,xn-2,y0,y1,…,yn-2)=0當且僅當

(16)

所以

(17)

化簡上述方程組得：

(18)

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

(19)

則

(20)

令

(21)

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

(22)

則

(23)

□

從定理1中可得，對于任意n比特長的兩個數據塊，能夠計算出不同移位參數k下可變移位函數的逼近概率，如表2所示。

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

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

3 可變移位函數的循環性質分析

上一節研究了可變移位函數的非線性逼近性質，本節主要研究該函數的循環性質。首先介紹關于函數的循環對概念，然后給出一個關于可變移位函數循環概率的定理，最后對本節進行總結。

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

(24)

下面給出一個關于可變移位函數循環概率的定理。

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

(25)

證明：根據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)

當k=0時,

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

(30)

始終成立，即

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

(31)

當1≤k≤n-1時,分r≤k和r>k兩種情況進行討論。

情形1：當r≤k,則有

(32)

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

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

(33)

(34)

情形2：當r>k,則有

(35)

根據式(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知：當k=0時,f0(X,Y)的循環概率為1；當1≤k≤n-1時,fk(X,Y)的循環概率在循環參數r=1時均能達到最大，并且最大概率均為9/16。注意到文獻[9]中引理11只是本文定理2中關于移位參數k=1時的推論。

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

4 結論

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