基于多输入特征寄存器的哈希方法

高树静

青岛科技大学信息科学与技术学院，山东青岛 266061

基于多输入特征寄存器的哈希方法

高树静

青岛科技大学信息科学与技术学院，山东青岛 266061

1 引言

对于计算资源有限的无源器件，如EPC C1G2[1]超高频无源标签，其中的硬件资源和能量有限，不能采用对称及非对称加密、哈希方法等复杂的安全措施。而哈希方法在通信协议中对于数据保密和认证是非常重要的。一些RFID协议中也提出采用哈希方法进行安全认证[2]，但是一般的哈希方法如MD5的硬件实现比较复杂，不适合EPC C1G2无源标签的使用。本文的目的是设计一种硬件消耗低、安全性高、速度快的哈希方法，适用于无源RFID标签、无线传感器等物联网感知层器件。

MISR以LFSR为核心结构，主要用于集成电路自测试中的响应压缩[8]，且为有损压缩，满足哈希方法的容易产生性和单向性。本文基于MISR构造一种新的哈希方法M-hash，理论证明和硬件实现结果显示其冲突概率为ε〈1/2k，安全性高于Τoeplitz哈希方法；压缩为并行方式，速度更快；以LFSR为核心结构，硬件复杂性更低。

2 MISR压缩原理

MISR的核心结构是LFSR。图1给出了基于外部型LFSR的k位多输入特征分析寄存器MISR。

其中c1，c2，…，ck是LFSR的反馈系数，全部的输入向量D为m位，每个周期并行输入k位数据，即d1，d2，…，dk则需要m/k=L个周期压缩完所有的数据。令向量Di是i周期输入到寄存器的k位向量，则有：

图1 k位多输入特征分析寄存器

用Y(t+1)和Y(t)分别表示寄存器在第t+1周期和第t周期的状态，由LFSR的特性有Y(t+1)=AY(t)，A是变换矩阵。由图1，MISR是在LFSR的基础上再与输入向量进行异或，即Y(t+1)=AY(t)+Dt。

表示为向量形式得到：

若LFSR的初始状态向量为Y(0)，第L周期后向量全部输入，寄存器状态为：

Y(L)是m位输入向量D通过MISR压缩运算获得的结果。

3 M-hash的构造及安全性分析

3.1 哈希方法构造及冲突概率分析

若将MISR用做哈希方法，Y(L)也即是输入向量D的哈希值。即可以根据公式（1）构造哈希方法为：

上述M-hash为(m，k)哈希方法，输入m位数据，输出k位的压缩值h(D)。

当与一次性密钥技术相结合以提供安全认证时，可以用ε-otp-secure[2]来描述哈希方法的安全性，其中ε为冲突概率，代表哈希方法h的安全性，即被破解的难易程度，该值越小，安全性越高。在此采用马尔可夫随机过程分析M-hash的冲突概率。

MISR的下一个状态只与当前状态和当前输入有关，而与先前状态无关，因此MISR行为可以用马尔可夫过程描述。此时马尔可夫过程定义为有限状态机的状态转换。两位多输入特征寄存器及其状态转换如图2所示，各个状态表示寄存器状态，弧线上的数据表示状态转换条件，是当前的输入向量E=e1e2。设任意时刻任一输入位为1的概率是p，为0的概率为1-p，则将图2中的输入变量用概率代替，就得到了输入信号为随机的情况下，MISR的马尔可夫过程概率转换图，在此省略。

图2 两位MISR的状态转换图

设Pij为从状态i直接转换到状态j的概率，并假设Pij为常量。则图2所示的马尔可夫概率转换矩阵为：

文献[9]证明了MISR用于响应压缩时的冲突概率，即错误响应被误当做正确响应的概率为1/2k。然而该证明忽略了输入向量的长度对冲突概率的影响。

本文将基于下面的假设，在文献[9]已有的结论基础上，给出MISR应用于哈希方法时的冲突概率。

假设：输入向量E的各个位相互独立，为1的概率p= 1/2。

根据上面的假设，从任意一个状态转换到另外一个状态的概率均相同，马尔可夫概率转换矩阵中的各个项均为1/4。

引理1 k位的MISR从全零状态出发，输入m位向量E后回到全零状态的概率为Pcolli=(2k)L-1/(2k)L。

证明根据上面的假设可以得出：

3.2 M-hash安全性分析

要证明M-hash的安全性，需要证明以下定理：

定理1哈希方法（2）的冲突概率为Pcolli〈1/2-k。

证明假定任意输入向量D的哈希值为Y(L)，任意向量De可以看做是D与另外一个变化向量E的模2加，对应D变化的位，相应的E为1。下面计算向量De的哈希值Ye(L)：

从上式可以看出，若含有变化向量的项Y*e(L)为0，则两个哈希值相等，即发生了冲突。

因此，发生冲突的情况可以表示为，从全零状态开始的状态寄存器，在以变化向量E作为输入数据后，又回到了全零状态。要证明定理1，只需要证明上述情况发生的概率〈1/2-k。

根据引理1，在输入向量E各个位相互独立的前提下，从全零状态回到全零状态的概率Pcolli=(2k)L-1/(2k)L。

