基于樹鏈認證的一種組播源認證方案

摘 要:簡要介紹了現存的組播源認證方案，指出其優點和缺點。同時，基于樹鏈認證技術提出了一種新的組播源認證方案，該方案中，不同數據塊的摘要之間采用類似于T-CSA的方法串聯起來，擴展了T-CSA的優越性，減少了延遲;而且隨著數據流的不斷增大，數據包的平均認證代價呈下降趨勢，這對于資源有限的成員機器來講非常重要。

關鍵詞:安全組播;源認證;樹鏈認證;T-CSA

中圖分類號:TP393 文獻標志碼:A

文章編號:1001-3695(2010)03-1071-03

doi:10.3969/j.issn.1001-3695.2010.03.074

Source authentication scheme in multicast based on tree chaining

WU Tao1，ZHENG Xue-feng2，ZHANG Wen-jun1，LIU Zhen-hua1，MU Cui-xia1

(1.Dept. of Computer， China Women’s University，Beijing 100101， China;2.School of Information Engineering， University of Science Technology Beijing， Beijing 100083， China)

Abstract:This paper briefly reviewed the existing source authentication schemes and described the advantages and disadvantages of these schemes.Then，proposed a new source authentication scheme based on tree chaining， in which， the abstract came from different block was connected used the technology similar T-CSA， thus expanded the superiority of T-CSA and reduced the average delay on every packet. Moreover， the average authetincation price on each packet will drop along with the unceasingly increases of the data stream， this is very important to the member machines with limited resources.

Key words:secure multicast; source authentication; tree chaining authentication; timed-CSA

隨著網絡技術的進一步發展，組播逐漸成為面向群組服務的一種非常流行的通信方式，比如視頻點播、遠程教學、新聞發布、股票報價、視頻會議、協同工作、網絡游戲等。與單播相比，組播通信中，數據包只需要發送一次，路由器會自動轉發到位于不同網段上的每一位接收者，這樣就降低了網絡通信量，減少了網絡擁塞，節省了網絡帶寬，提高了系統的性能;與廣播相比，組播通信能實現把發送的數據傳送到分散的處于不同子網的主機，組播組內的主機可以位于互聯網的任何地方，突破了廣播通信對同一個子網的限制。組播作為在組內交換信息的有效的數據傳輸方式，得到了越來越廣泛的應用。

然而，組播的安全問題成為制約組播發展的一個重要因素。其中，組播源認證作為整個安全服務的基礎引起了更多的關注。組播源認證方案不僅要保證消息來自正確的發送者，同時還要考慮認證消息產生的速度、長度以及通信開銷和安全性等。設計一個可擴展的、高效的而且能夠有效解決包丟失問題的組播源認證方案是一個極具挑戰性的難題。

1 幾種典型的源認證方案

針對組播源認證問題，學者們提出了很多種方案。總體來講，大致可分為以下四類:

a)最簡單也最直接的方法。將多播流分成一系列的數據包，并采用傳統的簽名算法對每個數據包簽名，如RSA或DSA等。這種方法具有不可否認性、不可偽造性和可仲裁性等特點，滿足認證的安全性要求，因此它已經成為認證系統中的關鍵技術。但其簽名速度較慢，效率較低，生成和校驗簽名需要較大的計算開銷和通信開銷。由于代價過高，在實際應用中受到了很大的限制。

b)不對稱消息認證碼MAC的認證技術。MAC技術是利用一個通信雙方共享的密鑰和加密算法生成一個小的數據塊追加在消息的后面。然而，由于不能采用一個所有成員都共享的密鑰來區分組播組內的發送者，所有成員共享一個密鑰的完全的MAC方法不能實現源認證。為此，R.Cenetti等人提出了基于不對稱消息認證碼MAC的認證技術:發送者S擁有n個密鑰的一個子集K，每個接收者R知道K的一個子集;消息M由S認證時，S根據K中的每個密鑰計算出一個MAC，然后全部追加到消息末尾和消息一起傳送;每個接收者R根據自己所擁有的密鑰子集校驗所有的MACs，認證消息。但這種方法不能提供抗抵賴服務，沒有證據向第三方證明發送者發送過消息。

