基于Sponge結(jié)構(gòu)的輕量級(jí)Hash函數(shù)設(shè)計(jì)

趙太飛，尹 航，李永明

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，西安 710048)

1 引 言

隨著物聯(lián)網(wǎng)技術(shù)(Internet of Things，IOT)的高速發(fā)展，其存在的安全隱私問題也越來越受到人們重視.Hash函數(shù)是應(yīng)對(duì)安全威脅的有效手段，同時(shí)也是密碼學(xué)的重要組成部分，它可以將任意長的消息映射成為固定長度的消息摘要，是一種單向散列函數(shù).主要應(yīng)用于數(shù)字簽名、射頻識(shí)別技術(shù)(Radio Frequency Identification，RFID)、隨機(jī)數(shù)生成、鑒定消息的完整性和準(zhǔn)確性等方面.針對(duì)RFID系統(tǒng)、無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)等場景，安全性不再是衡量算法的唯一標(biāo)準(zhǔn).因?yàn)樵谶@些資源受限條件下，硬件只有有限的計(jì)算能力和很小的存儲(chǔ)空間.這就要求用于信息安全的加密算法必須“輕量化”：在保證一定安全性的前提下有較小的實(shí)現(xiàn)代價(jià)，占用較低的硬件資源，有很快的處理速度[1].文獻(xiàn)[2]中提到在RFID系統(tǒng)中用于安全加密的標(biāo)準(zhǔn)門電路(Gate Equivalent，GE)可能只有200～2000個(gè)，很顯然傳統(tǒng)的Hash函數(shù)并不能滿足這一點(diǎn).Tianyong Ao等人于2014年提出的國家商密標(biāo)準(zhǔn)Hash函數(shù)SM3 的最優(yōu)化硬件實(shí)現(xiàn)仍需6904 GE[3].

從針對(duì)資源受限環(huán)境的Hash函數(shù)概念提出到現(xiàn)在，國內(nèi)外學(xué)者設(shè)計(jì)了一系列輕量級(jí)Hash函數(shù)：SQUASH[4]、PHONTON[5]、Quark[6]、SPONGENT[7]、Lesamnta-LW[8]、GLUON[9]、DM-PRESENT[10]、LHash[11]等.但由于目前沒有統(tǒng)一的輕量級(jí)Hash函數(shù)標(biāo)準(zhǔn)，這些算法針對(duì)硬件效率，或針對(duì)軟件效率各有側(cè)重.本文設(shè)計(jì)了一種輕量級(jí)Hash函數(shù)，在滿足一定安全性的同時(shí)具有較好的軟硬件實(shí)現(xiàn)效率.

2 Sponge結(jié)構(gòu)和Klein算法

2.1 Sponge結(jié)構(gòu)

在設(shè)計(jì)構(gòu)造Hash函數(shù)時(shí)，根據(jù)不同的迭代結(jié)構(gòu)和壓縮函數(shù)有不同的實(shí)現(xiàn)方法.目前常用的迭代結(jié)構(gòu)有：DM結(jié)構(gòu)、MD(Merkle-Damg?rd)結(jié)構(gòu)、Sponge結(jié)構(gòu)等.基于置換函數(shù)的Hash函數(shù)可采用Sponge結(jié)構(gòu)，如作為SHA-3標(biāo)準(zhǔn)算法的Keccak算法[12]，該算法可通過參數(shù)調(diào)節(jié)進(jìn)行輕量化實(shí)現(xiàn).相較于其它結(jié)構(gòu)，Sponge 結(jié)構(gòu)對(duì)隨機(jī)預(yù)言機(jī)區(qū)分攻擊具有可證明安全性[13]，且沒有前向反饋，實(shí)現(xiàn)起來只需要較小內(nèi)存和硬件開銷，更適合于輕量級(jí)Hash函數(shù)的設(shè)計(jì).

