基于秘密共享的(t,m,n)-AS組認證方案

,,

(中國科學技術大學 計算機科學與技術學院,合肥 230027)

0 概述

身份認證是保障通信安全的重要手段,在日益復雜的網絡通信環境中,高效的身份認證機制成為信息安全專家研究的重點之一。傳統身份認證有2種基本的實現方式:無第三方參與的認證和有第三方參與的認證。在無第三方參與的認證系統中,認證雙方利用事先共享的秘鑰或者公開秘鑰體制進行身份認證;在有第三方參與的認證系統中,認證雙方在可信認證中心的支持下驗證彼此的身份。

現有的認證方案大多都是一對一的認證[1-4],即認證方每次認證一個用戶。但是很多網絡應用,如網絡會議、電子拍賣等,往往采用面向組的認證模式,即要求認證方案一次完成對組內所有成員的認證,這類認證被稱為組認證。目前已經存在很多種組認證方案,例如:文獻[5]針對Ad Hoc網絡提出的基于可信第三方的組認證方案,利用一種公鑰基礎設施PKI認證各個網絡節點;文獻[6]改進著名協議Kerberos提出的組認證方案Kaman,可以更好地適用于Ad Hoc網絡;文獻[7]針對Ad Hoc提出的EAP協議,將整個Ad Hoc網絡作為一個群組,并利用認證服務器(Authorization Server,AS)作為群組和其他網絡認證的媒介,所有組內成員的身份認證都由AS完成;文獻[8]提出的另一種組認證方案mGAP,通過管理域名預測移動節點行為并管理節點和組之間的認證;Harn提出的分布式組認證方案(t,m,n)-GAS,可以在O(1)時間內認證所有的參與者。該方案在注冊階段利用Shamir(t,n)秘密共享機制[10]為注冊的成員發送k個share。在認證階段,參與認證的m個參與者每人利用自己的share生成一個令牌,并收集其他參與者的令牌恢復秘密s,從而確認m個參與者是否屬于預先定義的一個組;文獻[11]提出的開放式PKI認證模型,改進了傳統的PKI方案,利用CA獨立完成2個驗證服務,從而提高了CA的信任度;文獻[12]提出的一對多認證的基本框架,不僅可以用于成員之間的互相認證,還可用于服務器和客戶端之間的認證。作為一種通用框架,該方案允許使用不同的公鑰機制(如Diffie-Hellman、DLP等)進行實現;在文獻[13]針對Ad Hoc網絡提出的基于線性配對無AS的組認證方案中,任何用戶都可以快速生成一個組,組成員的人數不受限制,且組成員之間可以互相認證并生成會話密鑰;文獻[14]則提出了一種基于Shamir秘密共享機制且支持欺騙檢測的組認證方案。

現有的組認證方案[5-6,8]多為擁有AS的集中式認證方案,但都是基于公鑰密碼機制實現,因而計算復雜,效率低下。這些方案都是一對一的認證方案,不能一次認證所有參與者。方案[15-16]是無AS的認證方案。方案[9]是基于秘密共享的分布式方案,雖然可以快速完成對所有組成員的認證,但是需要多個多項式且不夠靈活,并且該方案只能判斷組內是否存在非法成員,但是存在非法成員的情況下,無法確定具體的非法成員。

考慮以下應用場景:一組人計劃在某個時間舉行一個網絡會議,在會議開始之前所有參會人員可以隨時向認證服務器提交自己的身份信息,但是為提高認證效率,希望認證服務器在收到所有參會人員的身份信息之后,通過一次計算就能夠認證所有參與者,并且在有非法參與者的情況下對其進行隔離,保障會議順利進行。上述組認證的方案難以滿足該應用場景的要求。

本文基于Shamir秘密共享機制,提出一種包含組認證服務器的(t,m,n)組認證方案,并對其正確性和安全性加以驗證。

1 基礎知識

1.1 Shamir(t,n)秘密共享機制

(t,n)秘密共享[10]的基本設計思想是將一個秘密分割成n份share,并將每個share分發給一個參與者,只有t(t≤n)個或t個以上的參與者合作才能恢復秘密,少于t個參與者無法恢復秘密。方案包含一個Dealer及n個share持有者U={U1,U2,…,Un},t為門限,該方案包括2個算法:

