低功耗AVR微處理器上Quark 哈希算法優(yōu)化實現(xiàn)-技術(shù)方案

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

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

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

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

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

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

在迭代結(jié)構(gòu)上，Quark采用了在新型哈希算法設(shè)計中廣泛被采用的Sponge構(gòu)造.與傳統(tǒng)的Merkle-Damgard構(gòu)造相比，Sponge構(gòu)造對于長消息攻擊和隨機預(yù)言機區(qū)分攻擊有著非常好的可證明安全性.同時在低功耗設(shè)備的實現(xià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為哈希輸出值.

3面向低功耗AVR微處理器的Quark哈希算法實現(xiàn)3.1基于字節(jié)的壓縮函數(shù)變換操作Quark的壓縮函數(shù)輪數(shù)與內(nèi)部數(shù)據(jù)寬度有關(guān).

以D-Quark為例，由于其內(nèi)部數(shù)據(jù)寬度為176比特，我們采用22個字節(jié)來存儲內(nèi)部數(shù)據(jù)，同時需要704輪來迭代處理數(shù)據(jù).在普通環(huán)境實現(xiàn)中，我們可以采用并行化的方法，增大內(nèi)部數(shù)據(jù)存儲空間的方式來加快處理速度.但在受限硬件環(huán)境下，由于內(nèi)存的限制，三個變換操作每輪只能輸出一個比特，在AVR微處理器環(huán)境下，算法的實際總輪數(shù)大大增加.

在算法的優(yōu)化上，我們采用基于字節(jié)的方式來提高壓縮函數(shù)的效率.在每一輪迭代過程中，由于新的輸出值將會影響到下一輪的運算，我們增加一個額外的字節(jié)用來存放相關(guān)數(shù)據(jù)，同時根據(jù)算法每次運行需左移一位的特點，我們可以把比特的運算變?yōu)樽止?jié)的運算.假設(shè)寄存器里存放x0x1x2x3x4x5x6x7八個比特的值，我們在當(dāng)前的計算中需要x0這個比特數(shù)，那么下計算中我們需要x1這個比特數(shù)，由此我們對寄存器作or或者and的操作，就可以同時更新8個比特的值.因此我們可以把的循環(huán)次數(shù)降低1/8.改進后的Quark各子算法在內(nèi)部狀態(tài)存儲上所需的字節(jié)數(shù)和基于字節(jié)的壓縮函數(shù)所需迭代輪數(shù)如下表2所示.

3.2基于布爾運算特點的非線性函數(shù)優(yōu)化基于字節(jié)操作方式優(yōu)化壓縮函數(shù)后，f,g,h三個非線性布爾函數(shù)的變換操作耗時長.由于f,g,h本身是基于比特運算的非線性函數(shù)，每次需要對輸入比特進行大量的加法和乘法運算.而在AVR環(huán)境下并沒有針對比特的上述算術(shù)操作，因而在實際計算需要對布爾函數(shù)的每一項進行運算才能得出結(jié)果.在算法的優(yōu)化過程中，我們基于布爾運算的特點，將f,g,h函數(shù)的計算過程通過同類項和提前約取的方法加以簡化.我們通過布爾函數(shù)f（x）=x0x1x2+x0×1x3（其中x0x1x2+x0x1×3表示各比特邏輯與之后再進行邏輯加運算，與Quark中表示方法一致）對優(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ù)的過程中能大大簡化所需要的布爾運算次數(shù).

優(yōu)化后的Quark算法的AVRASM偽代碼結(jié)構(gòu)如下所示.

main:

SRAM_DATA=message;callquark;ifdigestequaloutreturndigestok;elsereturndigesterror;quark:

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

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

為了比較Quark實現(xiàn)在ATtiny設(shè)備上的實際效率，我們采用ATMELATting45系列微處理器作為實驗平臺，在平臺上使用AVRASM匯編語言（編譯環(huán)境AVRStudio6.0）來實現(xiàn)D-Quark和S-Quark算法.ATtiny45系列微處理器具有4K字節(jié)可編程FlashROM,256字節(jié)EEPROM,256字節(jié)SRAM,工作模式下主頻可自適應(yīng)調(diào)整，可為20MHz.

為了對比所提出的優(yōu)化方法的效率，我們也按照Quark原始參考文獻當(dāng)中的標(biāo)準方法將D-Quark和S-Quark在相同平臺下加以實現(xiàn)并測試.各項性能數(shù)據(jù)均由AVRStudio6.0測試給出.

4結(jié)束語雖然摩爾定律預(yù)測計算機的計算速度和存儲能力每18個月能增加一倍，但由于制造成本和便攜性的限制，WSN和RFID硬件平臺的計算能力.存儲能力和能量仍然受