低功耗低功耗AVR微处理器上微处理器上Quark 哈希算法优化实现哈希算法优化实现
摘 要: 哈希算法被广泛用于数据完整性检测.在物联网数据完整性检测中,现有标准哈希算法的软硬件开销仍需
进一步降低.从低功耗AVR 微处理器的特点出发,通过基于字节的压缩函数变换操作和基于布尔运算特点的函数
优化,以AVR ASM 为开发语言环境给出了Quark 哈希算法的优化实现,在算法实现的处理速度和存储开销上取
得较好的平衡. 1 引言物联网是继 Internet 出现之后信息技术领域的革命,它能帮助我们将信息转变为洞察
力,提高决策的质量,优化工业控制过程和生产管理,提高生产力,增强综合国力和国际竞争力.无线传感器网
络(WSN)和射频标签技术(RFID)具有硬件成本低.网络健壮性.自组织
摘 要: 哈希算法被广泛用于数据完整性检测.在物联网数据完整性检测中,现有标准哈希算法的软硬件开销仍需进一步降
低.从低功耗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 函数.输入输出长度和迭代次数上有所不同.
评论0
最新资源