低功耗AVR微處理器上Quark哈希算法優化實現

溫雅敏，黎鳳霞，龔 征，唐韶華

1.廣東商學院 數學與計算科學學院，廣州 510320

2.華南理工大學 計算機科學與工程學院，廣州 510641

3.華南師范大學 計算機學院，廣州 510631

低功耗AVR微處理器上Quark哈希算法優化實現

溫雅敏1，黎鳳霞2，龔 征3，唐韶華2

1.廣東商學院 數學與計算科學學院，廣州 510320

2.華南理工大學 計算機科學與工程學院，廣州 510641

3.華南師范大學 計算機學院，廣州 510631

1 引言

物聯網是繼Internet出現之后信息技術領域的一次革命，它能幫助人們將信息轉變為洞察力，提高決策的質量，優化工業控制過程和生產管理，提高生產力，增強綜合國力和國際競爭力。無線傳感器網絡（WSN）和射頻標簽技術（RFID）具有硬件成本低、網絡健壯性、自組織性強、適用性廣泛的特點，已經成為未來信息技術重點應用“物聯網”的關鍵組成部分。由于WSN和RFID基于無線網絡傳輸信息，攻擊者更加容易獲得、干擾甚至破壞信息傳輸，信息安全的重要性不言而喻。在國際上，目前已提出不少面向受限環境的輕量級分組密碼算法。如 PRESENT[1]、DESXL[2]、LBlock[3]和 LED 算 法[4]。但在具體應用中，除了數據保密性之外，完整性檢測也是保障信息安全所需的基本密碼學構件。通常情況下，密碼學哈希函數（如SHA-1，SHA-2等）被用來檢測消息完整性。在受限環境下，已有實驗結果表明SHA-1等常用哈希函數需要6 000～8 000個門電路才能在硬件上實現，但現有數據表明一個典型RFID標簽只具有1 000到10 000個標準門電路，其中僅有200到2 000個門電路可用于信息安全[5-6]。如果采用軟件方式實現，由于WSN與RFID往往只具有8 bit CPU和KB級別的存儲能力，安全算法同樣面對ROM、RAM和處理器性能上的嚴格限制。過多的存儲和計算開銷也會增大對能量的消耗，降低算法的實用性，這在WSN和RFID環境下同樣是不可接受的。

SHA-3競賽雖然將會選出新的哈希算法作為國際標準，但選擇依據并沒有將傳感器和RFID等資源受限環境下的實現開銷和性能作為評選準則，從進入最后一輪的5個候選算法來看，除了Keccak可以通過參數設置來降低開銷以適應低功耗環境之外，其他4種算法均不具備受限環境下輕量級性質。在文獻[6]中，Bogdanov等人采用基于分組密碼的構造方式，基于PRESENT給出了滿足RFID資源限制的輕量級哈希算法。在已公開文獻中，也有若干哈希算法在設計當中直接考慮了受限環境下的實用性，如 MAME[7]、Photon[8]和 Quark[9]等。但從實驗結果來看，上述算法的實現仍然需要4 000～6 000個門電路，雖然上述哈希算法與標準環境下廣泛應用的算法（如SHA-1，SHA-2等）相比有比較大的軟硬件開銷優勢，但在受限環境下，其軟硬件開銷仍需進一步降低才能具有比較好的實用價值。此外，國內雖然已有若干針對輕量級分組密碼算法的安全性與優化實現分析[10-11]，但針對輕量級哈希算法的比較少，需要進一步研究。

愛特梅爾（ATMEL）公司設計并生產的AVR系列微控制器由于其出色的指令集設計和優秀的性價比，在嵌入式應用環境下成為了廣泛采用的解決方案。在AVR微控制器家族中，ATtiny系列具有低功耗、成本低、開發環境友善等優點，在無線傳感器和RFID領域得到了廣泛的應用。在本文中，從ATtiny微處理器的特點出發，基于AVR ASM語言給出了QUARK哈希算法的優化實現。由于Quark算法并沒有采用傳統的S盒來實現非線性性，在算法優化上并不能簡單套用分組密碼算法的優化方法?；赒uark算法的特點，采用了基于字節與布爾函數運算特點相結合的方法，從而算法實現的處理速度和存儲開銷三方面數據上取得較好的平衡。實際實驗數據表明，優化后的Quark算法實現在ATtiny微處理器平臺下與傳統實現相比具有較大優勢。