1)share生成算法

Dealer隨機選擇一個大素數p,并在有限域GF(p)上選一個(t-1)次的隨機多項式f(x)=a0+a1x+…+at-1xt-1(modp),令秘密s=f(0)=a0∈GF(p),ai,i=1,2,…,t-1∈GF(p)。Dealer計算n個share,si=f(xi),i=1,2,…,n,xi是與Ui有關的公開信息。然后,Dealer通過安全信道將si秘密地發送給share持有者Ui。

2)秘密恢復算法

如果m(t≤m≤n)個share持有者(即參與者),如{U1,U2,…,Um}需要聯合恢復秘密s,則m個share持有者互相交換share,通過以下公式恢復秘密s:

在該方案中,任意大于等于t個參與者合作可以恢復秘密,而少于t個參與者得不到關于秘密的任何信息,因此,可以抵御t個以下參與者的聯合攻擊。該方案不基于任何的數學假設,是無條件安全的。

1.2 Harn(t,m,n)組認證方案

文獻[9]提出了一種分布式的(t,m,n)組認證方案,可以在O(1)時間內認證所有參與認證的用戶是否屬于預先定義的組。該方法具體描述如下:

1)注冊階段

2)認證階段

如果有m(t≤m≤n)個用戶,若{Ui|i=1,2,…,m}需要互相認證,則每個用戶利用自己的k個share生成一個令牌ti:

該方案基于秘密共享,在不依賴任何數學假設的前提下完成了對m個參與者的快速認證。但是該方案要求kt>(n-1),因而限制了門限t和參與者n的選擇,不夠靈活,并且該方案只能判斷所有參與認證的用戶是否屬于預先定義的組,在有非法參與者的情況下沒有給出有效的解決方案。

2 本文(t,m,n)-AS組認證方案

本文基于Shamir秘密共享提出一種(t,m,n)-AS組認證方案,其中:t為門限;m為參與認證的參與者個數;n為組內成員個數;AS為認證服務器。該方案共分為3個階段,分別為注冊階段、整體認證階段和單一認證階段。在整體認證階段,AS認證所有參與者中是否存在非法參與者,如果存在非法參與者,AS可以在單一認證階段確定所有的非法參與者。在單一認證階段,AS無需與參與者進行進一步交互。

2.1 實體

本文方案的包括1個組管理員GM、1個組認證服務器AS和若干參與者,具體如下:

1)組管理員GM:假設GM對于所有參與認證的成員是可信的。GM負責多項式參數及秘密的選擇、計算并公開秘密的Hash值、生成shares并安全地分發給組成員。組管理員只參與方案的注冊階段。

2)組認證服務器AS:假設AS對所有組成員是可信的,并且在AS和任意組成員之間有私有信道。AS負責方案的整體認證和單一認證。

3)參與者:稱在組管理員處成功注冊獲得有效share的用戶為組成員。在認證階段所有參與認證的用戶為參與者。

本文假設在認證階段所有參與者事先知道參與者數量及所有參與者的公開身份信息,例如參與網絡會議的人員可以事先通過會議通知中的參會人員列表等途徑了解要參與會議的人員。

2.2 攻擊模型

本文考慮2種攻擊模型,即非成員攻擊者和成員攻擊者。

1)非成員攻擊者:非成員攻擊者不是合法的組成員,和組管理員以及AS之間沒有私有信道。他們自身沒有share,但是可能通過破解組成員和AS之間的信道獲得令牌。本文假設非成員攻擊者最多可以獲取(m-1)個參與者的令牌。

2)成員攻擊者:成員攻擊者是合法的組成員且有有效share,但是他們可能串謀破壞認證或者企圖幫助非法參與者通過認證。本文假設最多有(t-1)個成員攻擊者合謀攻擊。

2.3 具體方案

本文方案包括注冊階段和認證階段。

1)注冊階段

同時,GM為組認證服務器AS生成2×(t-1)個share:f1(xk),f2(xk)(k=n+1,n+2,…,n+t-1),并安全地發送給AS。然后,GM在GF(p)上選擇2個數對(a1,b1)、(a2,b2),組成2個秘密:s1=a1f1(0)+b1f2(1)(modq)和s2=a2f1(0)+b2f2(1)(modq),使得s1、s2均在GF(q)上。GM計算s1和s2的單向哈希值H(s1)、H(s2),公開(a1,b1)、(a2,b2)及單向哈希函數H(·)。share分發過程如圖1所示。

