陳大江，秦 臻，秦志光

(1. 電子科技大學(xué)信息與軟件工程學(xué)院 成都 611731；2. 電子科技大學(xué)網(wǎng)絡(luò)與數(shù)據(jù)安全四川省重點(diǎn)實(shí)驗(yàn)室 成都 611731)

竊聽信道下的認(rèn)證信道容量

陳大江1,2，秦 臻1,2，秦志光1,2

(1. 電子科技大學(xué)信息與軟件工程學(xué)院 成都 611731；2. 電子科技大學(xué)網(wǎng)絡(luò)與數(shù)據(jù)安全四川省重點(diǎn)實(shí)驗(yàn)室 成都 611731)

消息認(rèn)證是合法發(fā)送方Alice傳輸消息M給合法的接收方Bob并向Bob認(rèn)證M的交互過程。為了防止敵手Eve的攻擊，Alice和Bob通常共享了一個(gè)安全密鑰。該文考察如下認(rèn)證框架：Alice首先通過無噪聲信道將消息M發(fā)送給Bob；Alice接著利用消息M和安全密鑰K生成一個(gè)認(rèn)證標(biāo)簽；Alice再將認(rèn)證標(biāo)簽轉(zhuǎn)化為碼字Xn；最后，Alice通過竊聽信道模型將碼字Xn傳輸給Bob。該文定義了固定標(biāo)簽率下的安全認(rèn)證信道容量，并證明該認(rèn)證信道容量等于H(X|Z)。特別地，證明了文獻(xiàn)[15]提出的協(xié)議在該文的認(rèn)證模型中是可達(dá)容量的。

消息認(rèn)證; 認(rèn)證信道容量; 信息論安全; 竊聽信道

消息認(rèn)證是密碼學(xué)和信息安全領(lǐng)域中一個(gè)最基礎(chǔ)也是最重要的研究問題之一。其目的是，發(fā)送方Alice將消息M發(fā)送給接收方Bob，并通過交互(或者非交互)的方式使得Bob能夠確認(rèn)消息M是來自Alice的。要達(dá)到這個(gè)目的，Alice和Bob首先要共享一個(gè)密鑰K。為了確保協(xié)議的安全性，首先要考慮敵手模型，即敵手具有什么樣的計(jì)算能力，能夠發(fā)起什么形式的攻擊。通常采用的敵手模型是敵手可以發(fā)起中間人攻擊。即敵手可以冒充Alice(Bob)發(fā)送任何消息給Bob(Alice)。除此之外，敵手還可以插入、篡改和刪除Alice和Bob之間的消息。

在經(jīng)典消息認(rèn)證模型中，Alice和Bob之間的通信信道是無噪聲的[1-2]。然而，在無噪聲的認(rèn)證模型中，由于每一次認(rèn)證都會(huì)降低密鑰的熵，故而提高了敵手攻擊成功的概率。文獻(xiàn)[2]證明了使用相同密鑰認(rèn)證l個(gè)消息后，敵手攻擊成功概率的下界是2?H(K)(l+1)。這說明當(dāng)l增大時(shí)，攻擊成功的概率將會(huì)很快增加到1。噪聲是通信中常見的物理現(xiàn)象。在安全領(lǐng)域，噪聲卻帶來了諸多好處。文獻(xiàn)[3]在竊聽信道模型下利用噪聲實(shí)現(xiàn)了合法用戶間的密鑰共享，同時(shí)使竊聽者得不到任何關(guān)于密鑰的信息。文獻(xiàn)[4]將這一結(jié)果推廣到了廣播信道模型。從此，噪聲信道下的密鑰分配問題得到了理論和工業(yè)界的廣泛研究[5-9]，但在噪聲信道下的消息認(rèn)證的相關(guān)工作卻鮮有進(jìn)展。如何實(shí)現(xiàn)信息安全下的多項(xiàng)式次的消息認(rèn)證是一個(gè)值得關(guān)注的問題。