2 Quark哈希算法簡介

在CHES 2010會議上，Aumasson等人提出了一種名為Quark的新型輕量級哈希算法[9]。算法基于壓縮函數和迭代運算兩部分組成。壓縮函數基于不同的輸出長度，Quark分為U-Quark，D-Quark和S-Quark三種子算法，相關參數如表1所示。

表1 Quark哈希算法參數設置

出于低功耗的考慮，Quark的壓縮函數大量借鑒了輕量級流密碼Grain[12]和分組密碼Katan[13]的構造方法。如圖1所示，Quark的壓縮函數基于兩個非線性反饋移位寄存器（NFSR）X和Y用以增加輸出的非線性度，另外再采用一個線性反饋移位寄存器（LFSR）L為每一輪壓縮函數的執行提供輪常量，使得滑動攻擊等基于迭代構造的攻擊不再有效。布爾函數 f，g，h將輸入值按照固定的非線性方程的方式輸出一個比特。函數 p僅僅只對L的輸出進行一個線性變換。對于不同參數的Quark子函數而言，壓縮函數結構上是完全一致的，僅在f，g，h函數、輸入輸出長度和迭代次數上有所不同。上述實現具體細節請參考文獻[9]。

圖1 Quark壓縮函數的構造

在迭代結構上，Quark采用了在新型哈希算法設計中廣泛被采用的Sponge構造[14]。與傳統的Merkle-Damgard構造相比，Sponge構造對于長消息攻擊和隨機預言機區分攻擊有著非常好的可證明安全性。同時在低功耗設備的實現上，實驗結果表明基于Sponge結構的哈希算法能節約大量的內存開銷。圖2中描述了基于Sponge構造的Quark迭代方式，其中r和c是Sponge構造當中所定義的rate值和capacity值，P是上述Quark壓縮函數。mi為輸入消息值，在迭代輪數后，zi為哈希輸出值。

圖2 基于Sponge構造的Quark迭代方式

3 面向低功耗AVR微處理器的Quark哈希算法實現

3.1 基于字節的壓縮函數變換操作

Quark的壓縮函數輪數與內部數據寬度有關。以D-Quark為例，由于其內部數據寬度為176 bit，采用22個字節來存儲內部數據，同時需要704輪來迭代處理數據。在普通環境實現中，可以采用并行化的方法，增大內部數據存儲空間的方式來加快處理速度。但在受限硬件環境下，由于內存的限制，三個變換操作每輪只能輸出一個比特，在AVR微處理器環境下，算法的實際總輪數大大增加。在算法的優化上，采用基于字節的方式來提高壓縮函數的效率。在每一輪迭代過程中，由于新的輸出值將會影響到下一輪的運算，增加一個額外的字節用來存放相關數據，同時根據算法每次運行需左移一位的特點，可以把比特的運算變為字節的運算。假設寄存器里存放x0x1x2x3x4x5x6x7八個比特的值，在當前的計算中需要x0這個比特數，那么下一次計算中需要x1這個比特數，由此對寄存器作or或者and的操作，就可以同時更新8個比特的值。因此可以把循環次數降低1/8。改進后的Quark各子算法在內部狀態存儲上所需的字節數和基于字節的壓縮函數所需迭代輪數如表2所示。

表2 基于字節的Quark壓縮函數參數設置

3.2 基于布爾運算特點的非線性函數優化

