動態(tài)化DES算法變體研究

周煜軒 曾連蓀

(上海海事大學信息工程學院 上海 201306)

Hash algorithm

0 引 言

近20年里，隨著便攜式設(shè)備的流行，數(shù)據(jù)加密標準(DES)算法及其變體[1-3]在電子支票轉(zhuǎn)賬[4]、網(wǎng)絡(luò)設(shè)備[5]、嵌入式系統(tǒng)[6]等領(lǐng)域應(yīng)用廣泛。目前，對于DES算法變體的研究主要著眼于兩個方面：其一，DES算法采用56位加密密鑰，過短的密鑰長度易被暴力破解；其二，DES算法的內(nèi)部置換數(shù)組是靜態(tài)的，易被差分功耗分析(DPA)[7-13]。應(yīng)對的方案除了延長密鑰[14-15]外，還包括噪聲產(chǎn)生器[16]、雙軌電路[17]、隨機數(shù)掩碼[18]、流密碼[19]等。這些方案雖然提升了DES算法的安全性，但都沒有針對DES算法的置換數(shù)組的靜態(tài)特性進行改進。文獻[20]雖提出了一種基于時間戳的隨機數(shù)方案使DES算法的置換數(shù)組動態(tài)化，但這種隨機數(shù)生成方案過于簡單。本文提出基于卷積算法[21]和延長密鑰的隨機數(shù)生成方案。在實現(xiàn)過程中，考慮到延長密鑰與原始DES算法的兼容性，本文還提出結(jié)合哈希算法[22]生成新哈希密鑰的方案，從而得到一種較復(fù)雜的動態(tài)化DES算法變體。

本文從DES算法結(jié)構(gòu)與差分功耗分析進行探討，論證該變體的抗暴力破解與抗差分功耗分析能力，對加密表現(xiàn)進行對比，并分析其時間與空間復(fù)雜度。另外，本文還選擇與該變體近似的算法進行運行效率的對比，進行論證分析。

1 傳統(tǒng)DES算法

1.1 基于f函數(shù)的16次迭代

在加密過程中，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擴展為48位，與子密鑰Ki進行異或運算；

步驟3步驟2的結(jié)果依據(jù)S盒壓縮為32位；

步驟4步驟3的結(jié)果再依據(jù)P改變位排列順序后再輸出32位數(shù)據(jù)。

圖1 f函數(shù)

1.2 算法流程

DES算法步驟如圖2所示，流程如下：

步驟1輸入64位明文Plaintext以及64位密鑰Key。

步驟264位密鑰Key根據(jù)圖3的運算，生成16輪的子密鑰{K1，K2，…，K16}。

步驟364位明文按照IP進行初始置換，再分為左右32位L0和R0。

步驟4從L1和R1開始，執(zhí)行16次式(1)和式(2)的迭代，最終生成L16和R16。

步驟5合并L16與R16，再按照IP-1進行逆置換，得到密文C并輸出。

圖2 DES算法流程

圖3 子密鑰生成過程

圖1-圖3中所有標有*號的部分均為置換數(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ù)擴展為48位以加入與子密鑰的運算。

(3) S盒的作用是把48位的數(shù)據(jù)壓縮為32位，該S盒共有8個，每個S盒的容量為4行16列，即64，每行的元素大小在0到15之間且各不相同。48位數(shù)據(jù)分為8組6位的數(shù)據(jù)，以第一個S盒為例(如圖4所示)，其第一位與最后一位合并用于確定S盒的行，剩下的4位用于確定S盒的列，由此得到一個0到15的數(shù)，即4位的值，從而達到壓縮的目的。

圖4 S盒壓縮

(4)P的容量為32，其作用主要用于改變數(shù)據(jù)位的排列順序。

(5)PC-1的容量為56，除了改變數(shù)據(jù)位排列順序外，還用于去除64位密鑰的奇偶校驗位。

