竊聽信道下的認證信道容量

陳大江，秦 臻，秦志光

(1. 電子科技大學信息與軟件工程學院 成都 611731；2. 電子科技大學網絡與數據安全四川省重點實驗室 成都 611731)

竊聽信道下的認證信道容量

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

(1. 電子科技大學信息與軟件工程學院 成都 611731；2. 電子科技大學網絡與數據安全四川省重點實驗室 成都 611731)

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

消息認證; 認證信道容量; 信息論安全; 竊聽信道

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

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

1 相關工作

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

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

2 竊聽信道模型與系統模型

2.1 竊聽信道模型

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

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

2.2 系統模型

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

圖1 系統模型

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

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

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

3 敵手模型

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

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

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

4 安全認證協議與安全認證容量

4.1 安全認證協議

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

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

完備性說明合法消息有很高的概率通過認證；強安全性說明認證過程中的認證標簽不會向敵手泄露；認證性說明敵手不能偽造一個消息并通過認證。

限制第二型攻擊次數是不可避免的，這是因為敵手Oscar可以持續地選擇同一個消息M并選擇所有可能的Yn，并通過無噪聲信道發送給Bob。由于Yn是有限集，Oscar總能夠選中某些Yn使得攻擊成功。限定第二型攻擊的次數不超過多項式的原因是，每一次攻擊都涉及接收方Bob，而要求Bob的復雜度超過多項式是不實際的。另外，由于第一型攻擊的次數等于Alice發送消息的次數，故第一型攻擊自然的被限定在多項式內。

4.2 安全認證容量

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

第一類測度稱為標簽率，其定義是：

即消息源長度與標簽長度的比值。

第二類測度稱為標簽的信道編碼率，定義為：

即標簽長度和編碼長度的比值。

在竊聽信道下安全認證信道容量的定義如下：

定義 4 給定一個竊聽信道模型W1:X→Y，W1:X→Y。對于任何以auth的標簽率認證安全的協議Π，可達的最大信道率chan稱為以標簽率為auth的安全認證信道容量，簡記為Cchan(auth)。

5 主要結果

5.1 一個重要的定理

先引用一個重要的定理，該定理是構造一個可達安全認證容量的認證協議的基礎。

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

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

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

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

③ 對任意j′,j，有：

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

那么，對于足夠大的n，有：

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

5.2 可達性構造

文獻[15]所構造的安全認證協議描述如下。

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

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

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

在定理1中，fj將消息l編碼成碼本Cij中的第l個碼字，gj(Yn)將Yn解碼成⊥或者Cij中碼字的編號。由于編號和碼字是一一對應的，因此，在本文的構造中，gj(Yn)被定義為將Yn解碼⊥或者Cij中碼字。

定理 2 對于上述認證協議，存在一個恰當的參數輸入，使得對任意的auth，以及任意的δ∈(0,H(X|Z ))，有chan=H(X|Z)?δ。

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

5.3 理論上界

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

證明：由強安全性可知:式中，第1個不等式成立的原因是Zn∈VIEW(Oscar)；第2個不等式成立是因為T可以由Xn完全確定；第3個不等式成立是因為Xn和Zn是獨立同分布且竊聽信道是離散無記憶的。

故有：證畢。

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

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

6 結 論

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

[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

國家科技重大專項(20112X03002-002-03)；國家自然科學基金重點項目(61190110).

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