KNOT認(rèn)證加密算法的零和區(qū)分器分析

葉 濤，韋永壯，李靈琛

(1.桂林電子科技大學(xué) 信息與通信學(xué)院，廣西壯族自治區(qū) 桂林 541004；2.桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室，廣西壯族自治區(qū) 桂林 541004；3.密碼科學(xué)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100878)

伴隨著物聯(lián)網(wǎng)技術(shù)和5G通信技術(shù)的快速發(fā)展，各種移動通信終端以及物聯(lián)網(wǎng)中的傳感器終端遍布于人們的實(shí)際生活。如何確保通信的安全變得愈加重要。輕量級密碼算法作為一種重要的加密體制，具有易于實(shí)現(xiàn)、加解密速度快、占用資源少等優(yōu)勢，非常適用于這些資源受限的環(huán)境中，所以，輕量級密碼算法的設(shè)計(jì)[1]與分析[2]是近些年的研究熱點(diǎn)。最近，NIST(美國國家標(biāo)準(zhǔn)與技術(shù)研究院)發(fā)起了輕量級密碼算法征集競賽[3]活動，旨在面向全世界公開征集適用于資源受限環(huán)境下的輕量級密碼算法，其中第1輪共有56個(gè)候選算法。經(jīng)過第1輪的安全性評估，現(xiàn)有32個(gè)密碼算法入圍第2輪，KNOT密碼算法[4]是其中之一。KNOT密碼算法是由ZHANG等人設(shè)計(jì)的，由于其可以充分地利用比特切片法來實(shí)現(xiàn)，所以該算法具有優(yōu)秀的軟件和硬件實(shí)現(xiàn)性能。KNOT具有認(rèn)證加密功能和哈希運(yùn)算的功能，這些性能的好壞依賴于KNOT內(nèi)部輪置換函數(shù)的安全性。KNOT置換有3個(gè)版本，按照每個(gè)置換的分組長度，標(biāo)記為KNOT-256，KNOT-384和KNOT-512，其中KNOT-256算法的軟硬件實(shí)現(xiàn)所占用的資源最少，非常適用于資源受限的環(huán)境中。在KNOT的設(shè)計(jì)文檔中，算法的設(shè)計(jì)者認(rèn)為KNOT-256至少需要49輪才能抵抗差分分析和線性密碼分析，同時(shí)認(rèn)為KNOT-256算法存在的最長不可能差分區(qū)分器的輪數(shù)為17輪。對于積分分析，算法的設(shè)計(jì)者給出了17輪的積分區(qū)分器，需要的數(shù)據(jù)復(fù)雜度為2255。但是，是否存在更高輪的區(qū)分器還需要進(jìn)一步研究。因此，如何給出KNOT認(rèn)證加密算法安全性新評價(jià)是目前的研究熱點(diǎn)。

2009年，AUMASSON和MEIER等首次提出零和區(qū)分器[5]的概念，本質(zhì)上這個(gè)區(qū)分器可以看做擴(kuò)展的積分區(qū)分器[6]。由于零和區(qū)分器一般是在已知密鑰[7]的前提下構(gòu)造的，所以構(gòu)造零和區(qū)分器的一般方法是從中間狀態(tài)向加密方向和解密方向構(gòu)建積分區(qū)分器，并將這兩個(gè)積分區(qū)分器連接到一起[8]。此外，也可以通過利用迭代置換的特殊性質(zhì)[9-10]來構(gòu)建零和區(qū)分器。但是，這些方法是基于算法結(jié)構(gòu)或者算法本身具有的特殊性質(zhì)提出的，不具有通用性。可分性[11]的提出在很大程度上解決了這個(gè)問題。可分性是廣義的積分性質(zhì)，利用優(yōu)化工具求解可分性的混合整數(shù)線性規(guī)劃模型(MILP)，攻擊者可以構(gòu)建出高輪的積分區(qū)分器。近些年來，利用可分性質(zhì)結(jié)合自動化搜索工具來構(gòu)建零和區(qū)分器成為了密碼學(xué)者的研究熱點(diǎn)內(nèi)容之一[12-13]。可分性的標(biāo)志位技術(shù)[14]是在2018年的美密會上由WANG等人提出的，相比于傳統(tǒng)的可分性分析方法，利用添加標(biāo)志位的可分性技術(shù)可以提高可分性的MILP模型的精確性和擴(kuò)展區(qū)分器的輪數(shù)，同時(shí)能夠提高搜索區(qū)分器的效率。將標(biāo)志位技術(shù)應(yīng)用于分組密碼算法零和區(qū)分器的搜索中能否提高零和區(qū)分器的輪數(shù)或縮減需要的計(jì)算復(fù)雜度，還需要進(jìn)一步研究。

