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

作者：時(shí)間：2013-10-09 來(lái)源：網(wǎng)絡(luò)

加入技術(shù)交流群
- 掃碼加入
  和技術(shù)大咖面對(duì)面交流
  海量資料庫(kù)查詢

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

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

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

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

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

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