基于字節操作方式優化壓縮函數后，f，g，h三個非線性布爾函數的變換操作耗時最長。由于 f，g，h本身是基于比特運算的非線性函數，每次需要對輸入比特進行大量的加法和乘法運算。而在AVR環境下并沒有針對比特的上述算術操作，因而在實際計算需要對布爾函數的每一項進行運算才能得出結果。在算法的優化過程中，基于布爾運算的特點，將 f，g，h函數的計算過程通過同類項和提前約取的方法加以簡化。通過布爾函數 f(x)=x0x1x2+x0x1x3（其中 x0x1x2+x0x1x3表示各比特邏輯與之后再進行邏輯加運算，與Quark原始論文[9]中表示方法一致）對優化方法解釋如下：

（1）如果有 x0或 x1等于0，那么無論 x2或 x3取何值，整個函數的輸出值均為0。

（2）如果 x2或 x3等于0，那么所有包含 x2或 x3的項都為0。

（3）如果x2等于1，那么可以把所有 x2從等式中約去，對輸出結果沒有影響。

采用上述優化方法后，在計算 f，g，h函數的過程中能大大簡化所需要的布爾運算次數。優化后的Quark算法的AVR ASM偽代碼結構如下所示。

雖然上述優化方法需要額外增加邏輯判斷的開銷，但由于 f，g，h布爾函數是固定的，所以在實際運算的過程中，增加的邏輯判斷對算法的優化效果仍然比較明顯。

3.3 實驗結果

通過上述優化方法，基于AVR匯編語言實現了Quark算法?；赒uark原始論文[9]給出的正確性測試，優化后的算法在實現上是正確的。Quark算法基于標準輸入消息的相應輸出結果應如下所示。

（1）初始值

（2）在輸入消息為空（即分別為17、22、32 Byte的空數組）的情況下

為了比較Quark實現在ATtiny設備上的實際效率，采用ATMEL ATting45系列微處理器作為實驗平臺，在平臺上使用AVR ASM匯編語言（編譯環境AVR Studio 6.0）來實現D-Quark和S-Quark算法。ATtiny45系列微處理器具有4 kByte可編程Flash ROM，256 Byte EEPROM，256 Byte SRAM，工作模式下主頻可自適應調整，最大可為20 MHz。為了對比所提出的優化方法的效率，也按照Quark原始參考文獻當中的標準方法將D-Quark和S-Quark在相同平臺下加以實現并測試。各項性能數據均由AVR Studio 6.0測試給出。

表3 QUARK算法在ATtiny 45微處理器實現性能比較

4 結束語

雖然摩爾定律預測計算機的計算速度和存儲能力每18個月能增加一倍，但由于制造成本和便攜性的限制，WSN和RFID硬件平臺的計算能力、存儲能力和能量仍然受到非常大的限制。盡管輕量級分組密碼算法的研究已經引起廣泛的關注，但仍然存在不少問題尚待解決。輕量級密碼學作為一個新興研究分支，需要綜合密碼學、電路設計和嵌入式系統等方面的研究方法和成果。Quark哈希算法采用了面向軟件的設計思路，很好地平衡了算法的安全性和軟硬件實現上的效率與開銷。在未來的工作中，將進一步地深入分析Quark哈希算法在受限軟硬件環境下的具體實現方法，為Quark在實際中提供更充分的性能指標和算法實現參考。

[1]Bogdanov A，Knudsen L R，Leander G，et al.PRESENT：an ultra-lightweight block cipher[C]//LNCS 4727：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2007），Vienna，Austria，2007：450-466.

[2]Guo Jian，Peyrin T，Poschmann A，et al.The LED block cipher[C]//LNCS 6917：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2011），Nara，Japan，2011：326-341.

[3]Wu Wenling，Zhang Lei.LBlock：a lightweight block cipher[C]//LNCS 6715：Applied Cryptography and Network Security（ACNS 2011），Nerja，Spain，2011：327-344.

[4]Poschmann A.Lightweight cryptography-cryptographic engineering for a pervasive world[D].Bochum，Germany：Ruhr-University，2009.

[5]Juels A，Weis S A.Authenticating pervasive devices with human protocols[C]//LNCS 3126：Advances in Cryptology（CRYPTO 2005），Santa Barbara，California，USA，2005：293-308.