1 相關(guān)工作

本文將考察在噪聲信道下的消息認(rèn)證。文獻(xiàn)[10]提到了利用噪聲信道獲得的相關(guān)性實(shí)現(xiàn)(無噪聲)公共信道的消息認(rèn)證。該問題可歸類為信源模型[11]的消息認(rèn)證。文獻(xiàn)[12]首次提出了竊聽信道的消息認(rèn)證：Alice和Bob共享一個(gè)密鑰，當(dāng)Alice發(fā)送X時(shí)，合法接收者Bob通過主信道W1:X→Y收到Y(jié)，竊聽者通過竊聽信道W2:X→Z收到Z。當(dāng)不等式I(X;Y)>I(X;Z)成立時(shí)，文獻(xiàn)[12]構(gòu)造出一個(gè)能夠多次進(jìn)行消息認(rèn)證的認(rèn)證協(xié)議，并且認(rèn)證次數(shù)的增加對(duì)敵手攻擊成功的概率的影響是可以忽略的。而文獻(xiàn)[2]的結(jié)論說明上述結(jié)果在無噪聲信道下是不可能的。相關(guān)的研究工作還包括文獻(xiàn)[13]提出的在MIMO衰落信道下的認(rèn)證問題，該協(xié)議假設(shè)Alice和Bob之間沒有共享密鑰，并且假設(shè)攻擊者只發(fā)起冒充攻擊。該協(xié)議在文獻(xiàn)[14]中得到了進(jìn)一步的研究。

本文考察如下認(rèn)證框架：Alice首先通過無噪聲信道將消息M發(fā)送給Bob，接著利用安全密鑰生成一個(gè)認(rèn)證標(biāo)簽，再將認(rèn)證標(biāo)簽轉(zhuǎn)化為碼字Xn，最后通過竊聽信道模型將碼字傳輸給Bob。本文定義了固定標(biāo)簽率下的安全認(rèn)證信道容量，并證明該認(rèn)證信道容量等于H(X|Z)。這也進(jìn)一步證明了文獻(xiàn)[15]提出的協(xié)議在本文的認(rèn)證模型中是可達(dá)容量的。

2 竊聽信道模型與系統(tǒng)模型

2.1 竊聽信道模型

一條輸入字母表為X，輸出字母表為Y的信道稱為離散無記憶信道(discrete memoryless channel, DMC)當(dāng)且僅當(dāng)這個(gè)信道可以有隨機(jī)矩陣W={W(y|x)}x∈X,y∈Y表示。其中，W(i|x)是指當(dāng)輸入為x時(shí)，在信道輸出端的輸出分布情況，即當(dāng)輸入為序列輸出為時(shí)，有：

定義 1 把輸入相同的兩個(gè)離散無記憶信道W1:X→Y，W2:X→Y稱為竊聽信道模型。其中，W1為主信道；W2為竊聽信道。

2.2 系統(tǒng)模型

如圖1所示，考慮兩個(gè)離散無記憶信道W1:X→Y，W2:X→Z。Alice和Bob共享一個(gè)對(duì)稱密鑰K，其中K是從一個(gè)有限集Κ中均勻的隨機(jī)產(chǎn)生。他們由信道W1相連，當(dāng)Alice傳輸X∈X時(shí)，Bob以概率PY|X=W1(Y|X )接收到Y(jié)∈Y(其中，對(duì)任意隨機(jī)變量R，R定義為R的事件域)。同時(shí)，X將在竊聽信道W2上傳輸。竊聽者Oscar收到的信道輸出變量為Z∈Z，其概率分布滿足PZ|X=W2(Z|X )。Alice的目標(biāo)是傳輸消息M的同時(shí)并對(duì)消息進(jìn)行認(rèn)證。為此，定義認(rèn)證模型為：記M為消息域，Alice將傳輸并認(rèn)證消息M∈M。

圖1 系統(tǒng)模型

