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

作者：時間：2013-10-09 來源：網絡

加入技術交流群
- 掃碼加入
  和技術大咖面對面交流
  海量資料庫查詢

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

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

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

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

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

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