姜 曉， 馬昌社

(華南師范大學計算機學院, 廣州 510631)

對HB#協(xié)議的代數(shù)分析

姜 曉， 馬昌社*

(華南師范大學計算機學院, 廣州 510631)

HB協(xié)議是一類對計算要求極低的認證協(xié)議，能夠抵抗量子攻擊，非常適合于移動和物聯(lián)網(wǎng)環(huán)境，而這種無線通信環(huán)境要求HB協(xié)議應該具有抗中間人攻擊的能力. 基于此，設(shè)計了一種對HB#協(xié)議進行中間人攻擊的代數(shù)分析方法，在這種代數(shù)攻擊中，認證密鑰可以被快速地恢復. 這一攻擊方法建立在Z2中一類多元二次方程組的解的基礎(chǔ)之上，首先找到了這類方程組有解的充分必要條件和求解算法，然后利用這一結(jié)果對HB#協(xié)議進行中間人攻擊.

HB協(xié)議； 代數(shù)攻擊； 中間人攻擊

LPN(Learning Parity with Noisy)[1]是計算復雜性理論領(lǐng)域內(nèi)一個研究眾多的困難問題，得到了安全界的高度關(guān)注. 首先，密碼學界基于LPN設(shè)計了對稱加密[2]、公鑰加密[3]等諸多密碼方案. 其次，LPN已成為最有可能為計算資源非常有限的設(shè)備提供身份識別和認證方案的設(shè)計工具[4]. 在這方面，自從HB協(xié)議[5]被提出來以后，相繼出現(xiàn)了HB+[6]、RANDOM-HB#[7]和Auth[8]等眾多基于LPN的認證協(xié)議. 這些協(xié)議統(tǒng)稱為HB類型協(xié)議.

由于HB類型協(xié)議具有計算要求低和實現(xiàn)代碼短的優(yōu)點，它通常被用來設(shè)計RFID(Radio Frequency Identification)認證協(xié)議[9-12]. 而RFID系統(tǒng)中標簽的被動性、RFID環(huán)境的開放性、標簽的低成本要求和無線通訊方式給攻擊者提供了大量的可用漏洞和資源[13]，尤其是給中間人攻擊[14]帶來了諸多便利條件.

HB協(xié)議[5]的執(zhí)行過程如圖1所示. 容易看出HB協(xié)議中僅涉及比特加法和乘法，其計算要求非常低. HB協(xié)議能夠抵御在線竊聽等被動攻擊，但是無法抵御主動攻擊：攻擊者只要選擇k個線性無關(guān)的挑戰(zhàn)向量，對每一個挑戰(zhàn)向量發(fā)起多次主動攻擊查詢，利用Chernoff定理[3]便可獲得其與密鑰x的內(nèi)積，然后用高斯消元法解線性方程組即可得到密鑰x.

圖1 HB認證協(xié)議

HB+協(xié)議具有主動安全性[6]，但不能抗中間人攻擊[14]. RANDOM-HB#協(xié)議[7]能抗GRS中間人攻擊，但密鑰的存儲量太大，不符合RFID低成本標簽的設(shè)計要求，而且不能抵抗一般中間人攻擊[15]． 相對于HB+協(xié)議和RANDOM-HB#協(xié)議的3輪通信，KILTZ等[8]提出2輪認證協(xié)議——Auth協(xié)議，但Auth協(xié)議仍然無法抵抗中間人攻擊[16].

在抗中間人攻擊研究方面，KILTZ等[8]提出了基于LPN的MAC(Message Authentication Code)，此協(xié)議能夠抗一般中間人攻擊,但需要用到兩兩獨立的置換，超出了LPN的范圍[17]． 最近，唐靜和姬東耀[18]提出一個基于LPN的抗中間人攻擊的認證協(xié)議HB#，但本文將分析其仍然不能抵抗中間人攻擊．

由于LPN問題呈現(xiàn)出良好的線性代數(shù)特性，導致其容易遭受代數(shù)攻擊[19]. 本文采用代數(shù)攻擊方法對HB#協(xié)議進行攻擊，將密碼體制的加密活動描述為輸入(密鑰)和輸出之間的多元方程組，并且通過求解方程組來恢復密鑰. 每個密碼都可以描述為Z2上的多元方程組[20]，而解Z2上的非線性多元方程組的問題通常都是NP問題[20-21]. 因此，要想對某個安全方案進行代數(shù)分析，首先要找到該安全方案對應的多元非線性方程組的求解方法. 本文首先對Z2中一類多元二次方程組進行研究，給出其求解算法及該方程組有解的充分必要條件；然后利用GRS攻擊原理[14]設(shè)計了對HB#協(xié)議[18]的中間人攻擊算法，在該算法中，把認證密鑰的恢復歸約到這一方程組的求解，完成對HB#協(xié)議的中間人攻擊.