1) Alice通過無噪聲信道發(fā)送消息M給Bob；

3) Bob從無噪聲信道接收到消息M′，同時(shí)從信道W1接收到失真的認(rèn)證碼Yn。Bob計(jì)算T′=hK(M′)，并通過帶密鑰的函數(shù)gK:T×Yn→{0,1}認(rèn)證(T′,Yn)。如果函數(shù)gK的輸出是1，則接受消息M′；否則，拒絕。

把滿足上述模型的協(xié)議稱為一個(gè)認(rèn)證協(xié)議(記為Π)，如果生成的認(rèn)證碼為Xn，即認(rèn)證碼的長(zhǎng)度為n，用Πn表示Π。

3 敵手模型

協(xié)議Π的目的是認(rèn)證消息M。一個(gè)認(rèn)證失敗包含有兩種可能性：完備性錯(cuò)誤或者敵手攻擊，其中，完備性錯(cuò)誤是指沒有敵手存在時(shí)發(fā)生了錯(cuò)誤。在本文的模型中，從Alice到Oscar有一條DMC信道相連。Oscar可以插入和修改在無噪聲信道的傳輸消息。假設(shè)從Oscar到Bob的信道是無噪聲的，且敵手具有無限的計(jì)算能力。本文希望在敵手Oscar多次通過竊聽信道2W得到認(rèn)證的觀察值并且多次動(dòng)態(tài)地修改無噪聲信道的消息的前提下，Oscar還是不能偽造一個(gè)可通過認(rèn)證的消息。這里“多次”的上界是認(rèn)證碼長(zhǎng)度的任意多項(xiàng)式。形式化地，Oscar可發(fā)起兩類攻擊。

1) 假設(shè)Alice已經(jīng)認(rèn)證了消息M1,M2,,Mi?1。為了認(rèn)證消息Mi，Alice在無噪聲信道上發(fā)送消息Mi，并且在信道(W1,W2)上發(fā)送認(rèn)證碼。Oscar可以觀察到Mi并可以將其篡改為。還可以觀察到信道W2的輸出。Bob可以接收到無噪聲信道的消息和信道W1的輸出Oscar獲得Bob的判定比特這里當(dāng)bi=1并且時(shí)，攻擊成功。其中，的選取是基于Oscar的隨機(jī)源R，消息和前i?1階段收集到的信息以及在第一型攻擊下的判定比特和在第二型攻擊下的判定比特

2) Osca可以自適應(yīng)地通過無噪聲信道發(fā)送給Bob任何消息Oscar將會(huì)學(xué)習(xí)到Bob的判定比特其中，如果則攻擊成功。這里的計(jì)算是基于Oscar的隨機(jī)源R和前i?1階段收集到的信息

4 安全認(rèn)證協(xié)議與安全認(rèn)證容量

4.1 安全認(rèn)證協(xié)議

在引入敵手模型后，開始形式化定義認(rèn)證。認(rèn)證的性質(zhì)由完備性和認(rèn)證性組成。完備性指敵手不存在時(shí)，Bob應(yīng)當(dāng)以很高的概率接受消息M為合法的消息；認(rèn)證性指在敵手存在的前提下，認(rèn)證失敗的可能性應(yīng)該很小，其中，認(rèn)證失敗是指接受了敵手篡改過的消息。

定義 3 給定一個(gè)竊聽信道模型W1:X→Y，W2:X→Y，稱協(xié)議Π是認(rèn)證安全的當(dāng)且僅當(dāng)Π滿足下列條件：1) 完備性：如果敵手不存在，那么Bob將以指數(shù)(對(duì)于n)小的概率拒絕合法的消息M；2) 強(qiáng)安全性：記VIEW(Oscar)為竊聽者Oscar的觀察值，那么，互信息I(T;VIEW(Oscar))是可忽略的(對(duì)于n)；3) 認(rèn)證性：如果第二型攻擊的次數(shù)不超過多項(xiàng)式(對(duì)于n)，那么敵手攻擊成功的概率Pr(succ)是可忽略的(對(duì)于n)。

