低功耗AVR微处理器上Quark 哈希算法优化实现-技术方案

精品文档-下载后可编辑低功耗AVR微处理器上Quark哈希算法优化实现-技术方案摘要：哈希算法被广泛用于数据完整性检测.在物联网数据完整性检测中，现有标准哈希算法的软硬件开销仍需进一步降低.从低功耗AVR微处理器的特点出发，通过基于字节的压缩函数变换操作和基于布尔运算特点的函数优化，以AVRASM为开发语言环境给出了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微处理器平台下与传统实现相比具有较大优势.

2Quark哈希算法简介在CHES2022会议上，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微处理器环境下，算法的实际总轮数大大增加.

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

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

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

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

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

main:

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

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

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

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

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

4结束语虽然摩尔定律预测计算机的计算速度和存储能力每18个月能增加一倍，但由于制造成本和便携性的限制，WSN和RFID硬件平台的计算能力.存储能力和能量仍然受