1 預備知識

1.1 符號說明

1.2 LPN問題

1.3 環(huán)排列

把k個不同的元素按照圓圈排列，這種排列叫做環(huán)排列[22]. 2個環(huán)排列是同一排列，若環(huán)排列中同一元素的左右鄰居沒有改變. 由(c0,c1,c2,…,ck-1)組成的環(huán)排列(圖2)易知，由k個不同元素組成的環(huán)排列共有(k-1)!個.

圖2 環(huán)排列(c0,c1,c2,…,ck-1)

2 HB# 協(xié)議

為了解決HB協(xié)議不能抵御主動攻擊的問題，JUELS和WEIS[6]設(shè)計了HB+協(xié)議. 與HB協(xié)議的2輪認證不同的是，HB+協(xié)議中閱讀器與標簽之間增加了另外一個共享的k比特密鑰y，HB+協(xié)議中需要標簽首先產(chǎn)生k比特向量b發(fā)給閱讀器，并把b加入到驗證值z的計算中,即z=a·xb·yv. 正是b的隨機性使得攻擊者無法利用主動攻擊得到密鑰，這樣HB+協(xié)議實現(xiàn)了主動安全性. 但是HB+協(xié)議仍然無法抵御中間人攻擊：文獻[14]提出的一種中間人攻擊的方法(簡稱GRS攻擊)，成功地對HB+協(xié)議進行了中間人攻擊. GRS攻擊原理為：攻擊者通過“攔截消息-修改消息-發(fā)送消息”的方式[14]對閱讀器和標簽之間的通信進行干預，同時需要構(gòu)建一些參數(shù)使認證通過，從而獲得所需要的信息，這樣經(jīng)過多次攻擊之后攻擊者能夠成功恢復出密鑰. 下面具體闡述對HB+協(xié)議的GRS攻擊.

針對HB+協(xié)議，攻擊者偽裝成合法的標簽，截獲每次閱讀器發(fā)送的a，通過異或上同一個k比特向量б將a篡改為a′=aб；攻擊者再偽裝成合法的閱讀器將a發(fā)送給標簽；閱讀器按照HB+協(xié)議驗證a·xb·y=z是否成立. 整個攻擊過程中，攻擊者通過選擇合適的б(比如б=(1,0,…,0))，通過一個完整的認證協(xié)議執(zhí)行過程，根據(jù)認證結(jié)果即可恢復出密鑰x的第一個比特，重復這個過程k次就可以恢復出密鑰x的所有比特. 具體的GRS中間人攻擊如圖3所示.

圖3 GRS攻擊

針對HB+協(xié)議不能抵抗中間人攻擊的問題，唐靜和姬東耀[18]提出了宣稱能夠抵抗中間人攻擊的HB#協(xié)議. 與HB+協(xié)議不同的是，HB#協(xié)議中標簽端先對挑戰(zhàn)消息a進行一次非線性運算f，然后再按HB+的方式產(chǎn)生認證碼z. 本文研究發(fā)現(xiàn)文獻[18]提出的改進方法仍不能抵抗中間人攻擊.

具體的HB#協(xié)議為：閱讀器與標簽共享2個k比特密鑰x=(x0,x1,…,xk-1)和k比特密鑰y=(y0,y1,y2,…,yk-1). 標簽擁有1個噪聲發(fā)生器，以ηa(0，1/2)的概率生成噪聲v(即Pr[v=1]=η). 1個完整的HB#協(xié)議包括r次協(xié)議執(zhí)行，在1次協(xié)議中，標簽隨機生成k比特向量b并發(fā)送其給閱讀器. 閱讀器收到后隨機生成k比特向量a并發(fā)送其給標簽. 標簽計算驗證碼z=f(a)·x(b·y)v然后發(fā)送z給閱讀器，閱讀器檢驗f(a)·x(b·y)v=z是否成立. 這樣進行r次交互后，如果標簽響應錯誤的次數(shù)小于某個閥值ω，則認證通過. HB#認證協(xié)議的具體流程如圖4所示，其中f是一個非線性函數(shù)，假設(shè)k比特向量則f(a)=f(a0,a1,…,ak-2,ak-1)=(a0a1,a1a2,…,ak-2ak-1,ak-1a0).