完備性說明合法消息有很高的概率通過認(rèn)證；強(qiáng)安全性說明認(rèn)證過程中的認(rèn)證標(biāo)簽不會(huì)向敵手泄露；認(rèn)證性說明敵手不能偽造一個(gè)消息并通過認(rèn)證。

限制第二型攻擊次數(shù)是不可避免的，這是因?yàn)閿呈諳scar可以持續(xù)地選擇同一個(gè)消息M并選擇所有可能的Yn，并通過無噪聲信道發(fā)送給Bob。由于Yn是有限集，Oscar總能夠選中某些Yn使得攻擊成功。限定第二型攻擊的次數(shù)不超過多項(xiàng)式的原因是，每一次攻擊都涉及接收方Bob，而要求Bob的復(fù)雜度超過多項(xiàng)式是不實(shí)際的。另外，由于第一型攻擊的次數(shù)等于Alice發(fā)送消息的次數(shù)，故第一型攻擊自然的被限定在多項(xiàng)式內(nèi)。

4.2 安全認(rèn)證容量

考慮到在竊聽信道上通信是比較昂貴的資源，因此，希望盡可能少地利用這一昂貴的資源。針對(duì)有效性分析，定義了兩類有效性測(cè)度。

第一類測(cè)度稱為標(biāo)簽率，其定義是：

即消息源長(zhǎng)度與標(biāo)簽長(zhǎng)度的比值。

第二類測(cè)度稱為標(biāo)簽的信道編碼率，定義為：

即標(biāo)簽長(zhǎng)度和編碼長(zhǎng)度的比值。

在竊聽信道下安全認(rèn)證信道容量的定義如下：

定義 4 給定一個(gè)竊聽信道模型W1:X→Y，W1:X→Y。對(duì)于任何以auth的標(biāo)簽率認(rèn)證安全的協(xié)議Π，可達(dá)的最大信道率chan稱為以標(biāo)簽率為auth的安全認(rèn)證信道容量，簡(jiǎn)記為Cchan(auth)。

5 主要結(jié)果

5.1 一個(gè)重要的定理

先引用一個(gè)重要的定理，該定理是構(gòu)造一個(gè)可達(dá)安全認(rèn)證容量的認(rèn)證協(xié)議的基礎(chǔ)。

定理 1[15]記X,Y,Z分別為X,Y,Z上的隨機(jī)變量，且PY|X=W1，PZ|X=W2為兩個(gè)DMC。有一個(gè)類P使得X的概率分布PX=P，且對(duì)于任意x∈X，有P(x)>0。若存在τ>0，使得I(X;Y)> I(X;Z)+τ，那么，對(duì)于任意正整數(shù)I、J滿足條件：

2) 記J為[J]上的隨機(jī)變量，I為[I]上的隨機(jī)

3) 對(duì)于[J]上的任意隨機(jī)變量J，[I]上的任意隨機(jī)變量I，記為輸入時(shí)信道W2的輸出。假設(shè)[J]上的任意隨機(jī)變量J′使得J′≠J，且滿足下列條件：

①SD(PJ′J;PJ′J|I)≤δ1；

③ 對(duì)任意j′,j，有：

且函數(shù)d(i,i)滿足不等式：

那么，對(duì)于足夠大的n，有：

式中，ω是開區(qū)間(0,1)上的常數(shù)。

5.2 可達(dá)性構(gòu)造

文獻(xiàn)[15]所構(gòu)造的安全認(rèn)證協(xié)議描述如下。