筆者首先給出了密碼S盒可分性模型的新構(gòu)建方法；結(jié)合KNOT-256算法的結(jié)構(gòu)特點(diǎn)，給出了KNOT-256算法的可分性新模型，并由此設(shè)計(jì)了KNOT-256密碼算法的零和區(qū)分器自動化搜索方法。研究結(jié)果表明：KNOT-256存在20到30輪的零和區(qū)分器，這里僅提供第20輪和第30輪的結(jié)果，詳見表1。

表1 KNOT-256分析結(jié)果

文中用到的符號定義見表2。

表2 符號說明

1 基礎(chǔ)知識

1.1 可分性質(zhì)以及積分區(qū)分器的構(gòu)造

可分性[11]最初是由TODO在2015年提出的，這是一種廣義的積分性質(zhì)。2016年，TODO等人提出了基于比特的可分性質(zhì)[15]，其具體的定義如下。

(1)

為了更好地描述可分性的傳播性質(zhì)，文獻(xiàn)[16]中提出了可分性軌跡的概念，并給出了復(fù)制、與、異或等基本運(yùn)算以及S盒的可分性傳播模型。利用這些模型，可以構(gòu)建出一個(gè)不等式系統(tǒng)來描述可分性的傳播軌跡，然后利用優(yōu)化求解工具，如GUROBI[17]，通過判斷模型是否有解來確定積分區(qū)分器是否存在。

1.2 可分性的標(biāo)志位技術(shù)

在利用可分性質(zhì)搜索積分區(qū)分器時(shí)，活躍位置對應(yīng)的模型變量設(shè)置為1，其余的固定位置對應(yīng)的模型變量設(shè)置為0。在實(shí)際的密碼算法中，如果將這些固定的位置設(shè)置為不同的值，可分性的傳播軌跡會受到影響。所以，為了更精確地描述可分性的傳播性質(zhì)，WANG等人在2018年的美密會上提出了可分性的標(biāo)志位技術(shù)[14]。

對于可分性的MILP模型中的變量v，定義其對應(yīng)的標(biāo)志位為v.F∈{1F，0F，δ}，其中，1F表示變量在算法的內(nèi)部狀態(tài)的值為1，0F表示變量在算法的內(nèi)部狀態(tài)的值為0，δ表示變量在算法的內(nèi)部狀態(tài)的值不確定。標(biāo)志位的“異或”運(yùn)算規(guī)則為

(2)

標(biāo)志位的“與”運(yùn)算規(guī)則為

(3)

利用算法的結(jié)構(gòu)，結(jié)合標(biāo)志位的基本運(yùn)算規(guī)則，可以得到密碼置換任意的中間狀態(tài)對應(yīng)的標(biāo)志位。在對密碼算法的可分性質(zhì)構(gòu)建模型時(shí)，需要考慮標(biāo)志位對模型的影響。標(biāo)志位的影響主要表現(xiàn)在“與”運(yùn)算的模型上。

(4)

1.3 KNOT-256置換介紹

KNOT密碼算法[4]是國際輕量級密碼算法標(biāo)準(zhǔn)化征集競賽活動的第2輪候選算法之一[3]。按照分組長度，KNOT置換分為KNOT-256、KNOT-384和KNOT-512。其中，KNOT-256非常適用于在資源受限的環(huán)境下使用，所以筆者重點(diǎn)研究KNOT-256置換的安全性。KNOT-256置換的輪函數(shù)包含輪常數(shù)異或、列替換、行移位3個(gè)基本操作。