一個(gè)典型的Sponge結(jié)構(gòu)如圖1所示，其中Mt為填充后的消息分組，Hs為壓縮后的消息摘要分組，f(?)為壓縮函數(shù)，r是輸入消息分組長度，c為容量.加密流程為：待處理的消息通過填充處理后分為r位一組.第一組M0與初始r位數(shù)據(jù)異或后與初始c位數(shù)據(jù)拼接通過壓縮函數(shù)f(?)，輸出的中間狀態(tài)前r位與M1異或后與中間狀態(tài)剩下的c位數(shù)據(jù)拼接作為下一輪輸入，依次重復(fù)直到所有消息吸收完畢.壓縮階段將壓縮函數(shù)f(?)輸出的中間狀態(tài)作為下一輪的輸入，并提取H0，H1，…，Hs各子串連接起來成為消息摘要.

圖1 Sponge結(jié)構(gòu)圖Fig.1 Sponge structure

2.2 Klein算法

針對(duì)RFID系統(tǒng)和無線傳感網(wǎng)絡(luò)等資源受限環(huán)境，Gong等人在 RFIDSec 2011 會(huì)議上提出了一種基于SP(Substitution-Permutation Network)結(jié)構(gòu)的輕量級(jí)分組加密算法Klein.算法輪加密如圖2所示：明文P分組后與每一輪的輪密鑰進(jìn)行異或操作，產(chǎn)生的中間狀態(tài)通過16個(gè)4比特S盒，再進(jìn)行左移操作RotateNibbles，然后進(jìn)行線性置換MixNibbles，依次進(jìn)行n輪迭代最終產(chǎn)生密文C.

圖2 Klein輪加密Fig.2 Round transformation of KLEIN

Klein算法的分組長度為64bit，密鑰長度為可變的64、80或96bit，可以定義為Klein-64/80/96，與之對(duì)應(yīng)的加密輪數(shù)為12、16或20輪.該算法主要關(guān)注資源受限環(huán)境下的軟件實(shí)現(xiàn)，特別是在較低硬件資源下如8位處理器平臺(tái)上.算法設(shè)計(jì)者聲稱：Klein-80/96有很好的安全性可以應(yīng)對(duì)大多數(shù)的應(yīng)用場景，而Klein-64有很好的軟硬件實(shí)現(xiàn)性能可用于Hash函數(shù)設(shè)計(jì)以及消息認(rèn)證[14].

3 Hash函數(shù)構(gòu)造與實(shí)現(xiàn)

3.1 Hash函數(shù)設(shè)計(jì)

3.1.1 參數(shù)設(shè)置及預(yù)處理

本文采用的迭代結(jié)構(gòu)為Sponge結(jié)構(gòu)，算法整體結(jié)構(gòu)如圖3所示.消息經(jīng)過預(yù)處理后分為M0到Ms一共s個(gè)分組，經(jīng)過s次壓縮函數(shù)F的處理后完成吸收操作.然后再通過n次壓縮函數(shù)F的處理且每次提取一個(gè)子串，從H0到Hn一共n+1個(gè)子串拼接成摘要.壓縮函數(shù)的每輪運(yùn)算主要由輪密鑰加，Substitution層，RotateNibbles，Permutation層組成.

圖3 Hash函數(shù)算法結(jié)構(gòu)Fig.3 Hash function algorithm structure

考慮到輕量化需求，具體設(shè)計(jì)時(shí)取吞吐率r=8bit，容量c=56bit，那么置換長度b=64bit.消息摘要長度為64bit，擁有64bit的內(nèi)存狀態(tài).加密前的預(yù)處理操作為：將內(nèi)存狀態(tài)的初始值設(shè)為0，輸入消息轉(zhuǎn)換為二進(jìn)制后進(jìn)行填充.在消息后面填充一個(gè)1，然后填充若干個(gè)0，使之長度為r的最小整數(shù)倍.例如當(dāng)消息長度length 對(duì)r取余值為1時(shí)，填充的值為“100000000”. 再對(duì)填充后的數(shù)據(jù)進(jìn)行吸收、壓縮運(yùn)算.