圖1 share分發過程

2)認證階段

認證階段分為2個步驟,分別為統一認證和單一認證。統一認證是指AS確定所有參與者中是否存在非法參與者,而單一認證是指AS在不與參與者進一步交互的情況下確定所有的非法參與者。AS首先對所有參與者進行統一認證。

(1)統一認證

假設任意m(t≤m≤n)個用戶參與認證,其身份的下標集合記為Im?{1,2,…,n},|Im|=m,每個參與者Ui(i∈Im)計算2個令牌t1i,t2i(其中r1i、r2i是用戶Ui在GF(q)上選擇的隨機數)。Ui將t1i、t2i通過私有信道發送給AS。AS利用自己的share計算令牌tas(其中r是在GF(q)上選擇的隨機數)。

(2)單一認證

存在非法參與者時,AS可以直接對所有參與者進行單一認證,具體認證過程為:AS在對參與者Ui進行認證時,利用自己的share生成令牌ti(其中,ri為AS在GF(q)上均勻選擇的某個隨機數)。然后,AS計算s2′=(t2i+ti)modpmodq以及H(s2′);如果H(s2′)=H(s2),則Ui為組成員,否則Ui為非法參與者。對所有參與者進行此計算,可以在O(n)時間確定所有非法參與者。

3 方案正確性及安全性分析

3.1 方案的正確性分析

對本文方案進行正確性分析,具體如下:

1)統一認證過程的正確性分析

假設AS收集的所有參與者的令牌都合法有效,則一定能夠通過統一認證,因為:

2)單一認證的正確性分析

在對某個特定參與者進行單一認證時,假設參與者提供合法的令牌,則可以通過單一認證,計算公式如下:

[s2+(r2iq+riq)]modpmodq=s2

因為s2+r2iq+riq

3.2 安全性分析

本文在認證階段考慮成員和非成員2種攻擊者。非成員攻擊者沒有合法shares無法生成有效的令牌,但是它們可能破解AS與參與者之間私密信道從而獲得參與者的令牌。成員攻擊者有合法share,但是它們可能在少于t個成員情況下串謀企圖通過認證或者幫助非成員偽造share。

定理1給定某個參與者的令牌,攻擊者無法得到參與者的share,即通過令牌獲得其share的最大概率為1/q。

證明:假設用戶Ui的share為s1i、s2i,其公開身份信息為xi。在認證階段利用Ui的s1i、s2i生成令牌t1i、t2i,并發送給AS。攻擊者破解AS和Ui之間的安全信道獲得t1i、t2i:

將t1i、t2i用以下公式表示:

t1i=(α1s1i+β1s2i+r1iq)modp

t2i=(α2s1i+β2s2i+r2iq)modp

其中,α1、β1、α2、β2、p、q是已知信息,r1i、r2i都是GF(q)上的未知隨機數,化簡得:

s1i=(β2α1-β1α2)-1[β2t1i-β1t2i+(β1r2i-β2r1i)q]modp

因為r1i、r2i是未知的,對于任意的r1i、r2i都會有對應的s1i,由大數定律可知,當β1=-β2且r1i、r2i分別在[0,q-1]均勻變化時,β1r2i-β2r1i最多有q個相同的值,因此通過t1i,t2i獲得s1i的最大概率為q/q2=1/q,與直接在GF(q)上猜測s1i的概率相同。同理獲得s2i的最大概率也為1/q。

定理2(t-1)個成員攻擊者串謀無法通過整體認證,即(t-1)個成員攻擊者破解秘密s1的概率為1/q。

假設有(t-1)個成員,如U={U1,U2,…,Ut-1},其中 Ui∈U的share為s1i、s2i,t-1個組成員試圖串謀恢復秘密s1=a1f1(0)+b1f2(1)(modq)。欲恢復s1,需要確定f1(0)、f2(1)。先考慮f1(0),(t-1)個組成員利用他們的s1i,i=1,2,…,t-1得到以下方程組:

寫成矩陣形式XC=S,即:

