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

温雅敏，黎凤霞，龚 征，唐韶华

1.广东商学院 数学与计算科学学院，广州 510320

2.华南理工大学 计算机科学与工程学院，广州 510641

3.华南师范大学 计算机学院，广州 510631

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

温雅敏1，黎凤霞2，龚 征3，唐韶华2

1.广东商学院 数学与计算科学学院，广州 510320

2.华南理工大学 计算机科学与工程学院，广州 510641

3.华南师范大学 计算机学院，广州 510631

1 引言

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

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

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

2 Quark哈希算法简介

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

表1 Quark哈希算法参数设置

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

图1 Quark压缩函数的构造

在迭代结构上，Quark采用了在新型哈希算法设计中广泛被采用的Sponge构造[14]。与传统的Merkle-Damgard构造相比，Sponge构造对于长消息攻击和随机预言机区分攻击有着非常好的可证明安全性。同时在低功耗设备的实现上，实验结果表明基于Sponge结构的哈希算法能节约大量的内存开销。图2中描述了基于Sponge构造的Quark迭代方式，其中r和c是Sponge构造当中所定义的rate值和capacity值，P是上述Quark压缩函数。mi为输入消息值，在迭代轮数后，zi为哈希输出值。

图2 基于Sponge构造的Quark迭代方式

3 面向低功耗AVR微处理器的Quark哈希算法实现

3.1 基于字节的压缩函数变换操作

Quark的压缩函数轮数与内部数据宽度有关。以D-Quark为例，由于其内部数据宽度为176 bit，采用22个字节来存储内部数据，同时需要704轮来迭代处理数据。在普通环境实现中，可以采用并行化的方法，增大内部数据存储空间的方式来加快处理速度。但在受限硬件环境下，由于内存的限制，三个变换操作每轮只能输出一个比特，在AVR微处理器环境下，算法的实际总轮数大大增加。在算法的优化上，采用基于字节的方式来提高压缩函数的效率。在每一轮迭代过程中，由于新的输出值将会影响到下一轮的运算，增加一个额外的字节用来存放相关数据，同时根据算法每次运行需左移一位的特点，可以把比特的运算变为字节的运算。假设寄存器里存放x0x1x2x3x4x5x6x7八个比特的值，在当前的计算中需要x0这个比特数，那么下一次计算中需要x1这个比特数，由此对寄存器作or或者and的操作，就可以同时更新8个比特的值。因此可以把循环次数降低1/8。改进后的Quark各子算法在内部状态存储上所需的字节数和基于字节的压缩函数所需迭代轮数如表2所示。

表2 基于字节的Quark压缩函数参数设置

3.2 基于布尔运算特点的非线性函数优化

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

（1）如果有 x0或 x1等于0，那么无论 x2或 x3取何值，整个函数的输出值均为0。

（2）如果 x2或 x3等于0，那么所有包含 x2或 x3的项都为0。

（3）如果x2等于1，那么可以把所有 x2从等式中约去，对输出结果没有影响。

采用上述优化方法后，在计算 f，g，h函数的过程中能大大简化所需要的布尔运算次数。优化后的Quark算法的AVR ASM伪代码结构如下所示。

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

3.3 实验结果

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

（1）初始值

（2）在输入消息为空（即分别为17、22、32 Byte的空数组）的情况下

为了比较Quark实现在ATtiny设备上的实际效率，采用ATMEL ATting45系列微处理器作为实验平台，在平台上使用AVR ASM汇编语言（编译环境AVR Studio 6.0）来实现D-Quark和S-Quark算法。ATtiny45系列微处理器具有4 kByte可编程Flash ROM，256 Byte EEPROM，256 Byte SRAM，工作模式下主频可自适应调整，最大可为20 MHz。为了对比所提出的优化方法的效率，也按照Quark原始参考文献当中的标准方法将D-Quark和S-Quark在相同平台下加以实现并测试。各项性能数据均由AVR Studio 6.0测试给出。

表3 QUARK算法在ATtiny 45微处理器实现性能比较

4 结束语

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

[1]Bogdanov A，Knudsen L R，Leander G，et al.PRESENT：an ultra-lightweight block cipher[C]//LNCS 4727：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2007），Vienna，Austria，2007：450-466.

[2]Guo Jian，Peyrin T，Poschmann A，et al.The LED block cipher[C]//LNCS 6917：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2011），Nara，Japan，2011：326-341.