3.1.2 壓縮函數(shù)設(shè)計(jì)

預(yù)處理后的消息要通過壓縮函數(shù)的處理完成吸收，壓縮函數(shù)的設(shè)計(jì)借鑒了Klein算法的思想，并對(duì)其進(jìn)行優(yōu)化，使之更契合“輕量化”的設(shè)計(jì)目標(biāo).主流程可描述為：

fori= 1 toNRdo

AddRoundKey(STATE，ski)；

Substitution(STATE)；

RotateNibbles(STATE)；

Permutation(STATE)；

ski+1=KeySchedule(ski，i)；

其中i表示輪數(shù)，STATE表示中間狀態(tài)，ski表示輪密鑰.每輪運(yùn)算開始先將輸入的中間狀態(tài)與產(chǎn)生的輪密鑰進(jìn)行輪密鑰加，也就是異或運(yùn)算.輪密鑰生成算法采用典型的Feistel結(jié)構(gòu)[15]，將迭代輪數(shù)Nr作為變量參與運(yùn)算.密鑰更新流程如下所示，其中ski[n]表示第i輪密鑰的第n個(gè)字節(jié)，?表示異或運(yùn)算，sbox[?]表示用s盒(sbox)對(duì)數(shù)據(jù)進(jìn)行非線性變換.

ski+1[0]=ski[5]；

ski+1[1]=ski[6]；

ski+1[2]=ski[7]?Nr；

ski+1[3]=ski[4]；

ski+1[4]=ski[1]?ski[5]；

ski+1[5]=sbox[ski[2]?ski[6]]；

ski+1[6]=sbox[ski[3]?ski[7]]；

ski+1[7]=ski[0]?ski[4]；

輪密鑰加后的STATE通過Substitution層進(jìn)行非線性置換，Substitution層采用16個(gè)并行相同的s盒，s盒為Klein中的4位s盒，可以將4位輸入非線性變換為4位輸出，如表1所示.

表1 4比特s盒Table 1 4-Bit S-box

RotateNibbles操作將通過Substitution層的數(shù)據(jù)左移16bit.然后通過Permutation層進(jìn)行線性置換，依次迭代12輪完成壓縮函數(shù)的運(yùn)算.Permutation層沒有采用Klein中的置換操作而是使用文獻(xiàn)[15]中的位排列置換，這樣可以有更好的硬件實(shí)現(xiàn)性能，置換表如表2所示.

表2 P置換表Table 2 P- permutation table

3.2 算法優(yōu)化設(shè)計(jì)

本文設(shè)計(jì)的Hash函數(shù)主要針對(duì)的是資源受限環(huán)境，硬件條件多為8位處理器.為了在8位處理器環(huán)境下有較高效率，采用面向字節(jié)的思想對(duì)算法進(jìn)行優(yōu)化設(shè)計(jì)，將字節(jié)作為運(yùn)算單位.對(duì)待加密的數(shù)據(jù)按字節(jié)讀取，吸收和壓縮階段以及輪密鑰加、輪密鑰更新都是字節(jié)運(yùn)算.Permutation層是位排列操作，硬件實(shí)現(xiàn)有較高的效率，但軟件實(shí)現(xiàn)效率并不高.所以軟件實(shí)現(xiàn)時(shí)并沒有直接進(jìn)行按位排序操作，而是對(duì)字節(jié)數(shù)據(jù)進(jìn)行移位操作，并與按順序移位的十六進(jìn)制0x80進(jìn)行與運(yùn)算獲得比特?cái)?shù)據(jù).Substitution層軟件實(shí)現(xiàn)時(shí)將兩個(gè)4bit輸入輸出的s盒拼接為8bit的輸入輸出s盒，并生成一個(gè)容量為256字節(jié)的表.通過面向字節(jié)的查表操作即可完成非線性變化，Substitution層中64bit中間狀態(tài)的非線性變換只需要8次查表操作.例如輸入字節(jié)為0x09，通過查表3可得輸出為0x73.