X的秩最大為(t-1)

定理3非成員攻擊者即使截取(m-1)個參與者的令牌,也無法通過整體認證。確切地講,用(m-1)個參與者的令牌破解s1的概率為1/q。

證明:非成員攻擊者想要通過整體認證有2種可能的途徑。一種是攻擊者得到(m-1)個參與者的令牌后,嘗試從令牌恢復share,當(m-1)≥t時,攻擊者可以通過(m-1)個share直接恢復多項式,從而計算出秘密s1;另一種是嘗試直接通過令牌恢復秘密s1。下面分別證明2種方案破解s1的概率都為1/q。

1)假設非成員攻擊者截獲了U={U1,U2,…Um-1},這(m-1)個參與者與AS之間的私有信道并成功獲取他們的令牌t1i,t2i,i∈Im。由定理1可知通過令牌獲取share的最大概率為1/q,與直接猜測s1的概率相同,因此,無法通過令牌恢復多項式并通過認證。

2)假設非成員攻擊者能夠利用(m-1)個參與者的令牌直接恢復秘密出s1,則有:

由上式得:

t1mmodpmodq=0 ?t1mmodp=αq

其中,α為整數,當f1(x)、f2(x)的系數ci、di在GF(P)上呈均勻分布時,t1m在GF(P)上也是均勻分布的[17],則t1mmodp=αq成立的概率為(?p/q」+1)/p,當q趨于無窮大時,此概率趨近于1/q,即(m-1)個參與者通過整體認證的概率約為1/q。

綜上所述,定理3得證。

定理4參與者無合法令牌無法通過整體認證和單一認證,即如果參與者無合法令牌時,AS成功恢復秘密s1、s2的概率均約為1/p。

證明:

1)假如有m個參與者參與整體認證而其中一個參與者無合法令牌,想要通過整體認證,即等價于(m-1)個參與者通過認證,由定理3可知,(m-1)個參與者恢復秘密s1的概率約為1/p。}

2)假設對參與者Ui進行單一認證,AS針對Ui生成令牌ti若在Ui無合法令牌的情況下,AS恰好成功恢復秘密s2,則有s2=(ti+t2i′) modpmodq=(ti+t2i)modpmodq,推得(t2i-t2i′)modpmodq=0,即(t2i-t2i′)modp=αq。其中,α為整數,t2i′為Ui任意偽造的非法令牌。與定理3類似,對于某一偽造令牌t2i′,當q趨于無窮大時,(t2i-t2i′)modp=αq成立的概率趨近于1/q。因此參與者在無合法令牌時通過單一認證的概率約為1/q。

綜上所述,定理4得證。

4 方案特性

從3個方面分析本文方案的特性:

1)實用性。與Harn方案類似,本文方案不要求所有參與者同時將令牌發送給AS,在認證之前的任何時刻都可以隨時發送令牌。然而,Harn的方案要求kt>(n-1),多項式的個數(即每個人持有的share個數)和門限制約著參與者的人數。在門限不變的情況下,隨著n的增大,所需的多項式個數會越來越多,每個成員需要持有的share也越來越多。而本文方案在任何情況下都只需要2個多項式,每個參與者持有2個share。同時,文獻[9]的方案無法確定具體的非法參與者,而本文方案在整體認證的基礎上還可以對參與者進行單一認證,從而可以快速地確定非法參與者。因此,從存儲代價、通信代價,以及方案的完整性方面,本文方案具有更高的實用價值。

2)高效性。相對于一對一的認證方案[1-2],本文方案實現了一對多認證,AS可以在O(1)時間內確定所有的參與者是否都是組成員。相對文獻[5,8]方案,該方案不依賴公鑰密碼系統,計算簡單。相對于文獻[9]方案中每個參與者只需要兩個令牌,降低了存儲復雜度。而且在任何用戶和服務器之間只需要一次通信。

3)健壯性。該方案基于(t,n)門限秘密共享,可以抵御(t-1)個成員攻擊者的聯合攻擊。因為方案不是直接使用share而是通過構造令牌的方式參與認證,使得非成員攻擊者在截取了(m-1)個參與者令牌的情況下仍然無法通過認證。該方案不基于任何的計算假設,因而是理論上安全的。

5 結束語