(6)LS的容量為16，對應(yīng)著每一輪數(shù)據(jù)循環(huán)左移的位數(shù)。

(7)PC-2的容量為48，用于將循環(huán)左移后的56位結(jié)果壓縮為48位，用于加入到運算中。

(8) 以上提到的數(shù)組各元素的值可參閱文獻[1]。

由此部分可知，各個置換數(shù)組規(guī)模大小不一決定了DES算法在執(zhí)行時產(chǎn)生的功耗呈現(xiàn)規(guī)律性。

2 差分功耗分析

2.1 DES算法功耗曲線

文獻[7]對智能卡執(zhí)行加密并以時間為采樣點對設(shè)備寄存器進行功耗采集，從圖5可以看出DES算法功耗曲線的規(guī)律，其中16輪迭代可以清晰地看出來。

圖5 DES算法功耗曲線

2.2曲線區(qū)分函數(shù)D(C，b，Ks)

通過圖5的功耗曲線識別特定的加密環(huán)節(jié)，區(qū)分函數(shù)基于此得以實施。文獻[7]中對區(qū)分函數(shù)D(C，b，Ks)的定義為：記錄加密后的密文C，依據(jù)Ks的值計算最后一輪迭代前(第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)可計算猜測值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位的方式進行猜測，能夠明顯減少密鑰猜測的次數(shù)。

圖6 D函數(shù)作用范圍

2.3 差分功耗分析流程

由2.2可知，當Ks錯誤時，第b位的值則不確定，在大樣本的作用下該位取0和1的概率相近，各約等于1/2，所有功耗采樣點的功耗都與D函數(shù)不相關(guān)；當Ks正確時，與之對應(yīng)的第b位的值必然是確定的，即概率為1，對應(yīng)S盒處的采樣點功耗與D函數(shù)相關(guān)，而其他采樣點與之不相關(guān)。因此，采用如下差分公式：

(8)

式中:Ti[j]表示m條功耗曲線中第i條功耗曲線的第j個采樣點的功耗。式(8)表示根據(jù)D(C，b，Ks)把m條曲線分類，對兩類曲線的各個樣本點的功耗取均值，再彼此相減，得到差分功耗曲線ΔD。

由此，差分功耗分析的完整流程為：

步驟1使用相同密鑰K，對m條明文進行加密，采集m條功耗曲線T，并記錄相應(yīng)的密文C。

步驟2對任意Ks，根據(jù)式(7)計算D(C，b，Ks)的值。

步驟3根據(jù)式(8)，計算差分曲線ΔD并觀察，當Ks錯誤時，差分曲線ΔD的所有采樣點均趨于0；當Ks正確時，差分曲線ΔD在對應(yīng)S盒的采樣點處會出現(xiàn)尖峰(如圖7所示[7])。

圖7 差分功耗曲線

步驟4每組6位的Ks在經(jīng)過至多26次(64次)的窮舉后，得到正確的48位的第16輪子密鑰并輸出。

差分功耗分析的最終結(jié)果是得到加密過程中的用于迭代的48位子密鑰，由第1部分可知，得到該輪子密鑰后，剩余的子密鑰能夠按照相同的方法推算出來；得到兩輪以上的子密鑰后，根據(jù)圖3的逆過程窮舉計算可以確定56位密鑰的剩余6位，最終得到完整的密鑰。

3 動態(tài)化DES算法

3.1 基于卷積算法的隨機數(shù)數(shù)組

卷積算法主要用于信號處理領(lǐng)域[21]，該算法利用多個數(shù)值依據(jù)各自的權(quán)重得到單個數(shù)值，公式如下：

(9)

式中：B為新的數(shù)值數(shù)組；Core為卷積核數(shù)組；A為初始數(shù)組。

本文根據(jù)密鑰得到卷積核數(shù)組，再計算隨機數(shù)數(shù)組，流程如下：

步驟1輸入128位密鑰K，即容量為16的字符數(shù)組，初始化A為2行8列的二維數(shù)組，每一維數(shù)組分別存儲K的前8個字符和后8個字符。