表3 非線性表(部分)Table 3 Non-linear table (part)

4 硬件和軟件效率

4.1 硬件實(shí)現(xiàn)效率

本節(jié)用等效門電路GE個(gè)數(shù)來衡量算法的硬件實(shí)現(xiàn)規(guī)模.運(yùn)算過程中需要用于存儲(chǔ)64位中間狀態(tài)的寄存器，大約需要384.8GE.密鑰生成過程同樣需要64位的寄存器，大約需要384.8GE，除此之外輪密鑰的生成還需要一個(gè)8位的異或運(yùn)算用于將輪數(shù)參與運(yùn)算，大約需要21.8GE.吸收階段需要8位異或運(yùn)算用于吸收消息，大約需要21.8GE.壓縮函數(shù)中：輪密鑰加需要64位異或運(yùn)算，大約需要174GE.Permutation層可通過硬件電路實(shí)現(xiàn)不需要門電路.Substitution層采用的是相同的s盒，可以采用一個(gè)4x4的s盒實(shí)現(xiàn)，大約需要28GE.輪密鑰生成需要一個(gè)s盒，大約需要28GE，移位操作可通過改變布線邏輯實(shí)現(xiàn)，不需要門電路.綜上，共需384.8+384.8+21.8+21.8+174+56=1041.6GE.與文獻(xiàn)[16]總結(jié)的幾種Hash函數(shù)硬件實(shí)現(xiàn)進(jìn)行對(duì)比，如表4所示.

表4 硬件實(shí)現(xiàn)規(guī)模對(duì)比Table 4 Hardware implementation scale comparison

4.2 軟件實(shí)現(xiàn)效率

在AMD AthlonII X2 250 3GHz，Windows7 32位平臺(tái)下用C++對(duì)算法進(jìn)行實(shí)現(xiàn).并與同樣采用Sponge結(jié)構(gòu)作為SHA-3標(biāo)準(zhǔn)的經(jīng)典Keccak算法進(jìn)行對(duì)比.多次實(shí)驗(yàn)取均值，結(jié)果如表5所示.

表5 軟件效率對(duì)比Table 5 Software efficiency comparison

通過軟硬件實(shí)現(xiàn)對(duì)比可以看出：本文算法的硬件實(shí)現(xiàn)GE數(shù)在2000GE之下，滿足RFID等資源受限環(huán)境對(duì)硬件實(shí)現(xiàn)規(guī)模的要求；軟件實(shí)現(xiàn)通過面向字節(jié)優(yōu)化，相較于傳統(tǒng)采用Sponge結(jié)構(gòu)的Hash函數(shù)處理速度有了極大的提升，兼顧了軟件效率.

5 安全性測試與分析

5.1 依賴性測試

依賴性測試就是通過統(tǒng)計(jì)學(xué)的方法對(duì)密碼算法的混淆程度和擴(kuò)散性給出一個(gè)概率上的結(jié)論，主要包括完備性，雪崩效應(yīng)度da，嚴(yán)格雪崩準(zhǔn)則dsa等.理想狀態(tài)下，任何一位輸入的改變都會(huì)引起半數(shù)輸出值的改變；任何一位輸入改變引起每位輸出都以1/2的概率發(fā)生改變.

對(duì)64bit的數(shù)據(jù)進(jìn)行10000次測試，從第二次開始，每次隨機(jī)改變上次輸入值的某一位，將得到的64bit輸出值與上個(gè)輸出值進(jìn)行對(duì)比，得到測試數(shù)據(jù)如表6所示.可以看出輸入改變一位輸出改變位數(shù)的平均值接近32位，輸入改變一位輸出位改變的概率接近0.5.完備度為1，雪崩效應(yīng)度和嚴(yán)格雪崩準(zhǔn)則均接近1，有較好的依賴性.

