周煜軒 曾連蓀
(上海海事大學(xué)信息工程學(xué)院 上海 201306)
Hash algorithm
近20年里,隨著便攜式設(shè)備的流行,數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)算法及其變體[1-3]在電子支票轉(zhuǎn)賬[4]、網(wǎng)絡(luò)設(shè)備[5]、嵌入式系統(tǒng)[6]等領(lǐng)域應(yīng)用廣泛。目前,對于DES算法變體的研究主要著眼于兩個(gè)方面:其一,DES算法采用56位加密密鑰,過短的密鑰長度易被暴力破解;其二,DES算法的內(nèi)部置換數(shù)組是靜態(tài)的,易被差分功耗分析(DPA)[7-13]。應(yīng)對的方案除了延長密鑰[14-15]外,還包括噪聲產(chǎn)生器[16]、雙軌電路[17]、隨機(jī)數(shù)掩碼[18]、流密碼[19]等。這些方案雖然提升了DES算法的安全性,但都沒有針對DES算法的置換數(shù)組的靜態(tài)特性進(jìn)行改進(jìn)。文獻(xiàn)[20]雖提出了一種基于時(shí)間戳的隨機(jī)數(shù)方案使DES算法的置換數(shù)組動(dòng)態(tài)化,但這種隨機(jī)數(shù)生成方案過于簡單。本文提出基于卷積算法[21]和延長密鑰的隨機(jī)數(shù)生成方案。在實(shí)現(xiàn)過程中,考慮到延長密鑰與原始DES算法的兼容性,本文還提出結(jié)合哈希算法[22]生成新哈希密鑰的方案,從而得到一種較復(fù)雜的動(dòng)態(tài)化DES算法變體。
本文從DES算法結(jié)構(gòu)與差分功耗分析進(jìn)行探討,論證該變體的抗暴力破解與抗差分功耗分析能力,對加密表現(xiàn)進(jìn)行對比,并分析其時(shí)間與空間復(fù)雜度。另外,本文還選擇與該變體近似的算法進(jìn)行運(yùn)行效率的對比,進(jìn)行論證分析。
在加密過程中,16次迭代是最核心的部分,其公式如下:
Li=Ri-1
(1)
Ri=Li-1⊕f(Ri-1,Ki)
(2)
f函數(shù)如圖1所示,其過程如下:
步驟1輸入第i輪開始前的中間值的右32位Ri-1和該輪的48位子密鑰Ki;
步驟2Ri-1依據(jù)E擴(kuò)展為48位,與子密鑰Ki進(jìn)行異或運(yùn)算;
步驟3步驟2的結(jié)果依據(jù)S盒壓縮為32位;
步驟4步驟3的結(jié)果再依據(jù)P改變位排列順序后再輸出32位數(shù)據(jù)。
圖1 f函數(shù)
DES算法步驟如圖2所示,流程如下:
步驟1輸入64位明文Plaintext以及64位密鑰Key。
步驟264位密鑰Key根據(jù)圖3的運(yùn)算,生成16輪的子密鑰{K1,K2,…,K16}。
步驟364位明文按照IP進(jìn)行初始置換,再分為左右32位L0和R0。
步驟4從L1和R1開始,執(zhí)行16次式(1)和式(2)的迭代,最終生成L16和R16。
步驟5合并L16與R16,再按照IP-1進(jìn)行逆置換,得到密文C并輸出。
圖2 DES算法流程
圖3 子密鑰生成過程
圖1-圖3中所有標(biāo)有*號(hào)的部分均為置換數(shù)組,圖2和圖3中按從上到下,從左到右的順序描述各置換數(shù)組:
(1) 對于任意64位數(shù)據(jù)X,初始置換數(shù)組IP和逆置換數(shù)組IP-1的對應(yīng)關(guān)系為:
IP(IP-1(X))=IP-1(IP(X))=X
(3)
它們分別為容量為64的數(shù)組,數(shù)組元素各不相同,其大小在1到64之間,對應(yīng)著明文的64位,用于改變數(shù)據(jù)位的排列順序。
(2)E的容量為48,除了改變數(shù)據(jù)位排列順序外,還用于將32位的數(shù)據(jù)擴(kuò)展為48位以加入與子密鑰的運(yùn)算。
(3) S盒的作用是把48位的數(shù)據(jù)壓縮為32位,該S盒共有8個(gè),每個(gè)S盒的容量為4行16列,即64,每行的元素大小在0到15之間且各不相同。48位數(shù)據(jù)分為8組6位的數(shù)據(jù),以第一個(gè)S盒為例(如圖4所示),其第一位與最后一位合并用于確定S盒的行,剩下的4位用于確定S盒的列,由此得到一個(gè)0到15的數(shù),即4位的值,從而達(dá)到壓縮的目的。
圖4 S盒壓縮
(4)P的容量為32,其作用主要用于改變數(shù)據(jù)位的排列順序。
(5)PC-1的容量為56,除了改變數(shù)據(jù)位排列順序外,還用于去除64位密鑰的奇偶校驗(yàn)位。
(6)LS的容量為16,對應(yīng)著每一輪數(shù)據(jù)循環(huán)左移的位數(shù)。
(7)PC-2的容量為48,用于將循環(huán)左移后的56位結(jié)果壓縮為48位,用于加入到運(yùn)算中。
(8) 以上提到的數(shù)組各元素的值可參閱文獻(xiàn)[1]。
由此部分可知,各個(gè)置換數(shù)組規(guī)模大小不一決定了DES算法在執(zhí)行時(shí)產(chǎn)生的功耗呈現(xiàn)規(guī)律性。
文獻(xiàn)[7]對智能卡執(zhí)行加密并以時(shí)間為采樣點(diǎn)對設(shè)備寄存器進(jìn)行功耗采集,從圖5可以看出DES算法功耗曲線的規(guī)律,其中16輪迭代可以清晰地看出來。
圖5 DES算法功耗曲線
2.2曲線區(qū)分函數(shù)D(C,b,Ks)
通過圖5的功耗曲線識(shí)別特定的加密環(huán)節(jié),區(qū)分函數(shù)基于此得以實(shí)施。文獻(xiàn)[7]中對區(qū)分函數(shù)D(C,b,Ks)的定義為:記錄加密后的密文C,依據(jù)Ks的值計(jì)算最后一輪迭代前(第16輪迭代前)的中間值的左32位L15的第b位的值,b∈[0,32]。根據(jù)圖6,該函數(shù)的推導(dǎo)公式如下:
R16=L15⊕f(R15,K16)=IP(C)r
(4)
L16=R15=IP(C)l
(5)
由式(4)和式(5)得:
L15=IP(C)r⊕f(IP(C)l,K16)
(6)
猜測密鑰Ks代入式(6)可計(jì)算猜測值L15s,由此得到以下公式:
D(C,b,Ks)=(L15s>>b-1)&0x1=
((IP(C)r⊕f(IP(C)l,Ks))>>b-1)&0x1
(7)
根據(jù)D函數(shù)的定義可知,該函數(shù)返回值為0和1,若采集功耗曲線m次,采集到的功耗曲線可依據(jù)該返回值分成兩類。由圖1的f函數(shù)流程可知,Ks可劃分為8組,以每組6位的方式進(jìn)行猜測,能夠明顯減少密鑰猜測的次數(shù)。
圖6 D函數(shù)作用范圍
由2.2可知,當(dāng)Ks錯(cuò)誤時(shí),第b位的值則不確定,在大樣本的作用下該位取0和1的概率相近,各約等于1/2,所有功耗采樣點(diǎn)的功耗都與D函數(shù)不相關(guān);當(dāng)Ks正確時(shí),與之對應(yīng)的第b位的值必然是確定的,即概率為1,對應(yīng)S盒處的采樣點(diǎn)功耗與D函數(shù)相關(guān),而其他采樣點(diǎn)與之不相關(guān)。因此,采用如下差分公式:
(8)
式中:Ti[j]表示m條功耗曲線中第i條功耗曲線的第j個(gè)采樣點(diǎn)的功耗。式(8)表示根據(jù)D(C,b,Ks)把m條曲線分類,對兩類曲線的各個(gè)樣本點(diǎn)的功耗取均值,再彼此相減,得到差分功耗曲線ΔD。
由此,差分功耗分析的完整流程為:
步驟1使用相同密鑰K,對m條明文進(jìn)行加密,采集m條功耗曲線T,并記錄相應(yīng)的密文C。
步驟2對任意Ks,根據(jù)式(7)計(jì)算D(C,b,Ks)的值。
步驟3根據(jù)式(8),計(jì)算差分曲線ΔD并觀察,當(dāng)Ks錯(cuò)誤時(shí),差分曲線ΔD的所有采樣點(diǎn)均趨于0;當(dāng)Ks正確時(shí),差分曲線ΔD在對應(yīng)S盒的采樣點(diǎn)處會(huì)出現(xiàn)尖峰(如圖7所示[7])。
圖7 差分功耗曲線
步驟4每組6位的Ks在經(jīng)過至多26次(64次)的窮舉后,得到正確的48位的第16輪子密鑰并輸出。
差分功耗分析的最終結(jié)果是得到加密過程中的用于迭代的48位子密鑰,由第1部分可知,得到該輪子密鑰后,剩余的子密鑰能夠按照相同的方法推算出來;得到兩輪以上的子密鑰后,根據(jù)圖3的逆過程窮舉計(jì)算可以確定56位密鑰的剩余6位,最終得到完整的密鑰。
卷積算法主要用于信號(hào)處理領(lǐng)域[21],該算法利用多個(gè)數(shù)值依據(jù)各自的權(quán)重得到單個(gè)數(shù)值,公式如下:
(9)
式中:B為新的數(shù)值數(shù)組;Core為卷積核數(shù)組;A為初始數(shù)組。
本文根據(jù)密鑰得到卷積核數(shù)組,再計(jì)算隨機(jī)數(shù)數(shù)組,流程如下:
步驟1輸入128位密鑰K,即容量為16的字符數(shù)組,初始化A為2行8列的二維數(shù)組,每一維數(shù)組分別存儲(chǔ)K的前8個(gè)字符和后8個(gè)字符。
步驟2根據(jù)圖8計(jì)算卷積核數(shù)組Core的4個(gè)值,圖中雙箭頭表示異或運(yùn)算。
圖8 卷積核生成
步驟3根據(jù)圖9利用初始數(shù)組A與卷積核數(shù)組Core,根據(jù)式(9)得到隨機(jī)數(shù)數(shù)組B的7個(gè)值并輸出B。
圖9 卷積生成隨機(jī)數(shù)
由1.2節(jié)可知,DES算法除去與置換數(shù)組IP對應(yīng)的逆置換數(shù)組IP-1后共有7個(gè),因此該隨機(jī)數(shù)方案適用于本文的動(dòng)態(tài)化需求。
哈希算法常見于數(shù)據(jù)庫檢索、數(shù)據(jù)校驗(yàn)與分布式存儲(chǔ)等用途中,其包含的兩個(gè)特性對本文的價(jià)值很大[22]:
(1) 不論輸入的字符串長度與數(shù)量,該算法最終輸出固定位數(shù)的哈希值;
(2) 輸入的字符串發(fā)生細(xì)微變化,輸出會(huì)發(fā)生大幅度的改變。
利用以上兩個(gè)特性,本文能夠?qū)崿F(xiàn)利用128位密鑰得到64位的密鑰以適應(yīng)DES算法加密密鑰長度的目的。Murmurhash2哈希算法在非加密算法中具有高運(yùn)算性能和低碰撞率的優(yōu)點(diǎn)[23],因此本文選擇此算法來處理密鑰。該算法除了密鑰作為輸入外,該算法還需接受隨機(jī)數(shù)種子作為參數(shù),本文結(jié)合自身需求給出此哈希算法流程:
步驟1輸入容量為16的字符數(shù)組,即128位密鑰K,64位隨機(jī)數(shù)種子seed。
步驟2初始化常值乘數(shù)m=0xc6a4a7935bd1e995,常值右移參數(shù)r=47以及64位初始哈希值h=seed⊕(16×m)。
步驟3將密鑰K分為兩組64位無符號(hào)整型數(shù)值Kl和Kr,由此計(jì)算h=((h⊕(((Kl×m)>>r)×m)×m)⊕(((Kr×m)>>r)×m))×m。
步驟4計(jì)算h=((h⊕(h>>r))×m)>>r并輸出h。
本文采用基于卷積算法生成隨機(jī)數(shù)的方法對DES算法的內(nèi)部置換數(shù)組動(dòng)態(tài)化,具體流程如下:
步驟1輸入128位密鑰K和64位明文Plaintext。
步驟2將密鑰K作為輸入傳遞給3.1節(jié)中的算法,得到容量為7的隨機(jī)數(shù)數(shù)組RN,其中RN[0]~RN[6]依次為1.2節(jié)中IP、E、P、PC-1、LS、PC-2、S盒所對應(yīng)的隨機(jī)數(shù)。
步驟3取密鑰K高64位為L,低64位為R,計(jì)算隨機(jī)數(shù)種子seed=R⊕L。
步驟4將128位密鑰K與隨機(jī)數(shù)種子seed作為輸入傳遞給3.2節(jié)的算法,計(jì)算64位哈希密鑰H。
步驟5初始化i=0。
步驟6如果RN[i]為奇數(shù),則對該隨機(jī)數(shù)對應(yīng)的置換數(shù)組進(jìn)行循環(huán)左移RN[i]次,i=i+1;否則循環(huán)右移RN[i]次,i=i+1。
步驟7如果i小于6,執(zhí)行步驟6。
步驟8根據(jù)變換后的初始置換數(shù)組IP生成與其對應(yīng)的逆置換數(shù)組IP-1。
步驟9初始化i=1。
步驟10將S盒看作32個(gè)規(guī)模為16的數(shù)組,對第i個(gè)數(shù)組,其對應(yīng)隨機(jī)數(shù)RN[6]+i-1,如果i大于32,執(zhí)行步驟13;否則,如果RN[6]+i-1為奇數(shù),執(zhí)行步驟11,反之執(zhí)行步驟12。
步驟11對第i個(gè)數(shù)組循環(huán)左移RN[6]+i-1次,i=i+1,執(zhí)行步驟10。
步驟12對第i個(gè)數(shù)組循環(huán)右移RN[6]+i-1次,i=i+1,執(zhí)行步驟10。
步驟13取明文Plaintext和哈希密鑰H作為輸入傳遞到1.2節(jié)的DES算法,輸出密文C。
步驟2中,本文基于卷積算法根據(jù)128位的延長密鑰來生成與1.2節(jié)中提到的各置換數(shù)組相對應(yīng)的一個(gè)隨機(jī)數(shù),組成隨機(jī)數(shù)數(shù)組RN;在步驟5至步驟7,本文判斷前6個(gè)置換數(shù)組各自對應(yīng)的隨機(jī)數(shù)的奇偶性,以此決定各個(gè)置換數(shù)組循環(huán)移動(dòng)的方向與次數(shù);因?yàn)镾盒的結(jié)構(gòu)相比其他置換數(shù)組不同,若是直接旋轉(zhuǎn)會(huì)使得每一行數(shù)組不再滿足1.2節(jié)中各元素彼此不同的條件,所以本文在步驟9至步驟10將S盒劃分為32個(gè)容量為16的數(shù)組,確保不破壞原有的結(jié)構(gòu);針對1.2節(jié)中式(3)里初始置換數(shù)組IP和逆置換數(shù)組IP-1的關(guān)系,本文在步驟8根據(jù)IP的數(shù)組元素來構(gòu)造對應(yīng)的IP-1。該變體的解密過程除了使用的子密鑰的順序與加密過程相反外,其余步驟均一致。
3.4.1抗暴力破解
文獻(xiàn)[24]列出了每微秒解密106次的運(yùn)算頻率(該速率高于現(xiàn)代CPU的運(yùn)算速率)下,不同長度密鑰的破解時(shí)間,如表1所示。
表1 不同密鑰長度窮舉時(shí)間
可以看出,窮舉128位密鑰需要5.4×1018年,因此該變體能夠有效地抗暴力破解。
3.4.2抗差分功耗分析
定理1若DES算法的置換數(shù)組未知,則該算法能夠抗差分功耗分析。
證明假設(shè)DES算法的置換數(shù)組未知時(shí),該算法能夠被差分功耗分析。
若該算法能夠被差分功耗分析,即2.3節(jié)中差分功耗曲線ΔD存在,則式(8)中各變量已知,所以區(qū)分函數(shù)D(式(7))已知;
由式(7)可知,f函數(shù)與初始置換數(shù)組IP已知;
又由圖1和式(3)分別可知,擴(kuò)展數(shù)組E、S盒數(shù)組、內(nèi)置換數(shù)組P與逆置換數(shù)組IP-1已知;
由2.3節(jié)的子密鑰剩余6位窮舉過程可知,密鑰置換數(shù)組PC-1、PC-2和循環(huán)左移數(shù)組LS已知;
所以置換數(shù)組IP、IP-1、E、S盒、P、PC-1、PC-2和LS是已知的,這與假設(shè)矛盾,因此得證。
由于所有置換數(shù)組的組合為64!+56!+2×48!+32!+16!+32×16!=1.268 869 322×1089種,對該數(shù)量級的置換數(shù)組組合進(jìn)行窮舉顯然是不可能的。
綜合定理1與置換數(shù)組窮舉的數(shù)量級,該變體能夠抗差分功耗分析。
3.4.3均勻性測試
本文的測試平臺(tái)為Ubuntu 18.04 64位操作系統(tǒng),利用C語言以及gcc組件實(shí)現(xiàn)測試。
均勻性指改進(jìn)后的加密算法的密文,以明文作為參照,改變的位數(shù)要與改進(jìn)前相近,同時(shí)發(fā)生改變的位應(yīng)分布到每一個(gè)字節(jié)(8位)中。本文隨機(jī)生成50組明文,分別用改進(jìn)前后的算法進(jìn)行加密,并與明文對比,得到兩者的最大值、最小值及均值,并生成兩者改變位數(shù)的曲線圖;另外,對該變體的變化位圖進(jìn)行記錄,由于篇幅原因且各組位圖呈現(xiàn)相似的分布,本文給出前4組密文的變化位圖。
測試結(jié)果顯示:改進(jìn)前后密文變化位數(shù)的最小值相近,改進(jìn)后的最大值與均值均高于改進(jìn)前,且改進(jìn)后的變化位數(shù)接近明文半數(shù)(表2);對比各明文對應(yīng)的密文的變化位數(shù),其曲線波動(dòng)也相近(圖10);表3中,“-”代表該位未發(fā)生改變,“*”代表該位發(fā)生改變。該位圖表明,密文的每8位里均發(fā)生位的改變,即發(fā)生變化的位分布到各個(gè)字節(jié)中。因此該變體滿足均勻性需求。
表2 改進(jìn)前后改變位數(shù)最大值、最小值及均值
圖10 均勻性測試曲線
表3 密文變化位圖
續(xù)表3
3.4.4雪崩效應(yīng)
雪崩效應(yīng)指即使明文發(fā)生1位的改變,彼此對應(yīng)的密文之間也會(huì)發(fā)生接近半數(shù)的位變化。
本文以16進(jìn)制明文0x6867666564636261對應(yīng)的密文作為參照,依次對其第1-64位進(jìn)行改變,用改進(jìn)前后的算法分別加密,與參照密文對比,變化曲線如圖11所示;并計(jì)算兩者位變化數(shù)的最大值、最小值與平均值,結(jié)果如表4所示。同樣地,本文給出變化位圖的前4組,如表5所示,并對發(fā)生變化的16進(jìn)制位進(jìn)行加粗顯示,以此驗(yàn)證雪崩效應(yīng)。
圖11 雪崩測試曲線
表4 改變1位的密文變化數(shù)最大值、最小值及均值
表5 改變1位的密文變化位圖
結(jié)果顯示:改進(jìn)前后的最小值也相近,改進(jìn)后的最大值與均值也高于改進(jìn)前(表4)且發(fā)生接近半數(shù)的位變化; 由圖11可看出改進(jìn)前后的變化曲線相近;表5中變化位圖以參照密文作為依據(jù),分別對比各密文發(fā)生的改變,可以看出,明文改變1位后其密文變化也分布到各個(gè)字節(jié)中。因此該變體也滿足雪崩效應(yīng)需求。
3.4.5時(shí)間復(fù)雜度
本文的改進(jìn)策略是在原有的DES算法上引入卷積算法與哈希算法。在3.1節(jié)中,卷積核容量與卷積運(yùn)算次數(shù)均已知,所以時(shí)間復(fù)雜度為O(1);在3.2節(jié)中,哈希算法的時(shí)間復(fù)雜度也為O(1)。結(jié)合第1部分的DES算法的原時(shí)間復(fù)雜度為O(1),該變體的時(shí)間復(fù)雜度為O(1)+O(1)+O(1),即O(1),保持了原有算法的時(shí)間復(fù)雜度。
3.4.6空間復(fù)雜度
由第1部分可知,DES算法的輔助存儲(chǔ)空間為常量,即原空間復(fù)雜度為O(1)。該變體除了分配與DES算法相同的輔助存儲(chǔ)外,還會(huì)額外地分配卷積算法和哈希算法的輔助存儲(chǔ)內(nèi)存。而卷積算法和哈希算法也是常量存儲(chǔ),因此該變體空間復(fù)雜度仍為O(1),保持了原有算法的空間復(fù)雜度。
綜上,該變體能夠有效抗暴力破解與差分功耗分析,同時(shí)滿足了加密算法應(yīng)具備的基本要求(均勻性與雪崩效應(yīng)),也保持了原有的時(shí)間復(fù)雜度和空間復(fù)雜度。
3.4.7近似算法運(yùn)行效率對比
本文運(yùn)行效率測試平臺(tái)為64位Ubuntu18.04,利用C語言編寫,CPU頻率和運(yùn)行內(nèi)存分別為2.40 GHz和8 GB。
鑒于TEA[25](Tiny Encryption Algorithm)與3DES算法的加密明文為64位,加密密鑰為128位,與本文變體相一致,本文選擇這兩種算法與本文變體進(jìn)行運(yùn)行效率對比。另外,本文還給出DES算法與本文提及的Murmurhash2算法的運(yùn)行效率,討論Murmurhash2的引進(jìn)對算法運(yùn)行效率的影響。本文利用前四種算法分別對1 000組64位不同的明文類型重復(fù)加解密50次,利用Murmurhash2對1 000組128位不同的明文類型重復(fù)加密50次再取平均值,得出運(yùn)行效率如表6所示。
表6 DES及各變體運(yùn)行時(shí)間
續(xù)表6
由表6可知,TEA的運(yùn)行效率極高,這是因?yàn)槠渥鳛樽詈唵蔚腇eistel結(jié)構(gòu)加密算法之一,不包含查表變換等一系列操作[25],因此以此算法為基準(zhǔn)能夠清晰地表達(dá)本文變體與3DES的運(yùn)行時(shí)間上的增值。而本文變體的運(yùn)行效率介于DES算法與3DES算法之間,這表明針對DES算法的改進(jìn)產(chǎn)生的運(yùn)行時(shí)間增值主要體現(xiàn)在查表變換等操作上,而非Feistel結(jié)構(gòu)上,因此本文采用與3DES算法不同的改進(jìn)策略,動(dòng)態(tài)化置換數(shù)組,減少DES加解密的次數(shù),從而達(dá)到比3DES算法更高的運(yùn)行效率。另外,從Murmurhash2算法的運(yùn)行時(shí)間看來,其對整個(gè)改進(jìn)方案的運(yùn)行效率影響非常小,加之哈希算法的不可逆性,這兩者是本文將其加入到變體方案的原因。
本文提出基于卷積隨機(jī)數(shù)與哈希變換的動(dòng)態(tài)化DES算法變體。延長原有DES算法的密鑰長度,并依據(jù)延長密鑰基于卷積算法產(chǎn)生7個(gè)隨機(jī)數(shù),依次對應(yīng)不同的置換數(shù)組,執(zhí)行相應(yīng)的動(dòng)態(tài)策略,進(jìn)而能夠抗暴力破解與差分功耗分析;另一方面基于Murmurhash2哈希算法根據(jù)延長密鑰生成新的哈希密鑰,進(jìn)而保持原加密算法的基本特性。這兩種方式彼此不相關(guān),無法彼此推算,攻擊該變體需同時(shí)窮舉密鑰和置換數(shù)組,因此該算法的安全性得以提升。另外,與3DES算法相比,該變體還擁有更高的運(yùn)行效率。