圖4 HB#認證協(xié)議

3 HB# 協(xié)議中間人攻擊

3.1 HB#協(xié)議中間人攻擊原理

在HB#協(xié)議中，對挑戰(zhàn)消息a進行線性篡改(把a改成aб)后把f(aб)拆分成f(a)+g(a,б)的形式，然后利用閱讀器，攻擊者就可以獲得g(a,б)與標簽密鑰的內(nèi)積，重復這一過程多次，可以建立以標簽密鑰為未知數(shù)的方程組，解方程組就可以得到標簽密鑰，從而完成中間人攻擊.

具體來講，攻擊者偽裝成一個合法的標簽，截獲每一次閱讀器發(fā)送的a，異或上一個k比特向量б，然后偽裝成合法的閱讀器將a′=aб發(fā)送給標簽. 標簽收到后計算z=f(a′)·xb·yv并將z發(fā)回去，閱讀器檢驗是否f(a)·xb·y=z.

每次認證中閱讀器給出的a是隨機的，要求攻擊者每次通過選取б來消除由a帶來的差異，使得多次認證中f(aб)-f(a)的結(jié)果以較大概率相同. 定義函數(shù)g(a,б)=f(aб)-f(a)，則標簽計算

z=f(a′)·xb·yv=f(aб)·xb·yv=f(a)·xb·yg(a,б)·xv.

而閱讀器可以幫助攻擊者驗證f(a)·xg(a,б)·xv，從而獲得g(a,б)·xv的值，則攻擊者經(jīng)過多次攻擊就可以以很大概率獲得g(a,б)·x的值，進一步根據(jù)r次交互認證的認證結(jié)果恢復密鑰x. HB#協(xié)議的中間人攻擊過程如圖5所示.

圖5 HB#協(xié)議的中間人攻擊

3.2 HB#協(xié)議中間人攻擊實施

z=f(a′)·x(b·y)v=f(a)·x(b·y)g(a, б)·xv=f(a)·x(b·y)(1,0,0,…,0)·(x0,x1,x2,…,xk-1)v=f(a)·x(b·y)x0v.

