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

　　摘 要： 哈希算法被广泛用于数据完整性检测.在物联网数据完整性检测中，现有标准哈希算法的软硬件开销仍需进一步降低.从低功耗AVR 微处理器的特点出发，通过基于字节的压缩函数变换操作和基于布尔运算特点的函数优化，以AVR ASM 为开发语言环境给出了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 是Sponge 构造当中所定义的rate 值和 capacity 值，P是上述 Quark 压缩函数.mi为输入消息值，在迭代轮数后， zi 为哈希输出值.

　　3 面向低功耗AVR 微处理器的Quark 哈希算法实现3.1 基于字节的压缩函数变换操作Quark 的压缩函数轮数与内部数据宽度有关.

　　以D-Quark 为例，由于其内部数据宽度为176 比特，我们采用22 个字节来存储内部数据，同时需要704轮来迭代处理数据.在普通环境实现中，我们可以采用并行化的方法，增大内部数据存储空间的方式来加快处理速度.但在受限硬件环境下，由于内存的限制，三个变换操作每轮只能输出一个比特，在AVR 微处理器环境下，算法的实际总轮数大大增加.

　　在算法的优化上，我们采用基于字节的方式来提高压缩函数的效率.在每一轮迭代过程中，由于新的输出值将会影响到下一轮的运算，我们增加一个额外的字节用来存放相关数据，同时根据算法每次运行需左移一位的特点，我们可以把比特的运算变为字节的运算.假设寄存器里存放x0 x1x2 x3 x4 x5 x6 x7八个比特的值，我们在当前的计算中需要x0 这个比特数，那么下计算中我们需要x1这个比特数，由此我们对寄存器作or 或者and 的操作，就可以同时更新8 个比特的值.因此我们可以把的循环次数降低1/8.改进后的Quark 各子算法在内部状态存储上所需的字节数和基于字节的压缩函数所需迭代轮数如下表2 所示.

　　3.2 基于布尔运算特点的非线性函数优化基于字节操作方式优化压缩函数后， f , g ,h 三个非线性布尔函数的变换操作耗时长.由于f , g , h 本身是基于比特运算的非线性函数，每次需要对输入比特进行大量的加法和乘法运算.而在AVR 环境下并没有针对比特的上述算术操作，因而在实际计算需要对布尔函数的每一项进行运算才能得出结果.在算法的优化过程中，我们基于布尔运算的特点，将f , g , h 函数的计算过程通过同类项和提前约取的方法加以简化.我们通过布尔函数  f （x） = x0 x1x2 + x 0×1 x3 （其中x0 x1 x2 + x 0x 1×3 表示各比特逻辑与之后再进行逻辑加运算，与Quark中表示方法一致）对优化方法解释如下：

　　1.如果有x0或x1等于 0,那么无论x2或x3取何值，整个函数的输出值均为0;2.如果x2或x3等于 0,那么所有包含x2或x3的项都为0;3.如果x2等于 1,那么可以把所有x2从等式中约去，对输出结果没有影响.

　　采用上述优化方法后，我们在计算f , g , h函数的过程中能大大简化所需要的布尔运算次数.

　　优化后的Quark 算法的AVR ASM 伪代码结构如下所示.

　　main:

　　SRAM_DATA = message;call quark;if digest equal outreturn digest ok;else return digest error;quark:

　　call init;call update;call final;ret虽然上述优化方法需要额外增加逻辑判断的开销，但由于f , g , h 布尔函数是固定的，所以在实际运算的过程中，增加的逻辑判断对算法的优化效果仍然比较明显.

　　3.3 实验结果通过上述优化方法，我们基于AVR 汇编语言实现了Quark 算法.基于Quark 原始论文给出的正确性测试，优化后的算法在实现上是正确的.Quark算法基于标准输入消息的相应输出结果应如下所示：

　　为了比较Quark 实现在ATtiny 设备上的实际效率，我们采用ATMEL ATting45 系列微处理器作为实验平台，在平台上使用AVR ASM 汇编语言（编译环境AVR Studio 6.0）来实现D-Quark 和S-Quark 算法.ATtiny45 系列微处理器具有4K 字节可编程Flash ROM,256 字节EEPROM,256 字节SRAM,工作模式下主频可自适应调整，可为20MHz.

　　为了对比所提出的优化方法的效率，我们也按照Quark 原始参考文献当中的标准方法将D-Quark 和S-Quark 在相同平台下加以实现并测试.各项性能数据均由AVR Studio 6.0 测试给出.

　　4 结束语虽然摩尔定律预测计算机的计算速度和存储能力每18 个月能增加一倍，但由于制造成本和便携性的限制，WSN 和RFID 硬件平台的计算能力.存储能力和能量仍然受到非常大的限制.尽管轻量级分组密码算法的研究已经引起广泛的关注，但仍然存在不少问题尚待解决.轻量级密码学作为一个新兴研究分支，需要综合密码学.电路设计和嵌入式系统等方面的研究方法和成果.Quark 哈希算法采用了面向软件的设计思路，很好的平衡了算法的安全性和软硬件实现上的效率与开销.在未来的工作中，我们将进一步地深入分析Quark 哈希算法在受限软硬件环境下的具体实现方法，为Quark 在实际中提供更充分的性能指标和算法实现参考.