表6 依賴性測試結(jié)果Table 6 Dependency test

5.2 抗碰撞、原像和第二原像測試分析

理想情況下Hash函數(shù)是無碰撞的，但實(shí)際情況中很難做到這一點(diǎn).本節(jié)對(duì)算法進(jìn)行碰撞測試：隨機(jī)取一組明文，測試n次，每次隨機(jī)改變輸入值的其中1bit，對(duì)改變前后輸出值的ASCII碼進(jìn)行對(duì)比.若輸出值相同位置的ASCII字符相同則稱為碰撞一次，統(tǒng)計(jì)碰撞次數(shù).多次試驗(yàn)取均值，測試次數(shù)n分別為2000、4000、8000、10000，測試結(jié)果如表7所示.可以看出4000次碰撞測試時(shí)，有94次碰撞1次，3906次沒有發(fā)生碰撞，最大碰撞次數(shù)為1.當(dāng)碰撞測試10000次時(shí)有270次碰撞1次，6次碰撞2次，9724次沒有發(fā)生碰撞，最大碰撞次數(shù)為2，所以碰撞很小.

表7 碰撞測試結(jié)果Table 7 Collision test

同時(shí)對(duì)算法的抗碰撞、抗原像以及第二原像性能進(jìn)行理論分析，由于對(duì)基于Sponge結(jié)構(gòu)的Hash函數(shù)抗傳統(tǒng)攻擊的能力已有深刻研究，這里直接利用公式進(jìn)行計(jì)算：

抗碰撞攻擊：min{2n/2，2c/2}；

(1)

抗原像攻擊：min{2n，2c，max{2n-r，2c/2}}；

(2)

抗第二原像攻擊：min{2n，2c/2}.

(3)

其中n為輸出位數(shù)，c為容量大小，r為輸入消息分組長度.那么本文算法抗碰撞、原像和第二原像能力分別為：228，256，228.

5.3 滑動(dòng)攻擊分析

滑動(dòng)攻擊主要針對(duì)輪密鑰的生成，受到了相關(guān)密鑰攻擊的啟發(fā)，利用輪迭代函數(shù)的周期性，通過找到滿足相關(guān)條件的明文-密文對(duì)，由他們之間的關(guān)系式獲取密鑰信息.本文采用的密鑰調(diào)度算法基于Feistel結(jié)構(gòu)，具有很好的非對(duì)稱性.采用了一個(gè)輪計(jì)數(shù)器，將迭代輪數(shù)參與運(yùn)算，利用s盒進(jìn)行非線性置換.產(chǎn)生密鑰的輪函數(shù)內(nèi)有移位操作，且中間狀態(tài)更新時(shí)也有適當(dāng)移位操作.不具有自相似性，可以很好的抵抗滑動(dòng)攻擊.

5.4 差分和線性分析

6 結(jié) 語

本文設(shè)計(jì)了一種輕量級(jí)Hash函數(shù)，迭代結(jié)構(gòu)采用主流的Sponge結(jié)構(gòu)，內(nèi)部變換采用改進(jìn)的Klein算法，非線性置換層是硬件實(shí)現(xiàn)效率較好的位排列，同時(shí)為了兼顧軟件實(shí)現(xiàn)效率，對(duì)軟件實(shí)現(xiàn)進(jìn)行面向字節(jié)的優(yōu)化.最后對(duì)算法進(jìn)行依賴性實(shí)驗(yàn)和常規(guī)攻擊分析，結(jié)果表明算法具有良好的擴(kuò)散混淆性，并能抵抗常見攻擊.效率測試表明算法的硬件實(shí)現(xiàn)所需門電路數(shù)大約為1042GE，且有較好的軟件實(shí)現(xiàn)效率，適用于資源受限環(huán)境.