基于Sponge結構的輕量級Hash函數設計

趙太飛，尹 航，李永明

(西安理工大學 自動化與信息工程學院，西安 710048)

1 引 言

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

從針對資源受限環境的Hash函數概念提出到現在，國內外學者設計了一系列輕量級Hash函數：SQUASH[4]、PHONTON[5]、Quark[6]、SPONGENT[7]、Lesamnta-LW[8]、GLUON[9]、DM-PRESENT[10]、LHash[11]等.但由于目前沒有統一的輕量級Hash函數標準，這些算法針對硬件效率，或針對軟件效率各有側重.本文設計了一種輕量級Hash函數，在滿足一定安全性的同時具有較好的軟硬件實現效率.

2 Sponge結構和Klein算法

2.1 Sponge結構

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

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

圖1 Sponge結構圖Fig.1 Sponge structure

2.2 Klein算法

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

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

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

3 Hash函數構造與實現

3.1 Hash函數設計

3.1.1 參數設置及預處理

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

圖3 Hash函數算法結構Fig.3 Hash function algorithm structure

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

3.1.2 壓縮函數設計

預處理后的消息要通過壓縮函數的處理完成吸收，壓縮函數的設計借鑒了Klein算法的思想，并對其進行優化，使之更契合“輕量化”的設計目標.主流程可描述為：

fori= 1 toNRdo

AddRoundKey(STATE，ski)；

Substitution(STATE)；

RotateNibbles(STATE)；

Permutation(STATE)；

ski+1=KeySchedule(ski，i)；

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

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層進行非線性置換，Substitution層采用16個并行相同的s盒，s盒為Klein中的4位s盒，可以將4位輸入非線性變換為4位輸出，如表1所示.

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

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

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

3.2 算法優化設計

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

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

4 硬件和軟件效率

4.1 硬件實現效率

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

表4 硬件實現規模對比Table 4 Hardware implementation scale comparison

4.2 軟件實現效率

在AMD AthlonII X2 250 3GHz，Windows7 32位平臺下用C++對算法進行實現.并與同樣采用Sponge結構作為SHA-3標準的經典Keccak算法進行對比.多次實驗取均值，結果如表5所示.

表5 軟件效率對比Table 5 Software efficiency comparison

通過軟硬件實現對比可以看出：本文算法的硬件實現GE數在2000GE之下，滿足RFID等資源受限環境對硬件實現規模的要求；軟件實現通過面向字節優化，相較于傳統采用Sponge結構的Hash函數處理速度有了極大的提升，兼顧了軟件效率.

5 安全性測試與分析

5.1 依賴性測試

依賴性測試就是通過統計學的方法對密碼算法的混淆程度和擴散性給出一個概率上的結論，主要包括完備性，雪崩效應度da，嚴格雪崩準則dsa等.理想狀態下，任何一位輸入的改變都會引起半數輸出值的改變；任何一位輸入改變引起每位輸出都以1/2的概率發生改變.

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

表6 依賴性測試結果Table 6 Dependency test

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

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

表7 碰撞測試結果Table 7 Collision test

同時對算法的抗碰撞、抗原像以及第二原像性能進行理論分析，由于對基于Sponge結構的Hash函數抗傳統攻擊的能力已有深刻研究，這里直接利用公式進行計算：

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

(1)

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

(2)

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

(3)

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

5.3 滑動攻擊分析

滑動攻擊主要針對輪密鑰的生成，受到了相關密鑰攻擊的啟發，利用輪迭代函數的周期性，通過找到滿足相關條件的明文-密文對，由他們之間的關系式獲取密鑰信息.本文采用的密鑰調度算法基于Feistel結構，具有很好的非對稱性.采用了一個輪計數器，將迭代輪數參與運算，利用s盒進行非線性置換.產生密鑰的輪函數內有移位操作，且中間狀態更新時也有適當移位操作.不具有自相似性，可以很好的抵抗滑動攻擊.

5.4 差分和線性分析

6 結 語

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