高樹靜

青島科技大學(xué)信息科學(xué)與技術(shù)學(xué)院，山東青島 266061

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

高樹靜

青島科技大學(xué)信息科學(xué)與技術(shù)學(xué)院，山東青島 266061

1 引言

對于計算資源有限的無源器件，如EPC C1G2[1]超高頻無源標簽，其中的硬件資源和能量有限，不能采用對稱及非對稱加密、哈希方法等復(fù)雜的安全措施。而哈希方法在通信協(xié)議中對于數(shù)據(jù)保密和認證是非常重要的。一些RFID協(xié)議中也提出采用哈希方法進行安全認證[2]，但是一般的哈希方法如MD5的硬件實現(xiàn)比較復(fù)雜，不適合EPC C1G2無源標簽的使用。本文的目的是設(shè)計一種硬件消耗低、安全性高、速度快的哈希方法，適用于無源RFID標簽、無線傳感器等物聯(lián)網(wǎng)感知層器件。

MISR以LFSR為核心結(jié)構(gòu)，主要用于集成電路自測試中的響應(yīng)壓縮[8]，且為有損壓縮，滿足哈希方法的容易產(chǎn)生性和單向性。本文基于MISR構(gòu)造一種新的哈希方法M-hash，理論證明和硬件實現(xiàn)結(jié)果顯示其沖突概率為ε〈1/2k，安全性高于Τoeplitz哈希方法；壓縮為并行方式，速度更快；以LFSR為核心結(jié)構(gòu)，硬件復(fù)雜性更低。

2 MISR壓縮原理

MISR的核心結(jié)構(gòu)是LFSR。圖1給出了基于外部型LFSR的k位多輸入特征分析寄存器MISR。

其中c1，c2，…，ck是LFSR的反饋系數(shù)，全部的輸入向量D為m位，每個周期并行輸入k位數(shù)據(jù)，即d1，d2，…，dk則需要m/k=L個周期壓縮完所有的數(shù)據(jù)。令向量Di是i周期輸入到寄存器的k位向量，則有：

圖1 k位多輸入特征分析寄存器

用Y(t+1)和Y(t)分別表示寄存器在第t+1周期和第t周期的狀態(tài)，由LFSR的特性有Y(t+1)=AY(t)，A是變換矩陣。由圖1，MISR是在LFSR的基礎(chǔ)上再與輸入向量進行異或，即Y(t+1)=AY(t)+Dt。

表示為向量形式得到：

若LFSR的初始狀態(tài)向量為Y(0)，第L周期后向量全部輸入，寄存器狀態(tài)為：

Y(L)是m位輸入向量D通過MISR壓縮運算獲得的結(jié)果。

3 M-hash的構(gòu)造及安全性分析

3.1 哈希方法構(gòu)造及沖突概率分析

若將MISR用做哈希方法，Y(L)也即是輸入向量D的哈希值。即可以根據(jù)公式（1）構(gòu)造哈希方法為：

上述M-hash為(m，k)哈希方法，輸入m位數(shù)據(jù)，輸出k位的壓縮值h(D)。

當(dāng)與一次性密鑰技術(shù)相結(jié)合以提供安全認證時，可以用ε-otp-secure[2]來描述哈希方法的安全性，其中ε為沖突概率，代表哈希方法h的安全性，即被破解的難易程度，該值越小，安全性越高。在此采用馬爾可夫隨機過程分析M-hash的沖突概率。

MISR的下一個狀態(tài)只與當(dāng)前狀態(tài)和當(dāng)前輸入有關(guān)，而與先前狀態(tài)無關(guān)，因此MISR行為可以用馬爾可夫過程描述。此時馬爾可夫過程定義為有限狀態(tài)機的狀態(tài)轉(zhuǎn)換。兩位多輸入特征寄存器及其狀態(tài)轉(zhuǎn)換如圖2所示，各個狀態(tài)表示寄存器狀態(tài)，弧線上的數(shù)據(jù)表示狀態(tài)轉(zhuǎn)換條件，是當(dāng)前的輸入向量E=e1e2。設(shè)任意時刻任一輸入位為1的概率是p，為0的概率為1-p，則將圖2中的輸入變量用概率代替，就得到了輸入信號為隨機的情況下，MISR的馬爾可夫過程概率轉(zhuǎn)換圖，在此省略。

圖2 兩位MISR的狀態(tài)轉(zhuǎn)換圖

設(shè)Pij為從狀態(tài)i直接轉(zhuǎn)換到狀態(tài)j的概率，并假設(shè)Pij為常量。則圖2所示的馬爾可夫概率轉(zhuǎn)換矩陣為：

文獻[9]證明了MISR用于響應(yīng)壓縮時的沖突概率，即錯誤響應(yīng)被誤當(dāng)做正確響應(yīng)的概率為1/2k。然而該證明忽略了輸入向量的長度對沖突概率的影響。