r次交互以后，如果標簽認證通過則設(shè)置x0=0，否則x0=1. 同樣的方法，攻擊者在接下來的攻擊中選擇б滿足f(aб)=f(a)+(0,1,0,…,0)即可判斷x1的值. 最后攻擊者選擇б滿足f(aб即可判斷出xk-1的值，這樣，攻擊者就成功恢復密鑰x.

攻擊者得到密鑰x后可以成功冒充標簽與閱讀器進行通信，有2種方式：

(1)無需恢復密鑰y：鑒于HB#協(xié)議中b由標簽給定，因此攻擊者可以每次設(shè)定b=(b0,b1,b2,…,bk-1)=(0,0,0,…,0)，則由攻擊者發(fā)送給閱讀器的z值為：z=f(a)·x(0,0,0,…,0)·yv=f(a)·xv. 這樣進行r次后，如果閱讀器收到錯誤響應的次數(shù)小于ω，則攻擊者冒充標簽成功. 攻擊者冒充標簽的攻擊過程如圖6所示.

圖6 標簽冒充攻擊

(2)選取k個線性無關(guān)的向量b，根據(jù)認證結(jié)果構(gòu)成線性方程組，用高斯消元法解矩陣方程恢復密鑰y：HB#協(xié)議中密鑰y表示為y=(y0,y1,y2,…,yk-1)，攻擊者首先選取b=(b0,b1,b2,…,bk-1)=(1,0,0,…,0)，則攻擊者計算z=f(a)·x(1,0,0,…,0)·(y0,y1,y2,…,yk-1)v=f(a)·xy0v，保持b不變，攻擊者與閱讀器進行r次交互，并將r次認證后閱讀器對攻擊者的認證結(jié)果記為d0(若認證通過d0=0，否則d0=1). 同樣的方法，攻擊者選取b=(0,1,0,…,0)，則計算z=f(a)·x(0,1,0,…,0)·(y0,y1,y2,…,yk-1)v=f(a)·xy1v，重復進行r次，并將閱讀器對攻擊者的認證結(jié)果記為d1. 最后選取b=(0,0,0,…,1)，并將閱讀器對攻擊者的認證結(jié)果記為dk-1. 易知，密鑰y=(d0,d1,d2,…,dk-1)，即攻擊者成功恢復密鑰y.

3.3 HB#中間人攻擊算法的分析

首先考慮一類Z2上多元二次方程組的解. 設(shè)u0,u1,…,uk-1aZ2為未知數(shù)，c0,c1,c2,…,ck-1?Z2為已知數(shù). 關(guān)于u0,u1,…,uk-1的二次方程組為：

(1)

一般地，求解Z2的多元二次方程組是一個NP困難問題[16-17]，但對于某些特殊方程組可以快速求解. 關(guān)于方程組(1)求解的情況如引理1所述：

引理1 方程組(1)有解的充要條件是：環(huán)排列(c0,c1,c2,…,ck-1)中不含有子串“101”.

證明 必要性：已知方程組(1)有解，將證明環(huán)排列(c0,c1,c2,…,ck-1)中不含有子串“101”.

由uiui+1=1可得ui=ui+1=1；由ui+2ui+3=1可得ui+2=ui+3=1. 據(jù)此ui+1ui+2≠0，即不存在ui、ui+1、ui+2和ui+3滿足uiui+1=1、ui+2ui+3=1且ui+1ui+2=0，故方程組(1)無解.

充分性：已知環(huán)排列(c0,c1,c2,…,ck-1)中不含有子串“101”，接下來將證明方程組(1)有解. 求出方程組(1)的一個解的多項式時間算法如下:

for(i=1;i≤k;i++)

if(ci==1) then

ui=ui+1=1;

elseui+1=0.

算法的正確性分析：如果當前i滿足ci=1，由uiu(i+1)mod k=1可知ui=u(i+1)mod k=1；如果ci=0，由于環(huán)排列(c0,c1,c2,…,ck-1)中不含有子串“101”，則c(i+1)mod k=0或者c(i-1)mod k=0. 此時可選取ui=0以同時滿足ui-1ui=uiu(i+1)mod k=0. 而根據(jù)方程組(1)的多項式時間求解算法可知ui在第i-1次時已被設(shè)置為0，因此只需考慮c(i+1)mod k=0的情形，此時選擇u(i+1)mod k=0即可滿足. 從而按照方程組(1)的多項式時間求解算法可以得到方程組(1)的一個解(當環(huán)排列(c0,c1,c2,…,ck-1)中含有3個或3個以上連續(xù)的0時，方程組(1)有多個解，通過排列組合的方式可得到全部解,此處選擇其中的一個解). 關(guān)于算法的時間復雜度，由于算法總共進行了k次比較，因此時間復雜度是O(k)，為多項式時間復雜度.

其次，從3.2節(jié)可以看出，只要б存在，那么通過篡改a并利用認證結(jié)果就可以恢復標簽密鑰x. 下面將分析б存在的概率和恢復x的概率. 這里先分析б存在的概率,具體如引理2所示：

證明 由引理1易知，f(a)=(c0,c1,c2,…,ck-1)所組成的環(huán)排列中不含有子串“101”，其中ci=aiai+1. 由引理1知，只要f(a)+(0,…,0,1,0,…,0)不含有子串“101”，那么必然存在б滿足f(aб)=f(a)+(0,…,0,1,0,…,0)，而f(a)+(0,…,0,1,0,…,0)中子串“101”只可能存在于以第i個位置為中心的5個連續(xù)的位置，因此需要考慮(ci-2,ci-1,ci,ci+1,ci+2)+(0,0,1,0,0)中出現(xiàn)子串“101”的情況, 其中ci-2、ci-1、ci、ci+1、ci+2由ai-2、ai-1、ai、ai+1、ai+2、ai+3決定. 經(jīng)計算發(fā)現(xiàn)，當ai-2、ai-1、ai、ai+1、ai+2、ai+3屬于(***011)、(*1111*)和(110***)這3種形式的向量時，(ci-2,ci-1,ci,ci+1,ci+2)+(0,0,1,0,0)中一定會出現(xiàn)子串“101”. 于是，共有23+22+23-1=19種情況使得引理2的方程無解，則方程f(aб)-f(a)=(0,…,0,1,0,…,0)有解的概率為(26-19)/26=45/64.

接下來將給出攻擊者在一次攻擊中恢復密鑰x的一個比特xi的概率.

證明 根據(jù)xi取值分2種情況：(1)當xi=0時，z=f(a)·xb·yxiv=f(a)·xb·yv，即攻擊者對a的篡改不改變標簽的認證碼z，從而不改變閱讀器對標簽的認證結(jié)果，于是標簽可以通過閱讀器認證. 根據(jù)3.2節(jié)的攻擊算法，攻擊者以概率1的優(yōu)勢恢復出xi=0. (2)當xi=1時，z=f(a)·xb·yxiv，在這種情況下將證明閱讀器以壓倒性的概率拒絕標簽：由引理2得知，攻擊者對a篡改成功的概率為45/64，則z=f(a)·xb·yv，其中是一個參數(shù)為45/64的貝努利隨機變量. 易知，v仍服從貝努利分布，設(shè)其參數(shù)為α，則從而得到一個參數(shù)α>1/2的HB#認證協(xié)議. 進一步由Chernoff定理[3]可得:HB#中間人攻擊中標簽響應錯誤的次數(shù)大于ω的概率至少為1-e-θ2αr/3，其中0<θ<(α-η)/α.

以下定理將給出3.2節(jié)的中間人攻擊算法中攻擊者恢復密鑰x的概率.

4 結(jié)束語

LPN不但可以為RFID系統(tǒng)提供低成本的認證協(xié)議，而且還可以抵抗量子攻擊. 自從首個基于LPN的HB協(xié)議在2001年提出來以后，相繼出現(xiàn)了眾多的HB類型協(xié)議. 這些協(xié)議絕大部分不能抵抗中間人攻擊，一小部分只能抗主動攻擊，大部分可以抵抗被動攻擊. HB類型協(xié)議的發(fā)展還是遵循著協(xié)議設(shè)計、協(xié)議分析、協(xié)議改進這樣一條循環(huán)前進的道路，少有HB類型協(xié)議具有可證明的安全性. 而LPN假設(shè)自身的簡單性與線性特點給認證協(xié)議的設(shè)計帶來極大的困難，因此基于LPN設(shè)計出實用的、可證明安全的認證協(xié)議仍是HB類型協(xié)議發(fā)展的主要方向. 該文在研究一類多元二次方程組的解的基礎(chǔ)上，對HB#協(xié)議進行了中間人攻擊，攻擊算法的復雜度低且成功概率高. 這里提出的多元二次方程組的解不但可以用在HB類型協(xié)議的代數(shù)攻擊上，而且有望用于其他協(xié)議的分析，為進一步設(shè)計安全的HB類型協(xié)議提供了指導.

[1] BLUM A,KALAI A,WASSERMAN H. Noise-tolerant learning,the parity problem,and the statistical query model[J]. Jounal of ACM,2003,50(4):506-519.

[2] GILBERT H,ROBSHAW M J B,SEURIN Y. How to encrypt with the LPN problem[C]∥ACETO L,DAMG?RD L A,GOLDBERG L A,et al. Automata,Languages and Pro-gramming. Berlin:Springer,2008:679-690.[3] KILTZ E,MASN D,PIERTRZAK K. Simple chosen-ciphertext security from low-noise LPN[C]∥KRAWCZYK H. Public-Key Cryptography-PKC 2014. Berlin:Springer,2014:1-18.

[4] GUO Q,JOHANSSON T,LONDAHL C. Solving LPN using covering codes[C]∥SARKAR P,IWATA T. Advances in Cryptology-ASIACRYPT 2014. Berlin:Springer,2014:1-20.

[5] HOPPER N J,BLUM M. Secure human identification protocol[C]∥BOYD C. Advances in Cryptology-ASIACRYPT. Berlin:Springer,2001:52-66.

[6] JUELS A,WEIS S. Authenticating pervasive devices with human protocols[C]∥SHOUP V. Advances in Cryptology-CRYPTO 2005. Berlin:Springer,2005:293-308.

[7] GILBERT H,ROBSHAW M,SEURIN Y. HB#:increasing the security and efficiency of HB+[C]∥SMART N. Advances in Cryptology-EUROCRYPT 2008. Berlin:Springer,2008:361-378.

[8] KILTZ E,PIETRZAK K,CASH D,et al. Efficient authentication from hard learning problems[C]∥PATERSONK G. Advances in Cryptology- EUROCRYPT 2011. Berlin:Springer,2011:7-26.

[9] 周世杰,張文清,羅嘉慶. 射頻識別(RFID)隱私保護技術(shù)綜述[J]. 軟件學報,2015,26(4):960-976.

ZHOU S J,ZHANG W Q,LUO J Q. Survey of privacy of radio frequency identification technology[J]. Journal of Software,2015,26(4):960-976.

[10] 馬昌社. 前向隱私安全的低成本RFID認證協(xié)議[J]. 計算機學報,2011,34(8):1387-1398.

MA C S. Low cost RFID authentication protocol with forward privacy[J]. Chinese Journal of Computer，2011,34(8):1387-1398.

[11]LI Y J,DENG R H,LAI J Z,et al. On two RFID privacy notions and their relations[J]. ACM Transaction on Information and System Security,2011,14(4):68-85.

[12]MA C S,WENG J. Radio frequency identification system security proceedings of rfidsec asia workshop[M]. Netherlands:IOS Press,2013.

[13]AVOINE G,COISEL I,MARTIN T. Untraceability model for RFID[J]. IEEE Transactions on Mobile Computing,2014,13(10):2397-2405.

[14]GILBERT H,ROBSHAW M,SILBERT H. Active attack against HB+:a provably secure lightweight authentication protocol[J]. Electronics Letters,2005,41(21):1170.

[15]OUAFI K,OVERBACK R,VAUDENAY S. On the security of HB#against a man-in-the-middle attack[C]∥PIEPRZYK J. Advances in Cryptology-ASIACRYPT 2008. Berlin:Springer,2008:108-124.

[16]KOSEI E,NOBORU K. Security analysis on AUTH protocol and its variant against the man-in-the-middle attack[J]. IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,2015,98(1):153-161.

[17]LYUBASHEVSKY V,MANSY D. Man-in-the-middle secure authentication schemes from LPN and weak PRFs[C]∥CANETTI R,GARAY J A. Advances in Cryptology-CRYPTO 2013. Berlin:Springer,2013:308-325.

[18] 唐靜,姬東耀. 基于LPN問題的RFID安全協(xié)議設(shè)計與分析[J]. 電子與信息學報,2009,31(2):439-443.

TANG J,JI D Y. Design and analysis of security protocol for RFID based on LPN problem[J]. Journal of Electronics& Information Technology,2009,31(2):439-443.

[19]COURTOIS N T,MEIER W. Algebraic attacks on stream ciphers with linear feedback[C]∥BIHAM E. Advances in Cryptology-EUROCRYPT 2003. Berlin:Springer,2003:345-359 .

[20]COURTOIS N,KILMOV A,PATARIN J,et al. Efficient algorithms for solving overdefined systems of multivariate polynomial equations[C]∥PRENEEL B. Advances in Cryptology-EUROCRYPT 2000. Berlin:Springer,2000:392-407.

[21]BLUM A,FURST M,KEARNS M,et al. Cryptographic primitives based on hard learning problems[C]∥STINSON D R. Advances in Cryptology-CRYPTO’ 93. Berlin:Springer,1993:278-291.

[22]BRUALDI R A,FENG S. Introductory combinatorics[M]. Beijing:China Machine Press,2012:53-56.

【中文責編：莊曉瓊 英文審校:肖菁】

Algebraic Analysis on HB#Authentication Protocol

JIANG Xiao, MA Changshe*

(School of Computer Science, South China Normal University, Guangzhou 510631,China)

HB-like protocols are such a kind of authentication protocols that require low computational resource and promise to resist quantum attacks. They are especially suitable for mobile applications and the Internet of Things (IoT). However, the wireless communications in these environments have compelled that HB-like protocols should be able to resist the man-in-the-middle (MIM) attacks. In this vein, this paper proposes an algebraic MIM attack to a recently presented HB#authentication protocol which is claimed to resist MIM attacks. During this attack, the authentication keys can be totally recovered efficiently. The proposed attacking method is based on the solutions to a system of quadratic equations of multi-variables overZ2. Hence, the necessary and sufficient conditions for this system of equations being solvable have been found in advance. Then, an algebraic attack to HB#protocol has been presented accordingly.

HB protocol; algebraic attacks; man-in-the-middle attack

2015-08-04 《華南師范大學學報(自然科學版)》網(wǎng)址：http://journal.scnu.edu.cn/n

國家自然科學基金項目(61672243);廣東省自然科學基金項目(S2013020011913);廣東省教育廳科技創(chuàng)新項目(2013KJCX0055);廣州市基礎(chǔ)研究項目(11C42090777)

TP309

A

1000-5463(2017)01-0110-06

*通訊作者:馬昌社，教授,Email:chsma@163.com.