首先定義KNOT-256置換的第i輪的輸入狀態(tài)為Wi，輸出狀態(tài)為Wi+1，i≥0。Wi的具體形式如下：

(2) 替換SubCol(Wi)：KNOT-256密碼算法的S盒對每一列進(jìn)行操作，具體的操作方式如下：

表3 KNOT置換的S盒

(3) 行移位ShiftRow(Wi)：KNOT-256行移位操作對中間狀態(tài)的每行進(jìn)行操作，其中第0行不移位，第1行循環(huán)左移1位，第2行循環(huán)左移8位，第3行循環(huán)左移25位，得到的狀態(tài)為第i輪的輸出狀態(tài)Wi+1。

2 新零和區(qū)分器構(gòu)建方法

2.1 零和區(qū)分器基本構(gòu)建方法

零和區(qū)分器[5]的概念是由AUMASSON和MEIER在2009年提出的，其基本的定義如下。

可以利用可分性質(zhì)分別在加密方向和解密方向構(gòu)建積分區(qū)分器，然后將這兩個(gè)積分區(qū)分器連接在一起得到零和區(qū)分器。具體的步驟如下：

① 定義加密n1輪后的狀態(tài)對應(yīng)的模型變量為vn1，選取活躍變量的下標(biāo)集合為V，則vn1[j]=1，j∈V，其余固定為常數(shù)的位置的模型變量賦值為0，按照可分性的傳播模型構(gòu)建算法解密n1輪的可分性模型，并搜索對應(yīng)的積分區(qū)分器。

② 選取同樣的活躍位置V，構(gòu)建算法加密方向n1+1輪到n1+n2輪的可分性模型，并搜索對應(yīng)的積分區(qū)分器。

③ 如果①和②都存在積分區(qū)分器，則可以得到n1+n2輪的零和區(qū)分器，構(gòu)建這樣的區(qū)分器需要的數(shù)據(jù)復(fù)雜度為2|V|。

2.2 基于可分性和標(biāo)志位技術(shù)的零和區(qū)分器搜索方法

對于典型的分組密碼算法，其非線性層一般是由多個(gè)S盒構(gòu)成的。如何構(gòu)建基于標(biāo)志位的S盒的可分性傳播模型，是需要重點(diǎn)研究的問題。下面給出了算法1。

定義n比特S盒的輸入x={x0，x1，…，xn-1}，S盒的輸出表達(dá)式為S(x)，特別地，S(x|I，C)表示輸入固定xi0=c0，xi1=c1，…，xi|I|-1=c|I|-1后對應(yīng)的輸出表達(dá)式。如果I，C都為空的集合，則S(x)=S(x|I，C)。

算法1添加標(biāo)志位后S盒的可分性傳播軌跡。

⑤y=S(x|I，C)。

⑧ 返回K。

算法2縮減LS(x|I，C)，得到S(x|I，C)對應(yīng)的可分性MILP模型MS(x|I，C)。

③Ei=[]。

④ 對于j從0 到|LS(x|I，C)| - 1，重復(fù)執(zhí)行⑤到⑦。

⑤ val=lj·(ti‖1)，

⑥ 如果val<0：

⑦ 將j添加到集合Ei中。

⑧ 定義M為空的MILP模型。

益智仁揮發(fā)油對東莨菪堿致小鼠學(xué)習(xí)記憶障礙的改善作用研究 …………………………………………… 馬俊俏等（22）：3074

⑨ 定義模型M中的變量z0，z1，…，z|LS(x|I，C)|-1。

算法2的輸出表示排除S(x|I，C)全部的不可能可分性軌跡需要的最少的不等式。其中，算法2的第2行到第7行的作用是得到可以刪除S(x|I，C)的不可能可分性軌跡ti的不等式的下標(biāo)集合Ei；第8行到12行的作用是構(gòu)建用于縮減LS(x|I，C)的MILP模型；第13行到第19行的作用是對模型進(jìn)行求解。模型如果有解，則判斷是否存在zi=1；如果zi=1，則說明li包含在縮減后的不等式系統(tǒng)中；如果模型無解，則說明S(x|I，C)的可分性傳播軌跡不構(gòu)成凸包，需要使用“復(fù)制”“與”“異或”運(yùn)算的模型來構(gòu)建S(x|I，C)的可分性傳播模型。