步驟2根據(jù)圖8計算卷積核數(shù)組Core的4個值，圖中雙箭頭表示異或運算。

圖8 卷積核生成

步驟3根據(jù)圖9利用初始數(shù)組A與卷積核數(shù)組Core，根據(jù)式(9)得到隨機數(shù)數(shù)組B的7個值并輸出B。

圖9 卷積生成隨機數(shù)

由1.2節(jié)可知，DES算法除去與置換數(shù)組IP對應(yīng)的逆置換數(shù)組IP-1后共有7個，因此該隨機數(shù)方案適用于本文的動態(tài)化需求。

3.2 哈希算法

哈希算法常見于數(shù)據(jù)庫檢索、數(shù)據(jù)校驗與分布式存儲等用途中，其包含的兩個特性對本文的價值很大[22]：

(1) 不論輸入的字符串長度與數(shù)量，該算法最終輸出固定位數(shù)的哈希值；

(2) 輸入的字符串發(fā)生細微變化，輸出會發(fā)生大幅度的改變。

利用以上兩個特性，本文能夠?qū)崿F(xiàn)利用128位密鑰得到64位的密鑰以適應(yīng)DES算法加密密鑰長度的目的。Murmurhash2哈希算法在非加密算法中具有高運算性能和低碰撞率的優(yōu)點[23]，因此本文選擇此算法來處理密鑰。該算法除了密鑰作為輸入外，該算法還需接受隨機數(shù)種子作為參數(shù)，本文結(jié)合自身需求給出此哈希算法流程：

步驟1輸入容量為16的字符數(shù)組，即128位密鑰K，64位隨機數(shù)種子seed。

步驟2初始化常值乘數(shù)m=0xc6a4a7935bd1e995，常值右移參數(shù)r=47以及64位初始哈希值h=seed⊕(16×m)。

步驟3將密鑰K分為兩組64位無符號整型數(shù)值Kl和Kr，由此計算h=((h⊕(((Kl×m)>>r)×m)×m)⊕(((Kr×m)>>r)×m))×m。

步驟4計算h=((h⊕(h>>r))×m)>>r并輸出h。

3.3 動態(tài)化方案

本文采用基于卷積算法生成隨機數(shù)的方法對DES算法的內(nèi)部置換數(shù)組動態(tài)化，具體流程如下：

步驟1輸入128位密鑰K和64位明文Plaintext。

步驟2將密鑰K作為輸入傳遞給3.1節(jié)中的算法，得到容量為7的隨機數(shù)數(shù)組RN，其中RN[0]～RN[6]依次為1.2節(jié)中IP、E、P、PC-1、LS、PC-2、S盒所對應(yīng)的隨機數(shù)。

步驟3取密鑰K高64位為L，低64位為R，計算隨機數(shù)種子seed=R⊕L。

步驟4將128位密鑰K與隨機數(shù)種子seed作為輸入傳遞給3.2節(jié)的算法，計算64位哈希密鑰H。

步驟5初始化i=0。