記W1:X→Y，W2:X→Y為竊聽信道模型。假設(shè)I(X;Y)>I(X;Z)+τ，其中τ為大于0的常數(shù)。X的概率分布PX為類P，并且對(duì)任意的x∈X有 P(x) > 0 。記上的子集簇Cij(i=1,2,,I ; j=1,2,,J)是通過定理1得到的。令K1={1,2,,I }，h:M×K0→T是一個(gè)ε-ASU哈希函數(shù)[15]，其中，集合K0是密鑰空間，T?{1,2,,J}。Alice和Bob預(yù)先共享了對(duì)稱密鑰(K0,K1)∈K0×K1。如果Alice要傳輸消息M∈M給Bob，那么，執(zhí)行下列步驟：

1) Alice計(jì)算T=hK0(M)，并且從CK1T中隨機(jī)地選出一個(gè)碼字Xn。Alice再將消息M通過無噪聲(無認(rèn)證的)信道傳給Bob。消息M經(jīng)過Oscar后，Bob收到M′。最后，Alice通過信道(W1,W2)傳輸Xn。Oscar通過W2收到Zn，Bob通過W1收到Y(jié)n。

2) 獲得M′和Yn后，Bob計(jì)算T′=hK0(M′)。如果g(Yn)∈CK1T′，Bob接受M′；否則，拒絕。

在定理1中，fj將消息l編碼成碼本Cij中的第l個(gè)碼字，gj(Yn)將Yn解碼成⊥或者Cij中碼字的編號(hào)。由于編號(hào)和碼字是一一對(duì)應(yīng)的，因此，在本文的構(gòu)造中，gj(Yn)被定義為將Yn解碼⊥或者Cij中碼字。

定理 2 對(duì)于上述認(rèn)證協(xié)議，存在一個(gè)恰當(dāng)?shù)膮?shù)輸入，使得對(duì)任意的auth，以及任意的δ∈(0,H(X|Z ))，有chan=H(X|Z)?δ。

證明：該定理證明類似于文獻(xiàn)[15]的定理3，這里將其略去。

5.3 理論上界

定理 3 給定竊聽信道模型W1:X→Y，W2:X→Y。對(duì)于任何以auth的標(biāo)簽率認(rèn)證安全的協(xié)議Π，有chan≤H(X|Z)。

證明：由強(qiáng)安全性可知:式中，第1個(gè)不等式成立的原因是Zn∈VIEW(Oscar)；第2個(gè)不等式成立是因?yàn)門可以由Xn完全確定；第3個(gè)不等式成立是因?yàn)閄n和Zn是獨(dú)立同分布且竊聽信道是離散無記憶的。

故有：證畢。

定理 4 給定竊聽信道模型W1:X→Y，W2:X→Y。對(duì)于任意auth，認(rèn)證信道容量為Cchan(auth)=H(X|Z)。

證明：由定理2和定理3可以得出結(jié)論。

6 結(jié) 論

Alice在一個(gè)無噪聲信道的輔助下，利用竊聽信道W1:X→Y，W2:X→Y來認(rèn)證消息M，其中，Alice和Bob事先共享一個(gè)對(duì)稱密鑰。在這個(gè)認(rèn)證框架下，Alice利用無噪聲信道來傳輸要認(rèn)證的消息M，然后在竊聽信道上傳輸認(rèn)證標(biāo)簽T所對(duì)應(yīng)的碼字。證明了本文考慮的認(rèn)證模型下的安全認(rèn)證容量為H(X|Z)。文獻(xiàn)[15]提出了一個(gè)高效的消息認(rèn)證協(xié)議，本文的結(jié)果說明了該協(xié)議是可以達(dá)到認(rèn)證容量的。將來的工作會(huì)探究怎樣構(gòu)造出一個(gè)計(jì)算有效的協(xié)議？

[1] SIMMONS G J. Authentication theory/coding theory[C]// Proc of CRYPTO'84. Berlin, Heidelberg: Springer, 1985: 411-431.

[2] MAURER U M. Authentication theory and hypothesis testing[J]. IEEE Trans Inf Theory, 2000, 46(4): 1350-1356.

[3] WYNER A D. The wire-tap channel[J]. Bell Syst Tech J, 1975, 54: 1355-1387.