c)Wong等人[1]提出了基于認證樹的源認證技術。這種方法的主要思想是將多播數據流分成幾個數據塊，為每個數據塊構建一棵認證樹，只需要簽署一小部分信息就能把生成的認證信息分散到同一塊中所有的包內。樹鏈協議要求每一個包攜帶要求認證的信息，這樣就可以單個認證，也就是說，即使n個包中n-1個包丟失了同樣可以認證。該協議的優點是可以容忍包丟失，缺點是每一個包攜帶的認證信息量較大。

d)流簽字認證技術。Gennaro等人[2]提出了流簽字認證技術，該技術組合使用了傳統的簽名算法和一次簽名算法，只需在第一個包上使用傳統的簽名算法，其余的包都采用一次簽名算法。因為一次簽名算法僅需要一個單向函數計算就可以使鏈內的每一個包包含下一個包的密鑰散列值，從而依次驗證每一個包。該方案比基于非對稱密碼體系的傳統簽名算法在簽名和驗證方面都具有更高的效率，但這種方式不允許包丟失，必須要有可靠組播的支持，而且發送者需要提前知道全部的數據流。為了解決包丟失問題，Golle[3]、Perrig[4]等人對流簽字方案[5]提出了多種改進方法，總體思想大都為:將一個數據包的哈希值追加到多個數據包，即冗余哈希鏈接，這樣即使有一些包被丟失，仍有可能通過哈希鏈接路徑把鏈接的丟失包恢復過來。其最大的缺點是接收者為了驗證需要緩存數據包，這樣數據包就不能得到及時驗證，同時附加的信息會導致認證效率下降。

綜上所述，不同的方案各有優劣，有的適用于對認證率要求比較高的應用，有的適用于即時認證，每種方案都是在效率與損耗之間的一個折中。

2 基于樹鏈認證技術的一種新的組播源認證方案

2.1 方案的基本思想

該方案結合了樹鏈認證以及T-CSA技術，基于將數據流分成若干塊的思想，根據網絡實際情況選取塊的長度、塊的構造以及每個包的認證方法參照了樹鏈認證技術，同時為了減輕對每個塊簽名所帶來的巨大計算量以及每個包必須攜帶簽名信息所帶來的極大的通信量，對每個塊的摘要采用了T-CSA技術。也就是說:每個包的認證依賴于所在塊的摘要的認證，而摘要的認證又依賴于CSA技術。為了提高抗丟包的能力，本文提出在對塊摘要使用CSA技術進行發送的過程中，在每兩個塊摘要之后插入一個與其都相關的摘要。這樣，如果一個數據包無法通過自身的塊摘要得到認證，那么只要相關的兩個塊中，至少都有一個數據包被接收到，就可以利用這個插入的信息以及自身攜帶的認證信息，通過多個數據包的合作得到認證。

2.2 方案的具體描述

a)根據網絡丟包的實際情況將數據流分成若干塊[6，7]。例如可選取塊的長度為8(選取的原則是每個塊所含包的個數都為2的冪)，即S=B1‖B2‖B3‖…‖Bm，m=n/c，c=2k(S代表數據流stream;Bi代表第i個數據塊blocki;n為總的包個數;c為每個塊所包含的包個數;k為正整數)。每個數據塊Bi又可表示為Bi= M1(i)‖M2(i)‖M3(i)‖…‖Mc(i)(Mx(i)代表塊Bi的包，1≤x≤c)。D(i)代表塊Bi的消息摘要，其計算方法如圖1所示。其中[6]:

Dji=h(Mji);j=1，…，8

D1，2i= h(D1i‖D2i)，D3，4i=h(D3i‖D4i)，D1，4i= h(D1，2i‖D3，4i)

