王濤
(全球能源互聯(lián)網(wǎng)研究院,北京102209)
本文設(shè)計(jì)的Electricity(電力輕量級(jí)分組密碼)算法是一個(gè)迭代型的分組密碼,整體結(jié)構(gòu)為SP(substitution-permutation,代換、置換)網(wǎng)絡(luò),分組長(zhǎng)度為64 bit,密鑰長(zhǎng)度有64 bit、80 bit和128 bit共計(jì)3種可選值,對(duì)應(yīng)的輪數(shù)分別為16輪、18輪和20輪。電力輕量級(jí)分組密碼是一個(gè)硬件實(shí)現(xiàn)與軟件實(shí)現(xiàn)均有極佳性能,且安全性可靠的輕量級(jí)分組密碼算法。
相較LED密碼(一種輕型分組密碼算法),選用了硬件實(shí)現(xiàn)面積更優(yōu)的S盒和列混淆變換。這使得在相同實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)策略下,電力輕量級(jí)分組密碼更為輕量,即硬件面積需求更低。在一定硬件環(huán)境下,Electricity-80可以在1000 GE以下實(shí)現(xiàn)。
在很多輕量級(jí)密碼的應(yīng)用中,密鑰需要固化到硬件中。此外,輕量級(jí)密碼的一些應(yīng)用也需要同一密碼算法具有較好的軟件實(shí)現(xiàn)性能,而不僅僅是低的硬件面積。鑒于上述應(yīng)用需求,通過(guò)設(shè)計(jì)密鑰擴(kuò)展算法來(lái)保護(hù)算法,以抵抗相關(guān)密鑰攻擊。這樣的改變,在保證適度安全強(qiáng)度的前提下,只以較小的硬件面積增加(即密鑰擴(kuò)展算法的額外開(kāi)銷(xiāo))來(lái)?yè)Q取軟件速度的提升和硬件性能的提高,使電力專(zhuān)用算法兼有更好的軟件和硬件實(shí)現(xiàn)性能。
通過(guò)分析電力專(zhuān)用算法針對(duì)一些重要分析方法的安全性,得出電力專(zhuān)用算法具有充足的安全強(qiáng)度,能夠抵抗現(xiàn)有的已知安全性分析方法。
Electricity是迭代型的分組密碼,其為Rijndael-like(Rijndael算法是美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)協(xié)會(huì)即NIST所選的高級(jí)加密標(biāo)準(zhǔn)(AES)的候選算法)的SP網(wǎng)絡(luò)結(jié)構(gòu),分組長(zhǎng)度為64 bit,密鑰長(zhǎng)度有3種可選值:64 bit、80 bit、128 bit,3種密鑰長(zhǎng)度對(duì)應(yīng)的輪數(shù)分別為16輪、18輪與20輪。
算法將64 bit明文分組載入中間狀態(tài)寄存器,表示為M=m0||m1||…||m63。以下分別介紹加密過(guò)程與解密過(guò)程所用的有關(guān)結(jié)構(gòu)與數(shù)據(jù)。
在進(jìn)行后續(xù)加密操作前,首先用輪密鑰K0對(duì)其進(jìn)行一次輪密鑰加運(yùn)算,然后進(jìn)行R(R是對(duì)3種不同密鑰長(zhǎng)度的變體,R分別為16、18與20)輪加密運(yùn)算,最后將寄存器內(nèi)的值作為密文分組輸出。算法的每一輪分為4步:nibble代換s、行移位r、列混淆ρ、輪密鑰加πKi。于是輪函數(shù)可以寫(xiě)作fi=πKiiρr s,其中i為輪數(shù)。
nibble代換s:該步將中間狀態(tài)M=m0||m1||…||m63,看作16個(gè)4 bit nibble n0||n1||…||n15。
對(duì) 每 個(gè)0≤i≤15,ni=(mi×4,mi×4+1,mi×4+2,mi×4+3); 將 每 個(gè)nibble ni的值用經(jīng)由4×4的4 bit S盒S:運(yùn)算后所得的值代替。
對(duì)每個(gè)0≤i≤15,(mi×4,mi×4+1,mi×4+2,mi×4+3):=S(ni)=S(mi×4,mi×4+1,mi×4+2,mi×4+3),S盒以16進(jìn)制表示,見(jiàn)表1。
行移位γ:該步中,將中間狀態(tài)n0||n1||…||n15看作4×4的4 bit nibble矩陣:
表1 加密置換
對(duì)于i=0,1,2,3,將矩陣的第i行循環(huán)左移i個(gè)nibble的位置。
列混淆ρ:該步中MDS矩陣用于線性擴(kuò)散,該矩陣的設(shè)計(jì)原理見(jiàn)第3.2節(jié);具體可視為矩陣的連續(xù)4次運(yùn)用。如上,將中間狀態(tài)看作4×4的4 bit nibble矩陣,然后用矩陣A進(jìn)行4次左乘。選取一個(gè)合適的作用于nibble之上的4×4的4 bit線性變換L,則矩陣A與最終的MDS矩陣W可寫(xiě)作:
輪密鑰加π:該步將輪密鑰Ki=ki0ki1…ki63與中間狀態(tài)值做異或運(yùn)算,用所得的結(jié)果更新?tīng)顟B(tài)寄存器。
解密過(guò)程中,按與加密過(guò)程相反的次序運(yùn)用各輪輪密鑰,即在解密過(guò)程開(kāi)始前,首先運(yùn)用子密鑰Kr進(jìn)行輪密鑰加,然后經(jīng)過(guò)R輪解密輪,得出明文分組。加密過(guò)程輪函數(shù)為fi=πKiiρr s,則解密輪函數(shù)為fi-1=πKR-is-1ir-1ρ-1,此處的i表示第i次運(yùn)用解密輪函數(shù),其中應(yīng)用的密鑰為子密鑰KR-i。
列混淆逆ρ-1:該步中同樣可視為矩陣A的逆矩陣A-1的連續(xù)4次(左乘)運(yùn)用,A-1利用L的逆變換L-1定義如下:
行移位 逆r-1:將中間狀 態(tài)n0||n1||…||n15看作4×4的4 bit nibble矩陣,對(duì)于i=0,1,2,3,將矩陣的第i行循環(huán)右移i個(gè)nibble的位置。
nibble代換逆s-1:所用的4×4的4 bit逆S盒以16進(jìn)制表示,見(jiàn)表2。
表2 解密置換
Electricity的密鑰長(zhǎng)度可選為64 bit、80 bit或128 bit,處理過(guò)程統(tǒng)一描述如下。
將k比特主密鑰看作ω?cái)?shù)目的4 bit nibble,寫(xiě)作V=v0||v1||…||vk=n0||n1||…||nω。首先將其載入k bit密鑰寄存器R=n0||n1||…||nω=r0||r1||…||rk=v0||v1||…||vk,將 寄 存 器 中 前64 bit取出作為輪密鑰K0:K0=k00k01…k063=r0||r1||…||r63(=v0||v1||…||v63),然后對(duì)于i=1,…,r來(lái)說(shuō),對(duì)密鑰寄存器進(jìn)行如下更新與取輪密鑰操作。
加輪常量:將5 bit LFSR初始化為全1值(l0,l1,l2,l3,l4)=(1,1,1,1,1),首先依據(jù)反饋多項(xiàng)式x5+x3+1對(duì)其進(jìn)行更新,然 后 將 其 值 異 或 到 密 鑰 寄 存 器 的 前5 bit中,(r0′,r1′,r2′,r3′,r4′)=(r0茌l0,r1茌l1,r2茌l2,r3茌l3,r4茌l4)。以 后 每 輪 都 首 先 依 據(jù)x5+x3+1更新LFSR狀態(tài),再進(jìn)行異或操作。
nibble代換:將k bit密 鑰寄存器 看 作4×λ的4 bit nibble矩陣。
行移位:與加密過(guò)程相似,該步將密鑰寄存器看作4×λ的4 bit nibble矩陣,當(dāng)主密鑰長(zhǎng)度為64 bit和128 bit時(shí),對(duì)于i=0,1,2,3,將矩陣的第i行循環(huán)左移i個(gè)nibble的位置;當(dāng)主密鑰長(zhǎng)度為80 bit時(shí),對(duì)于i=0,1,2,3,將矩陣的第i行循環(huán)左移i+3個(gè)nibble的位置。
列混淆:與加密過(guò)程相似,該步用矩陣A對(duì)輪密鑰nibble矩陣進(jìn)行4次左乘,所用矩陣A與加密過(guò)程中所用A相同。
取i輪輪密鑰:取密鑰寄存器的前64 bit作為第i輪的輪密鑰,即Ki=ki0ki1…ki63=r0||r1||…||r63。
對(duì)長(zhǎng)度不足64 bit的數(shù)據(jù)分組,要先對(duì)其進(jìn)行10×1式填充,即先填充一個(gè)比特1,再填充足夠多的比特0,最后填充一個(gè)比特1,將其補(bǔ)足為64倍數(shù)比特(64或128),詳細(xì)算法如下。
算法1數(shù)據(jù)填充算法
輸入 長(zhǎng)度少于64 bit的數(shù)據(jù)塊m。
輸出 長(zhǎng)度為64 bit或者128 bit的填充數(shù)據(jù)塊p。
if長(zhǎng)度of m是63
Rijndael自其誕生并被選為AES標(biāo)準(zhǔn)以來(lái),受到了廣泛的分析,實(shí)踐證明其承受住了絕大部分的考驗(yàn)。在其基礎(chǔ)上發(fā)展出了Rijndael-like結(jié)構(gòu),其定義如下。
定義1 Rijndael-like結(jié)構(gòu):指滿足下述條件的SP網(wǎng)絡(luò)型分組密碼:
·其線性變換形式為(θ1,θ2,θ3,θ4)π;
·(π的條件)yi的各nibble來(lái)自不同的xi,其中x=(x1,x2,x3,x4)是π的輸入,y=(y1,y2,y3,y4)是π的輸出,即對(duì)于坌i=0,1,2,3,yi的4個(gè)nibble分別來(lái)自x0、x1、x2與x3;
·(θ=(θ1,θ2,θ3,θ4)的 條 件)將 各θi看作線性變換,則要求分 別 是線性變換θi在差分與線性分析中的分枝數(shù)目(branch number)。
對(duì)于Rijndael-like結(jié)構(gòu),其各種安全參數(shù)已有較完備的分析,得出了大量安全界?;诖?,本方案延用Rijndael-like結(jié)構(gòu)作為基礎(chǔ)。
輕量級(jí)密碼學(xué)方案中,為了較好地兼顧安全性與性能,常選用4 bit×4 bit的S盒,選擇依據(jù)如下。
·最大差分概率為2-2:
·最大線性偏差為2-2:
·沒(méi)有不動(dòng)點(diǎn)。
·代數(shù)次數(shù)達(dá)到最大值3。
·硬件實(shí)現(xiàn)面積小。
最終選定的S盒,硬件實(shí)現(xiàn)只需8次操作,共計(jì)約15.01 GE:
AES的設(shè)計(jì)過(guò)程中,提出了線性變換/擴(kuò)散層(diffusion layer)分枝數(shù)目的概念,含義是差分值/線性掩碼經(jīng)線性變換后,輸入輸出值中不為0的S盒的最小數(shù)目。分枝數(shù)目越大,擴(kuò)散層的擴(kuò)散效果越好。對(duì)S盒數(shù)目為s的加密方案而言,其分枝數(shù)目為s+1。將達(dá)到了此數(shù)值的線性變換稱(chēng)為完美擴(kuò)散層(perfect diffusion layer)。
已經(jīng)證明,當(dāng)[m,s,d]碼的生成矩陣所有的子方陣均為非奇異矩陣時(shí),該碼是MDS碼,這一性質(zhì)可用于檢驗(yàn)所構(gòu)造的線性變換是否完美(達(dá)到分枝數(shù)目)。實(shí)際構(gòu)造這樣的矩陣時(shí),一方面希望構(gòu)造過(guò)程簡(jiǎn)明,另一方面希望構(gòu)造的矩陣有較為簡(jiǎn)單的硬件實(shí)現(xiàn),一種構(gòu)造方式是利用多個(gè)基于bundle(bundle-based)的LFSR(linear feedback shifting register,一種流密碼技術(shù)),經(jīng)過(guò)d次更新,實(shí)現(xiàn)線性變換。在這種構(gòu)造方式下,最終的線性變換矩陣D就是這些LFSR的狀態(tài)轉(zhuǎn)移矩陣A的d次冪:D=Ad。本方案選取的就是這樣一個(gè)矩陣:
矩陣D是作用于4個(gè)4 bit bundle上的矩陣(16 bit),其中的矩陣L則是作用于4 bit bundle上的矩陣。若L選為有且僅有4個(gè)1的可逆矩陣,則D成為比特置換,而實(shí)際傾向于選取硬件實(shí)現(xiàn)面積最小且滿足最終構(gòu)造的矩陣D是MDS矩陣的L。
上述矩陣D是MDS矩陣的條件是其所有子方陣都非奇異,這樣可以計(jì)算得出7個(gè)條件,即下述7個(gè)矩陣均非奇異:L、L+1、L2+L+1、L3+L+1、L3+L2+1、L4+L3+1、L4+L3+L2+L+1。
這個(gè)L硬件實(shí)現(xiàn)時(shí)僅需要若干布線與一個(gè)異或門(mén),其開(kāi)銷(xiāo)很低。總的來(lái)看,此時(shí)矩陣D的硬件實(shí)現(xiàn)需2n+2數(shù)目的異或門(mén)電路,在同類(lèi)變換中是最低的,且達(dá)到4-bundle線性變換的分枝數(shù),在性能與安全性兩方面都十分出色。
本方案的密鑰編排設(shè)計(jì)遵循如下理念:
(1)在編排過(guò)程中使用非線性變換以增加安全強(qiáng)度,降低相關(guān)密鑰攻擊的可能性;
(2)在(1)的前提下,使用盡量少的S盒,以減少硬件實(shí)現(xiàn)開(kāi)銷(xiāo),方案中每次只對(duì)狀態(tài)寄存器中1/4的4 bit單元運(yùn)用S盒;
(3)編排過(guò)程盡量使用加密過(guò)程中使用的部件,以便實(shí)現(xiàn)時(shí)共用部件,降低實(shí)現(xiàn)開(kāi)銷(xiāo);
(4)引入與輪數(shù)相關(guān)的量以抵御slide attack(滑動(dòng)攻擊)。
綜合上述幾點(diǎn),最終選用了第2.3節(jié)、第3.3節(jié)所述的編排方案。
本節(jié)從差分概率/線性閉包偏差上界、密鑰編排安全性等方面分析本方案的安全性。
對(duì)Rijndael-like結(jié)構(gòu)的差分概率/線性閉包偏差上界已有較完善的研究,這樣的設(shè)計(jì)不僅若干輪的單條軌跡概率/偏差很低,甚至連多條跡聚合而成的概率/偏差也不會(huì)很高。
具體地,對(duì)于2輪的SPN結(jié)構(gòu),差分方面有如下定理。
定理1若L的差分分枝數(shù)為βd,則2輪SPN結(jié)構(gòu)的差分概率上界為:
其中,DPSi(u,j)是第i個(gè)S盒將輸入差分u映射到輸出差分j的概率。將本方案的S盒差分分布數(shù)據(jù)代入式(7),計(jì)算得出2輪差分對(duì)概率不超過(guò)2-8;再依照與定理1中類(lèi)似的分析過(guò)程,可得本方案4輪差分對(duì)的概率不超過(guò)2-32。
線性方面,定義相關(guān)系數(shù)為兩倍的線性偏差,則有如下定理。
定理2若L的線性分枝數(shù)為βl,則2輪SPN結(jié)構(gòu)的線性相關(guān)系數(shù)平方上界為:
此處LPSi(u,j)是掩碼對(duì)(u,j)在第i個(gè)S盒上的相關(guān)系數(shù)平方值。將本方案的S盒線性參數(shù)代入式(8),計(jì)算得出2輪線性掩碼的相關(guān)系數(shù)平方值不超過(guò)2-8;再依與定理2中類(lèi)似的分析過(guò)程,可得出本方案4輪線性掩碼的相關(guān)系數(shù)平方值不超過(guò)2-32。此處的計(jì)算結(jié)果在值上與差分方面是相等的。
高階差分攻擊利用某些加密方案代數(shù)次數(shù)相對(duì)較低的特點(diǎn),將高階差分值作為區(qū)分依據(jù),當(dāng)加密方案輸出結(jié)果的某個(gè)比特可以寫(xiě)作輸入比特的n次多項(xiàng)式時(shí),方案輸出值的階差分值在該比特位點(diǎn)上是常數(shù)。插值攻擊和代數(shù)攻擊也利用這種相對(duì)較低的代數(shù)次數(shù):插值攻擊通過(guò)插值法求解輸出比特或中間比特的多項(xiàng)式表達(dá)式,實(shí)施區(qū)分;代數(shù)攻擊則在輸入比特、密鑰比特與輸入比特之間建立二次代數(shù)方程組,設(shè)法通過(guò)求解方程組完成密鑰的恢復(fù)。
鑒于本方案采用的S盒代數(shù)次數(shù)最高為3,僅在部分輸出上為2,即使在最不利的情形下,經(jīng)7輪以上后,各輸出比特表達(dá)為輸入比特的代數(shù)形式后,次數(shù)也已達(dá)到27=128,這意味著至少要2128數(shù)目的明文才能得到固定值的高階(128階)差分;鑒于方案的分組長(zhǎng)度僅為64 bit,獲取這么多的明文是不可能的??紤]到方案的實(shí)際輪數(shù)超過(guò)16輪,各經(jīng)過(guò)改進(jìn)的高階差分變體成功的可能性也是極低的。
鑒于類(lèi)似的考量,也無(wú)法得到實(shí)施插值攻擊所需的數(shù)據(jù)規(guī)模。在代數(shù)攻擊方面,則會(huì)因?yàn)榇螖?shù)過(guò)高、方程組規(guī)模過(guò)大而無(wú)法進(jìn)行。
涉及密鑰編排的攻擊包括slide attack、相關(guān)密鑰攻擊與中間相遇攻擊等。為了抵御slide attack,設(shè)計(jì)中引入了與輪數(shù)相關(guān)的常量,因此這種攻擊成功的可能性不大;由于輪函數(shù)采用了Rijndael-like結(jié)構(gòu),引入的差分會(huì)迅速擴(kuò)散,因此相信相關(guān)密鑰攻擊也不太可能;而對(duì)于中間相遇攻擊,由于Rijndael-like結(jié)構(gòu)中各比特的值會(huì)隨nibble迅速擴(kuò)散開(kāi),因此不太可能找到對(duì)較多輪數(shù)有效的中立密鑰比特,也就無(wú)法高效地實(shí)施中間相遇攻擊。
本方案采用的結(jié)構(gòu)與各部件都已有較完善的討論。根據(jù)已有成熟結(jié)論,給出本方案的串行化硬件實(shí)現(xiàn)結(jié)構(gòu),其64 bit變體的實(shí)現(xiàn)如圖1所示(datapath為4 bit,密鑰編排部分與加密部分很相似)。
考慮上述實(shí)現(xiàn)的硬件面積。加密部分的狀態(tài)框內(nèi)含16個(gè)4 bit存儲(chǔ)單元,其中實(shí)線框?yàn)殡p輸入的單元,平均每比特存儲(chǔ)約需6 GE,虛線框?yàn)閱屋斎氲膯卧?,平均每比特可以僅使用約4.67 GE;密鑰編排模塊的64 bit存儲(chǔ)與之類(lèi)似;S盒約需15.01 GE;列混淆模塊總計(jì)約需26.7 GE;用于生成常量的5 bit LFSR約需26.02 GE;控制邏輯需一個(gè)idle、一個(gè)控制初始的數(shù)據(jù)載入、一個(gè)控制輪密鑰加與代換、3個(gè)控制行移位、2個(gè)控制列混淆,總計(jì)8個(gè)狀態(tài);此外,需3 bit的LFSR作為轉(zhuǎn)移條件,總計(jì)約需80 GE。再考慮數(shù)據(jù)處理過(guò)程中用到的異或與片選組件,估計(jì)總計(jì)約需916.28 GE;其中控制邏輯約占8.73%。這樣的實(shí)現(xiàn)每輪約需39個(gè)時(shí)鐘周期,因此16輪加密總計(jì)需624個(gè)時(shí)鐘周期。
其中L與S盒都是4 bit輸入、4 bit輸出的元件,模塊L的細(xì)節(jié)如圖2所示。
圖2 模塊L的實(shí)現(xiàn)示意
在上述實(shí)現(xiàn)中,加密與密鑰編排部分分別用了兩個(gè)列混淆模塊與S盒,還有一種高度串行的實(shí)現(xiàn)方法是令加密與密鑰編排部分共用同一個(gè)列混淆與S盒,但實(shí)踐發(fā)現(xiàn),這種實(shí)現(xiàn)看似節(jié)約了兩個(gè)加密模塊,卻要額外使用多個(gè)片選電路,且增加控制邏輯的規(guī)模與復(fù)雜度,加倍加密所需的時(shí)鐘周期數(shù)目,實(shí)際能減少的實(shí)現(xiàn)面積卻極為有限,因此不予討論。
8 0 bit與128 bit的變體在硬件實(shí)現(xiàn)架構(gòu)上與64 bit變體是相似的,不同點(diǎn)在于密鑰編排部分需要更多的狀態(tài)寄存器。此外,由于每輪密鑰編排中全部完成列混淆運(yùn)算所需的時(shí)鐘周期數(shù)目不相同(64 bit分組需4×4+4=20個(gè)周期,80 bit密鑰狀態(tài)需5×4+5=25個(gè)周期,128 bit密鑰狀態(tài)需8×4+8=40個(gè)周期)。對(duì)于128 bit密鑰的變體,由于密鑰編排多出的周期數(shù)目40為4的倍數(shù),尚可在此期間內(nèi)令數(shù)據(jù)狀態(tài)寄存器反復(fù)循環(huán)移位來(lái)消耗時(shí)間;對(duì)于80 bit密鑰變體,多出的5個(gè)時(shí)鐘周期則難處理,為此將其在行移位階段設(shè)計(jì)成移動(dòng)位,以便用多出的3個(gè)周期將其補(bǔ)齊。這樣最終推算結(jié)果見(jiàn)表3。
利用SSE指令實(shí)現(xiàn)的本方案實(shí)例在便攜計(jì)算機(jī)上進(jìn)行了軟件實(shí)現(xiàn)性能測(cè)試實(shí)驗(yàn)。該便攜機(jī)處理器為Intel i5-2400,主頻為2.5 GHz,內(nèi)存為4 GB。Electricity軟件實(shí)現(xiàn)性能數(shù)據(jù)見(jiàn)表4。
圖1 硬件實(shí)現(xiàn)示意
表3 Electricity硬件實(shí)現(xiàn)性能
表4 Electricity軟件實(shí)現(xiàn)性能數(shù)據(jù)
得益于S盒與MDS矩陣研究的后期進(jìn)展,本方案獲得了相對(duì)已有方案而言極有競(jìng)爭(zhēng)力的硬件實(shí)現(xiàn)面積。選取了合適的輪數(shù)后,本方案的硬件實(shí)現(xiàn)加密延時(shí)得到控制,這方面優(yōu)于LED很多,加之各部件面積的優(yōu)化,整體硬件實(shí)現(xiàn)面積也優(yōu)于LED。
[1]QIU S,BAI G Q,CHEN H Y.One-dimensional confusion coefficient for block cipher[J].Journal of Cryptologic Research,2014,1(2):124-133.
[2]ZHOU Y B,LI J T,LIU J Y.The evolution of security requirements for cryptographic modules:the status quo,dilemma and future trends[J].Journal of Chengdu University of Information Technology.2011,26(2):109-122.
[3]ZHANG S Y,CHEN G L,FAN L,et al.Algorithm of G-AES[J].Journal of Cryptologic Research,2014,1(2):187-199.
[4]LIU Y Z,ZHANG L,LUO P,et al.Research of trustworthy software system in the network[C]//The 5th International Symposium on Parallel Architectures,Algorithms and Programming,December 17-20,2012,Taipei,China.New Jersey:IEEE Press,2012:287-294.
[5]HONG D,SUNG J,HONG S,et al.HIGHT:a new block cipher suitable for low-resource device[M].Berlin:Springer,2006:46-59.
[6]Leander G,PAAR C,POSCHMANN A,et al.New lighweight DES variants[J].Fast Software Encryption 2007-FSE 2007,4593:196-210.
[7]BOGDANOV A,KNUDSEN L R,LEANDER G,et al.PRESENT:an ultra-lightweight block cipher[J].Lecture Notes in Computer Science,2007(4727):450-466.