[6]Bogdanov A，Leander G，Paar C，et al.Hash functions and RFID tags：mind the gap[C]//LNCS 5154：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2008），Washington，DC，USA，2008：283-299.

[7]Yoshida H，Watanabe D，Okeya K，et al.MAME：a compression function with reduced hardware requirements[C]// LNCS 4727：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2007），Vienna，Austria，2007：148-165.

[8]Guo Jian，Peyrin T，Poschmann A.The photon family of lightweight hash[C]//LNCS 6841：Advances in Cryptology（CRYPTO 2011），Santa Barbara，California，USA，2011：222-239.

[9]Aumasson J，Henzen L，Meier W，et al.Quark：a lightweight hash[C]//LNCS 6225：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2010），Santa Barbara，USA，2010：1-15.

[10]葛十景.代數分析及其對若干輕量級分組密碼的應用[D].上海：上海交通大學，2011.

[11]李瑋，谷大武，趙辰，等.物聯網環境下LED輕量級分組加密算法的安全性分析[J].計算機學報，2012（3）：434-445.

[12]Hell M，Johansson T，Meier W.Grain：a stream cipher for constrained environments[J].IJWMC，2007，2（1）：86-93.

[13]De Canniere C，Dunkelman O，Knezevic M.KATAN and KTANTAN-a family of small and efficient hardwareoriented block ciphers[C]//LNCS 5747：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2009），Lausanne，Switzerland，2009：272-288.

[14]Bertoni G，Daemen J，Peeters M，et al.On the indifferentiability of the sponge construction[C]//LNCS 4965：Advances in Cryptology （EUROCRYPT 2008），Istanbul，Turkey，2008：181-197.

WEN Yamin1,LI Fengxia2,GONG Zheng3,TANG Shaohua2

1.School of Mathematics and Computational Science,Guangdong University of Business Studies,Guangzhou 510320,China
2.School of Computer Science and Technology,South China University of Technology,Guangzhou 510641,China
3.School of Computer,South China Normal University,Guangzhou 510631,China

Cryptographic hash functions are widely used for data integrity.The hash functions for standard environment need to be reduced for the applications in the Internet of Things.In this paper,based on the properties of AVR low-cost microcontrollers,it proposes an optimized implementation of the Quark hash function with AVR ASM.The optimized implementation makes a good balance between the processing speed and storage costs.

cryptographic algorithms;lightweight hash function;Quark;ATtiny

哈希算法被廣泛用于數據完整性檢測。在物聯網數據完整性檢測中，現有標準哈希算法的軟硬件開銷仍需進一步降低。從低功耗AVR微處理器的特點出發，通過基于字節的壓縮函數變換操作和基于布爾運算特點的函數優化，以AVR ASM為開發語言環境給出了Quark哈希算法的優化實現，在算法實現的處理速度和存儲開銷上取得較好的平衡。

密碼學算法；輕量級哈希函數；Quark；ATtiny

A

TP309.7

10.3778/j.issn.1002-8331.1301-0029

WEN Yamin,LI Fengxia,GONG Zheng,et al.Optimized implementation of Quark hash function for lightweight AVR microcontrollers.Computer Engineering and Applications,2014,50（23）：104-107.

國家自然科學基金（No.61100201，No.61170080，No.U1135004）；廣東省自然科學基金（No.S2012040006711，No.S2012010010376）；廣東省教育廳育苗工程（No.LYM11053）；廣東商學院校級科研項目（No.11BS41301）。

溫雅敏（1981—），女，博士，講師，研究領域為密碼學與信息安全；黎鳳霞，女，碩士研究生，研究領域為信息安全；龔征（1981—），男，博士，副教授，研究領域為信息系統安全；唐韶華（1970—），男，博士，教授，研究領域為信息安全。E-mail：ya-min.wen@gmail.com

2013-01-06

2013-03-22

1002-8331（2014）23-0104-04

CNKI網絡優先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1648.017.html