[4] CSISZAR I, KORNER J. Broadcast channels with confidential messages[J]. IEEE Trans Inf Theory, 1978, 24(3): 339-348.

[5] MAURER U M, WOLF S. Secret-key agreement over unauthenticated public channels, part I: Definitions and a completeness result[J]. IEEE Trans Inf Theory, 2003, 49(4): 822-831.

[6] MAURER U M, WOLF S. Secret-key agreement over unauthenticated public channels, part II: the simulatability condition[J]. IEEE Trans Inf Theory, 2003, 49(4): 832-838.

[7] MAURER U M, WOLF S. Secret-key agreement over unauthenticated public channels, part III: Privacy amplification[J]. IEEE Trans Inf Theory, 2003, 49(4): 839-851.

[8] CHEN D J, QIN Z, MAO X F, et al. Smokegrenade: an efficient key generation protocol with artificial interference [J]. IEEE Transactions on Information Forensics & Security, 2013, 8(11): 1731-1745.

[9] CHEN D J, MAO X F, QIN Z, et al. Smokegrenade: a key generation protocol with artificial interference in wireless networks[C]//Proceedings of IEEE MASS. Hangzhou: IEEE, 2013: 200-208.

[10] KORZHIK V, YAKOVLEV V, MORALES L G, et al. Performance evaluation of keyless authentication based on noisy channel[C]//MMM-ACNS 2007. Berlin, Heidelberg: Springer-Verlag, 2007: 115-126.

[11] AHLSWEDE R, CSISZAR I. Common randomness in information theory and cryptography, part II: CR capacity [J]. IEEE Trans Inf Theory, 1998, 44(1): 225-240.

[12] LAI L F, ELGAMAL H, POOR H V. Authentication over noisy channels[J]. IEEE Trans Inf Theory, 2009, 55(2): 906-916.

[13] BARACCA P, LAURENTI N, TOMASIN S. Physical layer authentication over MIMO fading wiretap channels[J]. IEEE Transactions on Wireless Communications, 2012, 11(7): 2564-2573.

[14] FERRANTE A, LAURENTI N, MASIERO C, et al. On the achievable error region of physical layer authentication techniques over Rayleigh fading channels[EB/OL]. (2013-03-04). http://arxiv.org/abs/1303.0707.

[15] CHEN D J, JIANG S Q, QIN Z G. Message authentication code over a wiretap channel[EB/OL]. (2013-10-15). http://arxiv.org/abs/1310.3902.

編輯蔣 曉

Authentication Capacity Over Wiretap Channel

CHEN Da-jiang1,2, QIN Zhen1,2, and QIN Zhi-guang1,2
(1. School of Information and Software Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. Network and Data Security Key Laboratory of Sichuan Provence, University of Electronic Science and Technology of China Chengdu 611731)

Message authentication is an interactive procedure that allows a legitimate sender Alice to send and authenticate a message M to a legitimate receiver Bob. To prevent the attacks from an adversary Eve, Alice and Bob usually share a secret key K. In this paper, we study a novel authentication framework as follows. Firstly, Alice sends a message M to Bob over a noiseless channel; Secondly, Alice generates an authentication tag with the message M and secret key K; Thirdly, Alice encodes the tag into a codeword Xn; Finally, Alice transmits the codeword Xnto Bob over a wiretap channel. This paper defines an authentication channel capacity under a fixed tag rate, and show that it equals to H(X|Z). Specifically, we prove that the authentication protocol proposed in Ref. [15] is capacity-achievable under our authentication model.

authentication; authentication channel capacity; information-theory security; wiretap channel

TP309

A doi:10.3969/j.issn.1001-0548.2015.04.017

2014 ? 02 ? 11；

2014 ? 12 ? 15

國(guó)家科技重大專項(xiàng)(20112X03002-002-03)；國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(61190110).

陳大江(1982 ? )，男，博士生，主要從事信息論安全、物理層安全、無線安全等方面的研究.