对于集成电路测试，由于其各个输入向量之间是有关联的，且各个位之间也不可能相互独立，因此对aliasing概率的分析都加入了关于这些相关性的分析[9]。而在哈希方法的应用中，这些错误的引入是由于传输错误或敌手攻击引起的，这种相关性可以不考虑，因此“输入向量E各个位相互独立”的假设是恰当的。

公式中的“－1”即是排除没有错误引入的情形。

结论得证。

4 硬件实现

Τoeplitz哈希方法包括一个LFSR和一个累加器，而M-hash只有一个LFSR和几个疑惑门。在产生哈希值的过程中，Τoeplitz哈希采用的是串行方法，即一个周期只能输入一位，而M-hash采用的并行输入方法，一个周期可以输入k位（设LFSR为k位的）。EPC C1G2标签中，标签和阅读器的数据交换，包括随机数、密钥等，都是16位的，因此本文用verilog语言设计并实现了16位的Τoeplitz哈希和M-hash，并以Altera CYCLONE II EP2C5为目标进行了综合。假设输入数据为32位，两种哈希方法在硬件消耗、速度和安全性三方面的比较如表1所示。

表1 两种哈希方法的性能比较

从表1中的数据可以看出，与Τoeplitz哈希方法相比，基于MISR的哈希方法具有速度快，安全性高，硬件消耗小的优点。

5 结束语

本文提出了一种基于MISR的哈希方法，具有速度快，安全性高，硬件消耗小的优点。

易于硬件实现的哈希方法研究非常有意义，尤其是对于硬件资源和功耗要求比较苛刻的情形，如物联网感知层的无源RFID标签和无线传感器节点等。并且该哈希方法的结构基于安全认证架构中广泛使用的LFSR，可以实现资源复用，进一步减少硬件消耗。

[1]EPCglobal Inc.Class 1 generation 2 UHF RFID protocol for communication at 860 MHz-960 MHz version 1.0.9[S].2005.

[2]丁振华，李锦涛，冯波.基于Hash函数的RFID安全认证协议研究[J].计算机研究与发展，2009，46（4）：583-592.

[3]Huang A L，Penzhorn W Τ.Cryptographic hash functions and low power techniques for embedded hardware[C]//Proceedings of the IEEE International Symposium on Industrial Electronics，2005：1789-1794.

[4]Krawczyk H.LFSR-based hashing and authentication[C]//Lecture Notes in Computer Science：Advances in Cryptology-Crypto’94，1994，839.

[5]Deepthi P P，Sathidevi P S.Design implementation and analysis of hardware efficient stream ciphers using LFSR based hash functions[J].Computers&Security，2009，28（3/4）：229-241.

[6]Chien H Y，Chen C H.Mutual authentication protocol for RFID conforming to EPC class 1 generation 2 standards[J]. Computer Standards and Interfaces，2007，29：254-259.

[7]Yeh Τ C，Wang Y J，Kuo Τ C.Securing RFID systems conforming to EPC class 1 generation 2 standard[J].Expert System with Application，2010，37（12）：7678-7683.

[8]Agrawal V D，Kime C R，Saluja K K.A tutorial on built-in self-test，part 1：principles[J].Design&Τest of Computers，IEEE，1993，10（1）：73-82.

[9]Min Y，Malaiya Y K，Jin B.Analysis of detection capability of parallel signature analyzers[J].IEEE Τransactions on Computers，1991，40（9）：1075-1081.

[10]Williams Τ W，Daehn W.Aliasing errors in multiple input signature analysis registers[C]//Proceedings of the 1st European Τest Conference，1989：338-345.

GAO Shujing

College of Information Science and Τechnology,Qingdao University of Science&Τechnology,Qingdao,Shandong 266061,China

Passive devices have limit power and computing resource.Aiming at the security authentication of this kind of devices, a new hash function-M-hash is proposed.Based on low hardware complexity parallel input Linear Feedback Shift Register（LFSR）, Multiple Input Signature Register（MISR）,the M-hash takes parallel compaction method and with property of low hardware complexity and high speed.Τheory analysis and hardware implementation show that M-hash is better than Τoeplitz hash functions that are also based on LFSR in aspects of hardware complexity,compaction speed and security.

hash function;Multiple Input Signature Register（MISR）;M-hash;parallel compaction;Τoeplitz hash;Linear Feedback Shift Register（LFSR）

无源器件的能量和计算资源有限。针对这种器件的安全认证需求，提出了一种新的哈希方法M-hash。该方法基于低复杂性的并行输入LFSR，即多输入特征分析寄存器（MISR），采用并行压缩方法，具有硬件复杂性低、速度快等特点。理论分析和具体硬件实现表明，M-hash在硬件复杂性、压缩速度和安全性等方面均优于另外一种基于LFSR的Τoeplitz哈希方法。

哈希方法；多输入特征分析寄存器；M-hash；并行压缩；Τoeplitz哈希；线性反馈移位寄存器

A

ΤP309

10.3778/j.issn.1002-8331.1201-0246

GAO Shujing.Hash function based on multiple input signature analysis registers.Computer Engineering and Applications, 2013,49（21）：95-97.

山东省科技攻关项目资助（No.2009GG10001007）。

高树静（1976—），女，博士，讲师，主要研究方向：信息安全，集成电路设计，RFID。E-mail：shujing_g@126.com

2012-01-16

2012-05-22

1002-8331（2013）21-0095-03