• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

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

      2021-01-29 04:30:58韋永壯李靈琛
      關(guān)鍵詞:區(qū)分解密標(biāo)志

      葉 濤,韋永壯,李靈琛

      (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è)問題??煞中允菑V義的積分性質(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í)用分析工具。

      猜你喜歡
      區(qū)分解密標(biāo)志
      區(qū)分“旁”“榜”“傍”
      解密“熱脹冷縮”
      你能區(qū)分平衡力與相互作用力嗎
      多功能標(biāo)志桿的使用
      解密“一包三改”
      炫詞解密
      認(rèn)標(biāo)志
      啟蒙(3-7歲)(2019年5期)2019-06-27 07:24:50
      首都的標(biāo)志是只熊
      教你區(qū)分功和功率
      醫(yī)改進(jìn)入新階段的重要標(biāo)志
      西乌| 郓城县| 房产| 汝城县| 景德镇市| 延寿县| 弋阳县| 秦皇岛市| 湾仔区| 桐梓县| 共和县| 樟树市| 克东县| 靖江市| 新密市| 竹北市| 安达市| 巴彦淖尔市| 旬邑县| 高清| 墨江| 抚远县| 郎溪县| 宝应县| 玛曲县| 衡南县| 蛟河市| 手机| 全州县| 琼结县| 吴川市| 阳城县| 怀宁县| 长治市| 雷州市| 新田县| 烟台市| 旬阳县| 新平| 九龙坡区| 洪泽县|