[3]Wu Wenling，Zhang Lei.LBlock：a lightweight block cipher[C]//LNCS 6715：Applied Cryptography and Network Security（ACNS 2011），Nerja，Spain，2011：327-344.

[4]Poschmann A.Lightweight cryptography-cryptographic engineering for a pervasive world[D].Bochum，Germany：Ruhr-University，2009.

[5]Juels A，Weis S A.Authenticating pervasive devices with human protocols[C]//LNCS 3126：Advances in Cryptology（CRYPTO 2005），Santa Barbara，California，USA，2005：293-308.

[6]Bogdanov A，Leander G，Paar C，et al.Hash functions and RFID tags：mind the gap[C]//LNCS 5154：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2008），Washington，DC，USA，2008：283-299.

[7]Yoshida H，Watanabe D，Okeya K，et al.MAME：a compression function with reduced hardware requirements[C]// LNCS 4727：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2007），Vienna，Austria，2007：148-165.

[8]Guo Jian，Peyrin T，Poschmann A.The photon family of lightweight hash[C]//LNCS 6841：Advances in Cryptology（CRYPTO 2011），Santa Barbara，California，USA，2011：222-239.

[9]Aumasson J，Henzen L，Meier W，et al.Quark：a lightweight hash[C]//LNCS 6225：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2010），Santa Barbara，USA，2010：1-15.

[10]葛十景.代数分析及其对若干轻量级分组密码的应用[D].上海：上海交通大学，2011.

[11]李玮，谷大武，赵辰，等.物联网环境下LED轻量级分组加密算法的安全性分析[J].计算机学报，2012（3）：434-445.

[12]Hell M，Johansson T，Meier W.Grain：a stream cipher for constrained environments[J].IJWMC，2007，2（1）：86-93.

[13]De Canniere C，Dunkelman O，Knezevic M.KATAN and KTANTAN-a family of small and efficient hardwareoriented block ciphers[C]//LNCS 5747：Workshop on Cryptographic Hardware and Embedded Systems（CHES 2009），Lausanne，Switzerland，2009：272-288.

[14]Bertoni G，Daemen J，Peeters M，et al.On the indifferentiability of the sponge construction[C]//LNCS 4965：Advances in Cryptology （EUROCRYPT 2008），Istanbul，Turkey，2008：181-197.

WEN Yamin1,LI Fengxia2,GONG Zheng3,TANG Shaohua2

1.School of Mathematics and Computational Science,Guangdong University of Business Studies,Guangzhou 510320,China
2.School of Computer Science and Technology,South China University of Technology,Guangzhou 510641,China
3.School of Computer,South China Normal University,Guangzhou 510631,China

Cryptographic hash functions are widely used for data integrity.The hash functions for standard environment need to be reduced for the applications in the Internet of Things.In this paper,based on the properties of AVR low-cost microcontrollers,it proposes an optimized implementation of the Quark hash function with AVR ASM.The optimized implementation makes a good balance between the processing speed and storage costs.

cryptographic algorithms;lightweight hash function;Quark;ATtiny

哈希算法被广泛用于数据完整性检测。在物联网数据完整性检测中，现有标准哈希算法的软硬件开销仍需进一步降低。从低功耗AVR微处理器的特点出发，通过基于字节的压缩函数变换操作和基于布尔运算特点的函数优化，以AVR ASM为开发语言环境给出了Quark哈希算法的优化实现，在算法实现的处理速度和存储开销上取得较好的平衡。

密码学算法；轻量级哈希函数；Quark；ATtiny

A

TP309.7

10.3778/j.issn.1002-8331.1301-0029

WEN Yamin,LI Fengxia,GONG Zheng,et al.Optimized implementation of Quark hash function for lightweight AVR microcontrollers.Computer Engineering and Applications,2014,50（23）：104-107.

国家自然科学基金（No.61100201，No.61170080，No.U1135004）；广东省自然科学基金（No.S2012040006711，No.S2012010010376）；广东省教育厅育苗工程（No.LYM11053）；广东商学院校级科研项目（No.11BS41301）。

温雅敏（1981—），女，博士，讲师，研究领域为密码学与信息安全；黎凤霞，女，硕士研究生，研究领域为信息安全；龚征（1981—），男，博士，副教授，研究领域为信息系统安全；唐韶华（1970—），男，博士，教授，研究领域为信息安全。E-mail：ya-min.wen@gmail.com

2013-01-06

2013-03-22

1002-8331（2014）23-0104-04

CNKI网络优先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1648.017.html