輸入不同的I，C到算法1和算法2中，可以得到不同的標(biāo)志位對應(yīng)的S盒的可分性的MILP模型MS(x|I，C)，這些不同的模型預(yù)先存儲到一個(gè)大表中。當(dāng)構(gòu)建算法的可分性模型時(shí)，首先基于算法結(jié)構(gòu)，按照式(2)和式(3)計(jì)算經(jīng)過每一步操作后的狀態(tài)對應(yīng)的標(biāo)志位。在對S層操作前，先根據(jù)標(biāo)志位判斷每一個(gè)S盒對應(yīng)的I和C，然后將對應(yīng)的模型MS(x|I，C)添加到密碼算法輪函數(shù)的可分性模型中。對于輪函數(shù)中的其余的線性變換，如行移位、輪常數(shù)加、輪密鑰加等操作，標(biāo)志位對可分性模型沒有影響，這些操作的可分性模型的構(gòu)建和標(biāo)志位的轉(zhuǎn)化是獨(dú)立進(jìn)行的。這樣迭代多輪后，可以分別構(gòu)建出加密方向和解密方向的可分性模型，然后再利用2.1節(jié)中的方法來搜索零和區(qū)分器。為了更好地體現(xiàn)可分性的標(biāo)志位技術(shù)以及新的S盒的可分性模型在構(gòu)建零和區(qū)分器中發(fā)揮的積極作用，對KNOT-256置換的安全性進(jìn)行了評估。

3 KNOT-256置換的零和區(qū)分攻擊

3.1 KNOT-256的S盒可分性的MILP模型構(gòu)建新方法

表4 KNOT算法S盒的可分性傳播軌跡

將KNOT的S盒的可分性軌跡作為SAGE軟件中的函數(shù)inequality_generator( )的輸入，可以得到201個(gè)線性不等式LS(x)；然后利用算法2縮減LS(x)中的不等式，可以得到S盒的可分性傳播模型為MS(x)。具體的表達(dá)式如下：

(5)

當(dāng)集合I和C不為空集時(shí)，利用算法1和算法2可以得到固定位置I后S盒的可分性模型MS(x|I，C)。以I={2，3}，C={0，0}為例，可以得到此時(shí)對應(yīng)的可分性軌跡TS(x|{2，3}，{0，0})，如表5所示。

表5 S(x|{2，3}，{0，0})的可分性軌跡

將可分性軌跡TS(x|{2，3}，{0，0})輸入到SAGE軟件中的函數(shù)inequality_generator( )中，可以得到11個(gè)不等式LS(x|{2，3}，{0，0})。將LS(x|{2，3}，{0，0})輸入到算法2中，可以得到S(x|{2，3}，{0，0})的可分性傳播模型：

(6)

但是，在測試的過程中發(fā)現(xiàn)，對于KNOT密碼算法的S盒，當(dāng)I={0，2}，C={1，0}或者|I|=3時(shí)，算法2中構(gòu)建的模型是無解的。這說明固定這些位置后，S盒的可分性軌跡不是一個(gè)凸集。為了構(gòu)建這些情況下S盒的可分性模型，需要計(jì)算出此時(shí)S盒每一位的輸出表達(dá)式，然后利用“復(fù)制”“與”“異或”運(yùn)算的可分性模型來構(gòu)建此時(shí)的S盒的模型。以I={0，2}，C={1，0}為例，此時(shí)S盒的輸出表達(dá)式如下：

(7)

(8)

同理，可以得到|I|=3時(shí)對應(yīng)的可分性模型。

對于解密方向的KNOT的S盒，可以使用同樣的步驟得到S盒的可分性傳播模型。需要注意的是，當(dāng)I={0，1}，C={0，1}或者|I|=3時(shí)，解密S盒對應(yīng)的可分性軌跡TS-1(x|I，C)不是凸集，需要計(jì)算出此時(shí)KNOT逆S盒每一位的輸出表達(dá)式，然后利用“復(fù)制”“與”“異或”運(yùn)算的可分性模型來構(gòu)建此時(shí)的S盒的模型。