本文將基于下面的假設(shè)，在文獻[9]已有的結(jié)論基礎(chǔ)上，給出MISR應(yīng)用于哈希方法時的沖突概率。

假設(shè)：輸入向量E的各個位相互獨立，為1的概率p= 1/2。

根據(jù)上面的假設(shè)，從任意一個狀態(tài)轉(zhuǎn)換到另外一個狀態(tài)的概率均相同，馬爾可夫概率轉(zhuǎn)換矩陣中的各個項均為1/4。

引理1 k位的MISR從全零狀態(tài)出發(fā)，輸入m位向量E后回到全零狀態(tài)的概率為Pcolli=(2k)L-1/(2k)L。

證明根據(jù)上面的假設(shè)可以得出：

3.2 M-hash安全性分析

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

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

證明假定任意輸入向量D的哈希值為Y(L)，任意向量De可以看做是D與另外一個變化向量E的模2加，對應(yīng)D變化的位，相應(yīng)的E為1。下面計算向量De的哈希值Ye(L)：

從上式可以看出，若含有變化向量的項Y*e(L)為0，則兩個哈希值相等，即發(fā)生了沖突。

因此，發(fā)生沖突的情況可以表示為，從全零狀態(tài)開始的狀態(tài)寄存器，在以變化向量E作為輸入數(shù)據(jù)后，又回到了全零狀態(tài)。要證明定理1，只需要證明上述情況發(fā)生的概率〈1/2-k。

根據(jù)引理1，在輸入向量E各個位相互獨立的前提下，從全零狀態(tài)回到全零狀態(tài)的概率Pcolli=(2k)L-1/(2k)L。

對于集成電路測試，由于其各個輸入向量之間是有關(guān)聯(lián)的，且各個位之間也不可能相互獨立，因此對aliasing概率的分析都加入了關(guān)于這些相關(guān)性的分析[9]。而在哈希方法的應(yīng)用中，這些錯誤的引入是由于傳輸錯誤或敵手攻擊引起的，這種相關(guān)性可以不考慮，因此“輸入向量E各個位相互獨立”的假設(shè)是恰當(dāng)?shù)摹?/p>

公式中的“－1”即是排除沒有錯誤引入的情形。

結(jié)論得證。

4 硬件實現(xiàn)

Τoeplitz哈希方法包括一個LFSR和一個累加器，而M-hash只有一個LFSR和幾個疑惑門。在產(chǎn)生哈希值的過程中，Τoeplitz哈希采用的是串行方法，即一個周期只能輸入一位，而M-hash采用的并行輸入方法，一個周期可以輸入k位（設(shè)LFSR為k位的）。EPC C1G2標簽中，標簽和閱讀器的數(shù)據(jù)交換，包括隨機數(shù)、密鑰等，都是16位的，因此本文用verilog語言設(shè)計并實現(xiàn)了16位的Τoeplitz哈希和M-hash，并以Altera CYCLONE II EP2C5為目標進行了綜合。假設(shè)輸入數(shù)據(jù)為32位，兩種哈希方法在硬件消耗、速度和安全性三方面的比較如表1所示。

表1 兩種哈希方法的性能比較

從表1中的數(shù)據(jù)可以看出，與Τoeplitz哈希方法相比，基于MISR的哈希方法具有速度快，安全性高，硬件消耗小的優(yōu)點。

5 結(jié)束語

本文提出了一種基于MISR的哈希方法，具有速度快，安全性高，硬件消耗小的優(yōu)點。

易于硬件實現(xiàn)的哈希方法研究非常有意義，尤其是對于硬件資源和功耗要求比較苛刻的情形，如物聯(lián)網(wǎng)感知層的無源RFID標簽和無線傳感器節(jié)點等。并且該哈希方法的結(jié)構(gòu)基于安全認證架構(gòu)中廣泛使用的LFSR，可以實現(xiàn)資源復(fù)用，進一步減少硬件消耗。

[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函數(shù)的RFID安全認證協(xié)議研究[J].計算機研究與發(fā)展，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。該方法基于低復(fù)雜性的并行輸入LFSR，即多輸入特征分析寄存器（MISR），采用并行壓縮方法，具有硬件復(fù)雜性低、速度快等特點。理論分析和具體硬件實現(xiàn)表明，M-hash在硬件復(fù)雜性、壓縮速度和安全性等方面均優(yōu)于另外一種基于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.

山東省科技攻關(guān)項目資助（No.2009GG10001007）。

高樹靜（1976—），女，博士，講師，主要研究方向：信息安全，集成電路設(shè)計，RFID。E-mail：shujing_g@126.com

2012-01-16

2012-05-22

1002-8331（2013）21-0095-03