低功耗AVR微处理器上Quark 哈希算法优化实现

　　1 引言物联网是继 Internet 出现之后信息技术领域的一次革命，它能帮助我们将信息转变为洞察力，提高决策的质量，优化工业控制过程和生产管理，提高生产力，增强综合国力和国际竞争力.无线传感器网络（WSN）和射频标签技术（RFID）具有硬件成本低.网络健壮性.自组织性强.适用性广泛的特点，已经成为未来信息技术重点应用“物联网”的关键组成部分.由于WSN 和RFID 基于无线网络传输信息，攻击者更加容易获得.干扰甚至破坏信息传输，信息安全的重要性不言而喻.在国际上，目前已提出不少面向受限环境的轻量级分组密码算法.如PRESENT.DESXL.LBlock和LED 算法.但在具体应用中，除了数据保密性之外，完整性检测也是保障信息安全所需的基本密码学构件.通常情况下，密码学哈希函数（如SHA-1,SHA-2 等）被用来检测消息完整性.在受限环境下，已有实验结果表明SHA-1 等常用哈希函数需要6000-8000 个门电路才能在硬件上实现，但现有数据表明一个典型RFID 标签只具有1000 到10000 个标准门电路，其中仅有200 到2000 个门电路可用于信息安全.如果采用软件方式实现，由于WSN与RFID 往往只具有8 比特CPU 和KB 级别的存储能力，安全算法同样面对ROM.RAM 和处理器性能上的严格限制.过多的存储和计算开销也会增大对能量的消耗，降低算法的实用性，这在WSN 和RFID 环境下同样是不可接受的.

　　SHA-3 竞赛虽然将会选出新的哈希算法作为国际标准，但选择依据并没有将传感器和RFID 等资源受限环境下的实现开销和性能作为评选准则，从进入最后一轮的5 个候选算法来看，除了Keccak可以通过参数设置来降低开销以适应低功耗环境之外，其他4 种算法均不具备受限环境下轻量级性质.在文献中，Bogdanov 等人采用基于分组密码的构造方式，基于PRESENT 给出了满足RFID 资源限制的轻量级哈希算法.在已公开文献中，也有若干哈希算法在设计当中直接考虑了受限环境下的实用性，如MAME.Photon和Quark等.但从实验结果来看， 上述算法的实现仍然需要4000-6000 个门电路，虽然上述哈希算法与标准环境下广泛应用的算法（如SHA-1,SHA-2 等）相比有比较大的软硬件开销优势，但在受限环境下，其软硬件开销仍需进一步降低才能具有比较好的实用价值.此外，国内虽然已有若干针对轻量级分组密码算法的安全性与优化实现分析，但针对轻量级哈希算法的比较少，需要进一步研究.

爱特梅尔（ATMEL）公司设计并生产的AVR系列微控制器由于其出色的指令集设计和优秀的性价比，在嵌入式应用环境下成为了广泛采用的解决方案.在AVR 微控制器家族中，ATtiny 系列具有低功耗.成本低.开发环境友善等优点，在无线传感器和RFID 领域得到了广泛的应用.在本文中，我们从ATtiny 微处理器的特点出发，基于AVRASM 语言给出了QUARK 哈希算法的优化实现.由于Quark 算法并没有采用传统的S 盒来实现非线性性，在算法优化上并不能简单套用分组密码算法的优化方法.基于Quark 算法的特点，我们采用了基于字节与布尔函数运算特点相结合的方法，从而算法实现的处理速度和存储开销三方面数据上取得较好的平衡.实际试验数据表明，优化后的Quark算法实现在ATtiny 微处理器平台下与传统实现相比具有较大优势.

　　2 Quark 哈希算法简介在 CHES 2010 会议上，Aumasson 等人提出了一种名为Quark 的新型轻量级哈希算法.算法基于压缩函数和迭代运算两部分组成.压缩函数基于不同的输出长度，Quark 分为U-Quark,D-Quark和S-Quark 三种子算法，相关参数如下表1 所示.

　　出于低功耗的考虑，Quark 的压缩函数大量借鉴了轻量级流密码Grain和分组密码Katan的构造方法.如下图1 所示，Quark 的压缩函数基于两个非线性反馈移位寄存器（NFSR）X 和Y 用以增加输出的非线性度，另外再采用一个线性反馈移位寄存器（LFSR）L 为每一轮压缩函数的执行提供轮常量，使得滑动攻击等基于迭代构造的攻击不再有效.布尔函数f , g , h 将输入值按照固定的非线性方程的方式输出一个比特.函数p 仅仅只对L的输出进行一个线性变换.对于不同参数的Quark 子函数而言，压缩函数结构上是完全一致的，仅在f ,g ,h 函数.输入输出长度和迭代次数上有所不同.

在迭代结构上，Quark 采用了在新型哈希算法设计中广泛被采用的Sponge 构造.与传统的Merkle-Damgard 构造相比，Sponge 构造对于长消息攻击和随机预言机区分攻击有着非常好的可证明安全性.同时在低功耗设备的实现上，实验结果表明基于Sponge 结构的哈希算法能节约大量的内存开销.下图2 中描述了基于Sponge 构造的Quark迭代方式，其中r 和c 是Spo