D5，6i= h(D5i‖D6i)，D7，8i=h(D7i‖D8i)，D5，8i= h(D5，6i‖D7，8i)

Di=h(D1，4i‖D5，8i)(1)

b)如前所述，為了提高抗丟包能力，將相鄰的兩個數據塊構成一個小組，并計算出小組的摘要，如圖2所示。

c)每個塊構建完成之后就可以發送相應的數據包，如圖2所示。計算好D1之后，開始發送P11，P21，P31，……。每個數據包攜帶了用于認證的一些哈希值，如P11包括M11，D21，D3，41，D5，81。同時，每個串的消息摘要采用類似于T-CSA的方法發送。

為了方便理解，可以把數據流看成兩個部分。

第一部分類似于數鏈認證方法。

(a) 計算D1，發送如式(2)的數據包

P11(M11，D21，D3，41，D5，81)

P21(M21，D11，D3，41，D5，81)

P31(M31，D41，D1，21，D5，81)

P41(M41，D31，D1，21，D5，81)

P51(M51，D61，D7，81，D1，41)

P61(M61，D51，D7，81，D1，41)

P71(M71，D81，D5，61，D1，41)

P81(M81，D71，D5，61，D1，41)(2)

P12(M12，D22，D3，42，D5，82)

P22(M22，D12，D3，42，D5，82)

P32(M32，D42，D1，22，D5，82)

P42(M42，D32，D1，22，D5，82)

P52(M52，D62，D7，82，D1，42)

P62(M62，D52，D7，82，D1，42)

P72(M72，D82，D5，62，D1，42)

P82(M82，D72，D5，62，D1，42)(3)

(b)計算D2，發送如式(3)的數據包

……

第二部分基于T-CSA。

(a)產生用于MAC計算的系列密鑰。發送者產生一個隨機數α[8]，反復使用哈希函數H產生一個密鑰鏈:α，H(α)，H2(α)，H3(α)，H4(α)，H5(α)，…，Hn-2(α)，Hn-1(α)，Hn(α)(n為很大的正整數)。為了保證密鑰的安全性(不能從已知的密鑰預知下一個使用的密鑰)，本文反方向使用這個密鑰鏈。

(b)發送者S多播數據SN，ST，αn，delay和sigs(SN，ST，αn，delay)。其中，SN為一個序列號，用來避免重放攻擊;ST為開始傳送數據的時間;αn=Hn(α);delay為密鑰傳輸的延遲時間(同T-CSA，密鑰的延遲分發是為了保證MAC消息不被偽造)。(注:發送端與接收端的時間同步，delay的計算不在本文研究范圍之內)。

(c)消息發送。

D1， MAC(D1，Hn-1(α))at time ST

D2，MAC(D2，Hn-2(α))at time ST+T

D1，2，MAC(D1，2，Hn-3(α))at time ST+2T(4)

D3， MAC(D3，Hn-4(α))at time ST+3T

D4，MAC(D4，Hn-5(α))at time ST+4T

D3，4，MAC(D3，4，Hn-6(α))at time ST+5T(5)



Di，MAC(Di，Hλ(α))λ=n-1-3×((i-1)/2)

Di+1，MAC(Di+1，Hλ(α))λ=n-2-3×((i-1)/2)

Di，i+1，MAC(Di，i+1，Hλ(α))λ=n-3-3×((i-1)/2)(6)

i為奇數

(d)密鑰發送。

αn-1=Hn-1(α)at time ST+delay

αn-2=Hn-2(α)at time ST+delay+T

αn-3=Hn-3(α)at time ST+delay+2T(7)

d)接收方R認證過程如下:

(a)在沒有包丟失的情況下，首先驗證簽名sig(Hn(α)，S)，然后采用類似于T-CSA的方法驗證每個塊的消息摘要，最后驗證每個數據包。比如計算H(Hn-1(α))，如果H(Hn-1(α))=Hn(α)成立，則通過MAC可以驗證消息摘要D1的正確性，塊1中的所有數據包則可以通過自身攜帶的認證信息得到驗證。