本文針對網絡會議、Ad Hoc網絡、電子拍賣等面向組的應用,提出了一種集中式的(t,m,n)-AS組認證方案。在注冊階段,GM為每個組成員分發2個share;在認證階段,參與者利用share構造2個令牌發送給AS用于整體認證和單一認證。該方案不僅可以抵御(t-1)個成員攻擊者聯合偽造令牌攻擊,而且可以阻止非成員攻擊者在截取多達(m-1)個參與者令牌的情況下通過認證。本文方案不依賴于任何數學難題,在理論上是安全的。但其未考慮組成員動態變化的情況,而且在認證之前,參與者必須事先知道哪些參與者參與認證,這也使得使用場景受限。因此,下一步將研究動態群組的組認證問題,并突破必須預知參與者身份這一限制。

[1] DAS M L.Two-factor User Authentication in Wireless Sensor Networks[J].IEEE Transactions on Wireless Communications,2009,8(3):1086-1090.

[2] OPPLIGER R,HAUSER R,BASIN D.SSL/TLS Session-aware User Authentication[J].Computer,2008,41(3):59-65.

[3] 王 帥,常朝穩,魏彥芬.基于云計算的USB Key身份認證方案[J].計算機應用研究,2014,31(7):2130-2134.

[4] 謝 璇,王瑞剛,楊小寶,等.一種SD卡用戶身份認證方案的設計與實現[J].電子科技,2015,28(6):57-60.

[5] PIRZADA A A,MCDONALD C.A Review of Secure Routing Protocols for Ad Hoc Mobile Wireless Networks[C]//Proceedings of the 2nd Workshop on the Internet,Telecommunications and Signal Processing.Berlin,Germany:Springer,2003:57-80.

[6] PIRZADA A,MCDONALD C.Kerberos Assisted Authentication in Mobile Ad-Hoc Networks[C]//Proceedings of the 27th Australasian Computer Science Conference.Dunedin,New Zealand:[s.n.],2004:41-46.

[7] BHAKTI M A C,ABDULLAH A,JUNG L T.EAP-based Authentication for Ad Hoc Network[C]//Proceedings of Seminar Nasional Aplikasi Teknologi Informasi Conference.Yogyakarta,Indonesia:[s.n.],2007:133-137.

[8] ABOUDAGGA N,QUISQUATER J J,ELTOWEISSY M.Group Authentication Protocol for Mobile Networks[C]//Proceedings of the 3rd IEEE International Conference on Wireless and Mobile Computing,Networking and Communications.Washington D.C.,USA:IEEE Press,2007:28.

[9] HARN L.Group Authentication[J].IEEE Transactions on Computers,2013,62(9):1893-1989.

[10] SHAMIR A.How to Share a Secret[J].Communications of the ACM,1979,22(11):612-613.

[11] 周曉斌,許 勇,張 凌.一種開放式PKI身份認證模型的研究[J].國防科技大學學報,2013,35(1):169-174.

[12] YANG H,JIAO L,OLESHCHUK V A.A General Framework for Group Authentication and Key Exchange Protocols[M].Berlin,Germany:Springer,2014.

[13] FENG W,CHANG C C,CHOU Y C.Group Authentication and Group Key Distribution for Ad Hoc Networks[J].International Journal of Network Security,2015,17(2):199-207.

[14] GUO C,ZHUANG R,YUAN L,et al.A Group Authentication Scheme Supporting Cheating Detection and Identification[C]//Proceedings of the 9th International Conference on Frontier of Computer Science and Technology.Washington D.C.,USA:IEEE Press,2015:110-114.

[15] CABALLERO-GIL P,HERNNDEZ-GOYA C.Self-organized Authentication in Mobile Ad-Hoc Networks[J].Journal of Communications and Networks,2009,11(5):509-517.

[16] CAPKUN S,BUTTYAN L,HUBAUX J P.Self-organized Public-key Management for Mobile Ad Hoc Networks[J].IEEE Transactions on Mobile Computing,2003,2(1):52-64.

[17] MIAO F Y,XIONG Y,WANG X F.Randomized Component and Its Application to (t,m,n)-group Oriented Secret Sharing[J].IEEE Transactions on Information Forensics and Security,2015,10(5):889-899.