3.2 基于可分性和標(biāo)志位技術(shù)的KNOT-256置換可分性模型構(gòu)建方法

KNOT_Division_Encryption_one_Round(i，M，ai，bi，ai.F，bi.F)

和 KNOT_Division_Decryption_one_Round(i，M，ai，bi，ai.F，bi.F) ，

其中，參數(shù)i代表加密或解密的是第幾輪，參數(shù)M代表可分性的MILP模型，ai.F代表模型變量ai對應(yīng)的標(biāo)志位，bi.F代表模型變量bi對應(yīng)的標(biāo)志位。算法3給出了第i輪KNOT-256加密方向可分性的MILP模型構(gòu)建方法，解密方向與上述同理。

算法3第i輪KNOT-256加密的可分性MILP模型構(gòu)建方法。

① KNOT_Division_Encryption_one_Round(第i輪加密，模型M，ai，bi，ai.F，bi.F)：

②ai.F=ai.F⊕RC[i]。

③ 對于j從0到 63 重復(fù)執(zhí)行④：

⑤ 對于j從0到63重復(fù)執(zhí)行⑥到：

⑥I=[]，C=[]。

⑦ 對于j1從0到3，重復(fù)執(zhí)行⑧到⑩。

⑨ 將j1添加到集合I中；

算法4構(gòu)建KNOT-256置換的n1+n2輪零和區(qū)分器。

① KNOT_Zero_Sum_Distinguisher(n1，n2，V)：

② 定義兩個(gè)空的可分性模型Me和Md。

③ 對于集合{(0，256]-V}中的每一個(gè)元素i，重復(fù)執(zhí)行④到⑥：

⑦ 對于集合V中的每一個(gè)元素i，重復(fù)執(zhí)行⑧到⑨：

⑩ 對于i從0到n1- 1，構(gòu)建KNOT-256解密方向輪函數(shù)的可分性的MILP模型：

對于Wn1中的非活躍的位置，都賦值為常數(shù)0，利用算法4，可以得到20輪到30輪的KNOT-256的零和區(qū)分器。在相同的活躍位置的條件下，與不添加標(biāo)志位得到的結(jié)果進(jìn)行了對比，部分得到的結(jié)果見表6(求解器：Gurobi 8.0；編程語言：Python 2.7；運(yùn)行環(huán)境：Intel Core i7-5500U 2.4GHz)。

表6 KNOT-256零和區(qū)分器

(9)

通過上面的討論可知，在利用可分性質(zhì)構(gòu)造零和區(qū)分器的過程中，筆者提出的方法考慮了固定的常數(shù)對區(qū)分器的影響，而這種影響可以通過標(biāo)志位技術(shù)引入可分性的模型的構(gòu)造中。相比于普通的可分性建模方法，筆者構(gòu)建的模型更精確，并且求解的速度更快。但是，當(dāng)攻擊輪數(shù)進(jìn)一步提高后，由于在模型中加入了大量的限制條件，這樣會超過計(jì)算機(jī)的求解能力，從而導(dǎo)致模型求解的時(shí)間加長，甚至不能在有限的時(shí)間內(nèi)返回模型的解。這也是許多區(qū)分器自動化搜索算法面臨的問題。如何解決這個(gè)問題還需要進(jìn)一步研究。

4 結(jié)束語

筆者給出了分組密碼算法S盒的新可分性模型的構(gòu)建方法，同時(shí)基于KNOT-256算法的S盒性質(zhì)和算法結(jié)構(gòu)，設(shè)計(jì)了KNOT-256算法的零和區(qū)分器的自動化搜索方法。研究結(jié)果表明：KNOT-256置換存在30輪的零和區(qū)分器。盡管上面的分析不能對KNOT認(rèn)證加密算法的安全性構(gòu)成威脅(分組長度是256 bit的版本的初始化輪數(shù)為52輪)，但是給出了構(gòu)造KNOT算法零和區(qū)分器的新方法及實(shí)用分析工具。