(b)在有包丟失的情況下，如果丟失的是用于認證的密鑰信息，則無須處理，因為可以利用單向函數的特性對以后收到的密鑰包進行相應次數的運算而獲得，只是推遲了認證而已。比如Hn-1(α)丟失，則可以等收到Hn-2(α)之后，通過計算H(Hn-2(α))=Hn-1(α)得到Hn-1(α)，從而驗證相關的數據包。如果塊的消息摘要丟失，則使用本文附加的與兩個塊相關的小組的摘要信息認證。比如D2丟失，認證P12的方法為:P12通過自身攜帶的認證信息計算出D2:D1，22=h(h(M12)‖D22); D1，42=h(D1，22‖D3，42);D2=h(D1，42‖D5，82)。只要塊1中有一個包收到，則用同樣的方法可以求出D1，進而計算出D1，2=h(D1‖D2)。這樣，通過驗證小組的摘要D1，2可以達到認證包P12的目的。

本文提出的源認證方案是基于樹鏈認證以及T-CSA。先采用樹鏈認證的方法計算每個塊的摘要，然后將每個塊的摘要看成一個新的數據流，采用T-CSA的方法進行傳送及驗證。當一個塊的摘要得到驗證時，每個串內的包就可以使用自身攜帶的認證信息進行認證。這樣，擴大了T-CSA方案的優越性，將其影響從一個包擴展到一個塊。為了增加抗丟包的能力，根據網絡的丟包情況，將相鄰塊構成小組，并插入了小組的摘要信息。通過小組內塊間的互助行為也可以達到認證數據包的目的。

2.3 方案的性能分析及比較

下面從計算耗費、通信代價、包平均驗證代價以及認證率等方面進行性能比較:

a)計算耗費的分析[9]。假設每個消息包的長度為m字節，SHA算法的計算耗費為αx+β(x為輸入的消息長度)，數字簽名采用基于公鑰的RSA算法，假設其計算耗費為γ。現分析本方案的計算耗費如下(以n個包為單位):

產生滿二叉樹的所有葉子節點的代價為

(mα+β)2k+1

計算滿二叉樹的其余節點的函數值的耗費為

(40α+β)(2k+1-1)

計算滿二叉樹的所有節點的總耗費為

(mα+β)2k+1+(40α+β)(2k+1-1)

為了認證，還需要三次哈希函數計算，其代價為

3(40α+β)

故n個包的計算開銷為

(((m+40-40/2k+1)α+(2-1/2k+1)β)2k+1+3(40α+β))n2k+1

b)通信代價分析。從方案的描述可以看出，為了得到驗證，每個包額外攜帶了k個哈希值，故其通信代價為20 KB(SHA算法的哈希值為160 bit)。

c)包平均驗證代價。文獻[1，9]都是針對一個大的數據塊進行簽名，如此反復，當數據量不斷增多時，簽名次數也會相應增加。當通信量一定時，每個包的平均驗證代價是固定的。本方案卻不然，無論數據量有多大，只有一個簽名包。這樣，隨著數據量的不斷增多，每個包的平均認證代價會不斷降低，從而突出其優勢。從方案的描述可以看出，新方案中只有一個簽名包，為了認證，每個包攜帶了k個哈希值，同時，為了認證數據塊及其小組的摘要信息，又附加了三個哈希運算。假定所有的數據包總數為n′，則包平均認證代價可表示為

(k+3/2k+1)Ch+Cs/n′

表1為幾個基于樹鏈的源認證方案的性能比較。

注:以組的大小為n時進行比較，n′代表整個數據流中所有包的總個數。表中Cs和Ch分別表示驗證簽名以及一次哈希運算的代價。另外在文獻[9]中，選擇ns=2。

