低功耗AVR微處理器上Quark哈希算法優(yōu)化實(shí)現(xiàn)

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

1.廣東商學(xué)院 數(shù)學(xué)與計算科學(xué)學(xué)院，廣州 510320

2.華南理工大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，廣州 510641

3.華南師范大學(xué) 計算機(jī)學(xué)院，廣州 510631

低功耗AVR微處理器上Quark哈希算法優(yōu)化實(shí)現(xiàn)

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

1.廣東商學(xué)院 數(shù)學(xué)與計算科學(xué)學(xué)院，廣州 510320

2.華南理工大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，廣州 510641

3.華南師范大學(xué) 計算機(jī)學(xué)院，廣州 510631

1 引言

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

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

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

2 Quark哈希算法簡介

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

表1 Quark哈希算法參數(shù)設(shè)置

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

圖1 Quark壓縮函數(shù)的構(gòu)造

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

圖2 基于Sponge構(gòu)造的Quark迭代方式

3 面向低功耗AVR微處理器的Quark哈希算法實(shí)現(xiàn)

3.1 基于字節(jié)的壓縮函數(shù)變換操作

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

表2 基于字節(jié)的Quark壓縮函數(shù)參數(shù)設(shè)置

3.2 基于布爾運(yùn)算特點(diǎn)的非線性函數(shù)優(yōu)化

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

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

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)果

通過上述優(yōu)化方法，基于AVR匯編語言實(shí)現(xiàn)了Quark算法。基于Quark原始論文[9]給出的正確性測試，優(yōu)化后的算法在實(shí)現(xiàn)上是正確的。Quark算法基于標(biāo)準(zhǔn)輸入消息的相應(yīng)輸出結(jié)果應(yīng)如下所示。

（1）初始值

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

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

表3 QUARK算法在ATtiny 45微處理器實(shí)現(xiàn)性能比較

4 結(jié)束語

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

[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]葛十景.代數(shù)分析及其對若干輕量級分組密碼的應(yīng)用[D].上海：上海交通大學(xué)，2011.

[11]李瑋，谷大武，趙辰，等.物聯(lián)網(wǎng)環(huán)境下LED輕量級分組加密算法的安全性分析[J].計算機(jī)學(xué)報，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

哈希算法被廣泛用于數(shù)據(jù)完整性檢測。在物聯(lián)網(wǎng)數(shù)據(jù)完整性檢測中，現(xiàn)有標(biāo)準(zhǔn)哈希算法的軟硬件開銷仍需進(jìn)一步降低。從低功耗AVR微處理器的特點(diǎn)出發(fā)，通過基于字節(jié)的壓縮函數(shù)變換操作和基于布爾運(yùn)算特點(diǎn)的函數(shù)優(yōu)化，以AVR ASM為開發(fā)語言環(huán)境給出了Quark哈希算法的優(yōu)化實(shí)現(xiàn)，在算法實(shí)現(xiàn)的處理速度和存儲開銷上取得較好的平衡。

密碼學(xué)算法；輕量級哈希函數(shù)；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.

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

溫雅敏（1981—），女，博士，講師，研究領(lǐng)域?yàn)槊艽a學(xué)與信息安全；黎鳳霞，女，碩士研究生，研究領(lǐng)域?yàn)樾畔踩积徴鳎?981—），男，博士，副教授，研究領(lǐng)域?yàn)樾畔⑾到y(tǒng)安全；唐韶華（1970—），男，博士，教授，研究領(lǐng)域?yàn)樾畔踩-mail：ya-min.wen@gmail.com

2013-01-06

2013-03-22

1002-8331（2014）23-0104-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1648.017.html