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

姜 曉， 馬昌社

(華南師范大學(xué)計(jì)算機(jī)學(xué)院, 廣州 510631)

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

姜 曉， 馬昌社*

(華南師范大學(xué)計(jì)算機(jī)學(xué)院, 廣州 510631)

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

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

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

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

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

圖1 HB認(rèn)證協(xié)議

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

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

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

1 預(yù)備知識(shí)

1.1 符號(hào)說(shuō)明

1.2 LPN問(wèn)題

1.3 環(huán)排列

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

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

2 HB# 協(xié)議

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

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

圖3 GRS攻擊

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)無(wú)需恢復(fù)密鑰y：鑒于HB#協(xié)議中b由標(biāo)簽給定，因此攻擊者可以每次設(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. 這樣進(jìn)行r次后，如果閱讀器收到錯(cuò)誤響應(yīng)的次數(shù)小于ω，則攻擊者冒充標(biāo)簽成功. 攻擊者冒充標(biāo)簽的攻擊過(guò)程如圖6所示.

圖6 標(biāo)簽冒充攻擊

(2)選取k個(gè)線性無(wú)關(guān)的向量b，根據(jù)認(rèn)證結(jié)果構(gòu)成線性方程組，用高斯消元法解矩陣方程恢復(fù)密鑰y：HB#協(xié)議中密鑰y表示為y=(y0,y1,y2,…,yk-1)，攻擊者首先選取b=(b0,b1,b2,…,bk-1)=(1,0,0,…,0)，則攻擊者計(jì)算z=f(a)·x(1,0,0,…,0)·(y0,y1,y2,…,yk-1)v=f(a)·xy0v，保持b不變，攻擊者與閱讀器進(jìn)行r次交互，并將r次認(rèn)證后閱讀器對(duì)攻擊者的認(rèn)證結(jié)果記為d0(若認(rèn)證通過(guò)d0=0，否則d0=1). 同樣的方法，攻擊者選取b=(0,1,0,…,0)，則計(jì)算z=f(a)·x(0,1,0,…,0)·(y0,y1,y2,…,yk-1)v=f(a)·xy1v，重復(fù)進(jìn)行r次，并將閱讀器對(duì)攻擊者的認(rèn)證結(jié)果記為d1. 最后選取b=(0,0,0,…,1)，并將閱讀器對(duì)攻擊者的認(rèn)證結(jié)果記為dk-1. 易知，密鑰y=(d0,d1,d2,…,dk-1)，即攻擊者成功恢復(fù)密鑰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的多元二次方程組是一個(gè)NP困難問(wèn)題[16-17]，但對(duì)于某些特殊方程組可以快速求解. 關(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)無(wú)解.

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

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

if(ci==1) then

ui=ui+1=1;

elseui+1=0.

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

其次，從3.2節(jié)可以看出，只要б存在，那么通過(guò)篡改a并利用認(rèn)證結(jié)果就可以恢復(fù)標(biāo)簽密鑰x. 下面將分析б存在的概率和恢復(fù)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個(gè)位置為中心的5個(gè)連續(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)計(jì)算發(fā)現(xiàn)，當(dāng)ai-2、ai-1、ai、ai+1、ai+2、ai+3屬于(***011)、(*1111*)和(110***)這3種形式的向量時(shí)，(ci-2,ci-1,ci,ci+1,ci+2)+(0,0,1,0,0)中一定會(huì)出現(xiàn)子串“101”. 于是，共有23+22+23-1=19種情況使得引理2的方程無(wú)解，則方程f(aб)-f(a)=(0,…,0,1,0,…,0)有解的概率為(26-19)/26=45/64.

接下來(lái)將給出攻擊者在一次攻擊中恢復(fù)密鑰x的一個(gè)比特xi的概率.

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

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

4 結(jié)束語(yǔ)

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

[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] 周世杰,張文清,羅嘉慶. 射頻識(shí)別(RFID)隱私保護(hù)技術(shù)綜述[J]. 軟件學(xué)報(bào),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認(rèn)證協(xié)議[J]. 計(jì)算機(jī)學(xué)報(bào),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問(wèn)題的RFID安全協(xié)議設(shè)計(jì)與分析[J]. 電子與信息學(xué)報(bào),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.

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

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 《華南師范大學(xué)學(xué)報(bào)(自然科學(xué)版)》網(wǎng)址：http://journal.scnu.edu.cn/n

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

TP309

A

1000-5463(2017)01-0110-06

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