不同的設備和環境，安全算法的速度差異非常大。從總體上來說，哈希算法的速度為對稱算法的一個數量級左右，為簽名驗證的三個數量級左右，為簽名的四個數量級左右。直觀上來看，如果用10 h能完成一次數字簽名，大約需2.2 s就可以進行一次哈希計算。這里選擇SHA-1對消息進行哈希運算，雖然MD5的速度要比SHA-1快一倍左右，但SHA-1具有更高的安全性，而且其速度也是RSA公鑰運算的3~4個數量級。從表1可以看出，當包的數目不斷增多時[7]，新提出的方案中，計算耗費及包平均認證代價下降得更快，逐漸成為所有方案中最少的;隨著數據包的進一步增加，其優勢將更加明顯。這一切都源于簽名的次數最少的緣故。

d)認證率仿真。包丟失模型的選擇與認證率和選擇的丟包模型有直接關系[3，10]，突發丟包模型更能準確地描述網絡丟包現象。這里仍采用2狀態的馬爾可夫鏈作為突發丟包模型， 同文獻[6]一樣，通過編寫模擬程序來比較幾個方案之間的認證率(對1 024個包進行了1 000次仿真)，仿真結果如圖3和4所示。在此，僅將本方案與著名的EMSS、文獻[9]進行比較。從仿真結果可以看出，當通信量增大時，EMSS的認證率提高，本方案與文獻[9]的認證率沒有大的變化。本方案在包丟失率達到50%時，驗證率仍高達90%左右，遠遠高于EMSS，能滿足大部分實際應用的需求。與文獻[9]相比，認證率有所下降。

表2為本方案與T-CSA方法的比較。

表2 本方案和T-CSA方案的比較

比較項本方案T-CSA

收到一個密鑰可驗證的數據包個數2k1

包平均延遲時間小大

3 結束語

組播源認證作為組播的核心問題備受關注，設計一個安全、高效的不可否認組播源認證協議迫在眉睫[10]。本文在分析以往提出的一些組播源認證方案的基礎上，提出了一種新的組播源認證方案。分析表明，基于數鏈認證技術的新方案最大的特色在于:隨著數據流的不斷增多，每個包平均的認證代價會不斷下降，而且對接收方緩存要求不高，延遲較小，但其認證率低于文獻[9]方案。該方案特別適用于數據量比較大、接收方資源有限，而且對延遲敏感的一些組播應用。

參考文獻:

[1]

WONG C K，LAM S S.Digital signatures for flows and multicasts[J].IEEE ACM Trans on Networking， 1999，7(4):502-513.

[2]GENNARO R，ROHATGI P.How to sign digital streams[J].Information and Computation，2001，165(1):100-116.

[3]GOLLE P，MODADUGO N.Streamed authentication in the presence of random packet loss[C]//Proc of ISOC Network and Distributed System Security Symposium.2001:13-22.

[4]PERRIG A，CANETTI R，TYGAR J D，et al.Efficient authentication and signing of multicast streams over lossy channels[C]//Proc of IEEE Symposium on Security and Privacy.2000:56-73.

[5]BERGADANO F，CAVAGNINO D.Dealing with packet loss in the interactive chained stream authentication protocol[J].Computers Security，2005，24(2):139-146.

[6]WANG Wei-dong，LI Zhi-tang，LU Chui-wei，et al.An efficient multicast source authentication protocol[J].Wuhan University Journal of Natural Sciences，2006，11(6):1831-1834.

[7]LI Bao-hong，HOU Yi-bin.Performance optimization for multicast packet authentication[J].Journal of Chongqing University:English Edition，2005，4(3):154-157.

[8]BERGADANO F，CAVAGNINO D，CRISPO B.Individual authentication in multiparty communications[J].Computers Security，2002，21(8):719-735.

[9]PARK Y S，CHUNG T S，CHO Y.An efficient stream authentication scheme using tree chaining[J]. Information Processing Letters，2003，86(1):1-8.

[10]BARNETT C A.Efficient reliable and secure source authentication schemes for real-time multicast[D].Maryland:University of Maryland， 2003.