步驟6如果RN[i]為奇數(shù)，則對該隨機數(shù)對應(yīng)的置換數(shù)組進行循環(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個規(guī)模為16的數(shù)組，對第i個數(shù)組，其對應(yīng)隨機數(shù)RN[6]+i-1，如果i大于32，執(zhí)行步驟13；否則，如果RN[6]+i-1為奇數(shù)，執(zhí)行步驟11，反之執(zhí)行步驟12。

步驟11對第i個數(shù)組循環(huán)左移RN[6]+i-1次，i=i+1，執(zhí)行步驟10。

步驟12對第i個數(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)的一個隨機數(shù)，組成隨機數(shù)數(shù)組RN；在步驟5至步驟7，本文判斷前6個置換數(shù)組各自對應(yīng)的隨機數(shù)的奇偶性，以此決定各個置換數(shù)組循環(huán)移動的方向與次數(shù)；因為S盒的結(jié)構(gòu)相比其他置換數(shù)組不同，若是直接旋轉(zhuǎn)會使得每一行數(shù)組不再滿足1.2節(jié)中各元素彼此不同的條件，所以本文在步驟9至步驟10將S盒劃分為32個容量為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 安全性分析

3.4.1抗暴力破解

文獻[24]列出了每微秒解密106次的運算頻率(該速率高于現(xiàn)代CPU的運算速率)下，不同長度密鑰的破解時間，如表1所示。

表1 不同密鑰長度窮舉時間

可以看出，窮舉128位密鑰需要5.4×1018年，因此該變體能夠有效地抗暴力破解。

3.4.2抗差分功耗分析

定理1若DES算法的置換數(shù)組未知，則該算法能夠抗差分功耗分析。

證明假設(shè)DES算法的置換數(shù)組未知時，該算法能夠被差分功耗分析。

若該算法能夠被差分功耗分析，即2.3節(jié)中差分功耗曲線ΔD存在，則式(8)中各變量已知，所以區(qū)分函數(shù)D(式(7))已知；

由式(7)可知，f函數(shù)與初始置換數(shù)組IP已知；

又由圖1和式(3)分別可知，擴展數(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ù)組組合進行窮舉顯然是不可能的。

綜合定理1與置換數(shù)組窮舉的數(shù)量級，該變體能夠抗差分功耗分析。

3.4.3均勻性測試

本文的測試平臺為Ubuntu 18.04 64位操作系統(tǒng)，利用C語言以及gcc組件實現(xiàn)測試。

均勻性指改進后的加密算法的密文，以明文作為參照，改變的位數(shù)要與改進前相近，同時發(fā)生改變的位應(yīng)分布到每一個字節(jié)(8位)中。本文隨機生成50組明文，分別用改進前后的算法進行加密，并與明文對比，得到兩者的最大值、最小值及均值，并生成兩者改變位數(shù)的曲線圖；另外，對該變體的變化位圖進行記錄，由于篇幅原因且各組位圖呈現(xiàn)相似的分布，本文給出前4組密文的變化位圖。

測試結(jié)果顯示：改進前后密文變化位數(shù)的最小值相近，改進后的最大值與均值均高于改進前，且改進后的變化位數(shù)接近明文半數(shù)(表2)；對比各明文對應(yīng)的密文的變化位數(shù)，其曲線波動也相近(圖10)；表3中，“-”代表該位未發(fā)生改變，“*”代表該位發(fā)生改變。該位圖表明，密文的每8位里均發(fā)生位的改變，即發(fā)生變化的位分布到各個字節(jié)中。因此該變體滿足均勻性需求。

表2 改進前后改變位數(shù)最大值、最小值及均值

圖10 均勻性測試曲線

表3 密文變化位圖

續(xù)表3

3.4.4雪崩效應(yīng)

雪崩效應(yīng)指即使明文發(fā)生1位的改變，彼此對應(yīng)的密文之間也會發(fā)生接近半數(shù)的位變化。

本文以16進制明文0x6867666564636261對應(yīng)的密文作為參照，依次對其第1-64位進行改變，用改進前后的算法分別加密，與參照密文對比，變化曲線如圖11所示；并計算兩者位變化數(shù)的最大值、最小值與平均值，結(jié)果如表4所示。同樣地，本文給出變化位圖的前4組，如表5所示，并對發(fā)生變化的16進制位進行加粗顯示，以此驗證雪崩效應(yīng)。

圖11 雪崩測試曲線

表4 改變1位的密文變化數(shù)最大值、最小值及均值

表5 改變1位的密文變化位圖

結(jié)果顯示：改進前后的最小值也相近，改進后的最大值與均值也高于改進前(表4)且發(fā)生接近半數(shù)的位變化； 由圖11可看出改進前后的變化曲線相近；表5中變化位圖以參照密文作為依據(jù)，分別對比各密文發(fā)生的改變，可以看出，明文改變1位后其密文變化也分布到各個字節(jié)中。因此該變體也滿足雪崩效應(yīng)需求。

3.4.5時間復(fù)雜度

本文的改進策略是在原有的DES算法上引入卷積算法與哈希算法。在3.1節(jié)中，卷積核容量與卷積運算次數(shù)均已知，所以時間復(fù)雜度為O(1)；在3.2節(jié)中，哈希算法的時間復(fù)雜度也為O(1)。結(jié)合第1部分的DES算法的原時間復(fù)雜度為O(1)，該變體的時間復(fù)雜度為O(1)+O(1)+O(1)，即O(1)，保持了原有算法的時間復(fù)雜度。

3.4.6空間復(fù)雜度

由第1部分可知，DES算法的輔助存儲空間為常量，即原空間復(fù)雜度為O(1)。該變體除了分配與DES算法相同的輔助存儲外，還會額外地分配卷積算法和哈希算法的輔助存儲內(nèi)存。而卷積算法和哈希算法也是常量存儲，因此該變體空間復(fù)雜度仍為O(1)，保持了原有算法的空間復(fù)雜度。

綜上，該變體能夠有效抗暴力破解與差分功耗分析，同時滿足了加密算法應(yīng)具備的基本要求(均勻性與雪崩效應(yīng))，也保持了原有的時間復(fù)雜度和空間復(fù)雜度。

3.4.7近似算法運行效率對比

本文運行效率測試平臺為64位Ubuntu18.04，利用C語言編寫，CPU頻率和運行內(nèi)存分別為2.40 GHz和8 GB。

鑒于TEA[25](Tiny Encryption Algorithm)與3DES算法的加密明文為64位，加密密鑰為128位，與本文變體相一致，本文選擇這兩種算法與本文變體進行運行效率對比。另外，本文還給出DES算法與本文提及的Murmurhash2算法的運行效率，討論Murmurhash2的引進對算法運行效率的影響。本文利用前四種算法分別對1 000組64位不同的明文類型重復(fù)加解密50次，利用Murmurhash2對1 000組128位不同的明文類型重復(fù)加密50次再取平均值，得出運行效率如表6所示。

表6 DES及各變體運行時間

續(xù)表6

由表6可知，TEA的運行效率極高，這是因為其作為最簡單的Feistel結(jié)構(gòu)加密算法之一，不包含查表變換等一系列操作[25]，因此以此算法為基準能夠清晰地表達本文變體與3DES的運行時間上的增值。而本文變體的運行效率介于DES算法與3DES算法之間，這表明針對DES算法的改進產(chǎn)生的運行時間增值主要體現(xiàn)在查表變換等操作上，而非Feistel結(jié)構(gòu)上，因此本文采用與3DES算法不同的改進策略，動態(tài)化置換數(shù)組，減少DES加解密的次數(shù)，從而達到比3DES算法更高的運行效率。另外，從Murmurhash2算法的運行時間看來，其對整個改進方案的運行效率影響非常小，加之哈希算法的不可逆性，這兩者是本文將其加入到變體方案的原因。

4 結(jié) 語

本文提出基于卷積隨機數(shù)與哈希變換的動態(tài)化DES算法變體。延長原有DES算法的密鑰長度，并依據(jù)延長密鑰基于卷積算法產(chǎn)生7個隨機數(shù)，依次對應(yīng)不同的置換數(shù)組，執(zhí)行相應(yīng)的動態(tài)策略，進而能夠抗暴力破解與差分功耗分析；另一方面基于Murmurhash2哈希算法根據(jù)延長密鑰生成新的哈希密鑰，進而保持原加密算法的基本特性。這兩種方式彼此不相關(guān)，無法彼此推算，攻擊該變體需同時窮舉密鑰和置換數(shù)組，因此該算法的安全性得以提升。另外，與3DES算法相比，該變體還擁有更高的運行效率。