趙曄暉

(寧夏銀川河?xùn)|機(jī)場(chǎng)民航寧夏空管分局氣象臺(tái),寧夏銀川750009)

1 研究?jī)?nèi)容和意義

為解決傳統(tǒng)PKI存在的缺陷問(wèn)題,麻省理工學(xué)院(MIT)的教授Butler Lampson、J.C.Mitchell[1-2]、Ronald Rivest[3-4]等在1996年提出“簡(jiǎn)單分布式安全基礎(chǔ)設(shè)施(Simple Distributed Security Infrastructure,SDSI)”的概念。然而SPKI/SDSI也存在缺陷:只限于理論上,并沒(méi)有一個(gè)成熟的系統(tǒng)[5-6];SPKI/SDSI最關(guān)鍵的是證書(shū)鏈搜索[7-8]算法,目前存在的證書(shū)鏈搜索算法復(fù)雜度高,難以應(yīng)用于實(shí)踐。

針對(duì)上述情況,主要工作如下:

(1)設(shè)計(jì)一個(gè)分布式訪問(wèn)控制模型:借鑒操作系統(tǒng)中緩存和同步的思想,設(shè)計(jì)出一個(gè)基于SPKI/SDSI證書(shū)的分布式訪問(wèn)控制模型,并給出了模型工作的具體流程圖。

(2)改進(jìn)了SPKI/SDSI系統(tǒng)中證書(shū)鏈搜索算法。仔細(xì)研究了目前各種SPKI/SDSI證書(shū)鏈搜索算法,分析各種算法優(yōu)缺點(diǎn),設(shè)計(jì)一個(gè)高效的證書(shū)鏈改進(jìn)算法。

(3)對(duì)改進(jìn)的證書(shū)鏈搜索算法進(jìn)行測(cè)試。通過(guò)實(shí)驗(yàn)數(shù)據(jù)詳細(xì)分析了影響證書(shū)鏈搜索效率的參數(shù),最后得出實(shí)驗(yàn)結(jié)論,證實(shí)了改進(jìn)算法證書(shū)規(guī)模越大算法優(yōu)勢(shì)越明顯的推斷。

2 基于認(rèn)證的訪問(wèn)控制模型的設(shè)計(jì)與實(shí)現(xiàn)

2.1 訪問(wèn)控制模型設(shè)計(jì)思路

以SPKI/SDSI分布式系統(tǒng)為基礎(chǔ)進(jìn)行訪問(wèn)控制,必須考慮證書(shū)鏈的搜索問(wèn)題。在海量證書(shū)庫(kù)中進(jìn)行證書(shū)鏈的搜索是一件非常耗費(fèi)資源的事情,目前對(duì)證書(shū)鏈搜索的處理主要有兩種方式:

(1)在資源服務(wù)器端進(jìn)行證書(shū)鏈的搜索[9]。采用這種方式時(shí),大量證書(shū)的更新、訪問(wèn)會(huì)影響服務(wù)器的性能,會(huì)導(dǎo)致服務(wù)器的阻塞;而且,證書(shū)鏈的搜索是非常耗費(fèi)資源的,在服務(wù)器上進(jìn)行搜索證書(shū)無(wú)疑進(jìn)一步加重服務(wù)器的負(fù)擔(dān)。

(2)在客戶(hù)端進(jìn)行證書(shū)鏈的搜索。采用這種方式,使證書(shū)庫(kù)管理不便,證書(shū)庫(kù)分散存放到客戶(hù)端。難以對(duì)證書(shū)進(jìn)行更新,會(huì)造成多個(gè)客戶(hù)端證書(shū)庫(kù)不統(tǒng)一的現(xiàn)象。

基于上述兩種設(shè)計(jì)方式的優(yōu)缺點(diǎn),訪問(wèn)控制模型設(shè)計(jì)策略是:

(1)服務(wù)器端設(shè)計(jì)

分解資源服務(wù)器功能,將傳統(tǒng)的資源服務(wù)器按照功能分解成資源控制服務(wù)器、在線驗(yàn)證服務(wù)器、證書(shū)管理服務(wù)器3部分。

(2)客戶(hù)端設(shè)計(jì)

設(shè)計(jì)思想:采用計(jì)算機(jī)內(nèi)存管理中cache緩存思想,在客戶(hù)端構(gòu)建一個(gè)規(guī)模較小的證書(shū)庫(kù),里面存儲(chǔ)的證書(shū)只與當(dāng)?shù)乜蛻?hù)端訪問(wèn)的資源有關(guān),搜索任務(wù)可以不必由證書(shū)管理服務(wù)器做,減輕了服務(wù)器的負(fù)擔(dān),有利于系統(tǒng)整體性能的提高。模型設(shè)計(jì)如圖1所示。

圖1 訪問(wèn)控制模型

2.2 模型工作流程

模型主要有以下幾部分組成:資源控制服務(wù)器、在線驗(yàn)證服務(wù)器、證書(shū)管理服務(wù)器、本地證書(shū)庫(kù)、服務(wù)器證書(shū)庫(kù)、授權(quán)實(shí)體、訪問(wèn)控制列表(ACL)等。

資源控制服務(wù)器主要功能是采用相關(guān)控制策略,審核驗(yàn)證訪問(wèn)者的合法權(quán)限,限制訪問(wèn)者的具體相關(guān)操作權(quán)限,保證資源的受控和合法使用。

證書(shū)管理服務(wù)器主要任務(wù)是:管理證書(shū)庫(kù),將頒發(fā)的證書(shū)存放到證書(shū)庫(kù)中;進(jìn)行證書(shū)鏈的搜索。在線驗(yàn)證服務(wù)器,主要是驗(yàn)證證書(shū)是否有效,其中設(shè)置一在線驗(yàn)證進(jìn)程,若在資源管理服務(wù)器中有證書(shū)在線測(cè)試申請(qǐng),調(diào)用該進(jìn)程進(jìn)行在線測(cè)試,并返回給資源控制器相關(guān)信息。

客戶(hù)端,主要指發(fā)出訪問(wèn)請(qǐng)求的用戶(hù)的集合,在客戶(hù)端采用內(nèi)存管理中的緩存思想,設(shè)置一個(gè)較小的證書(shū)庫(kù),保存與本客戶(hù)端訪問(wèn)相關(guān)的證書(shū)。

具體來(lái)說(shuō),一個(gè)用戶(hù)訪問(wèn)資源的過(guò)程有以下幾步:

(1)首先客戶(hù)端發(fā)出訪問(wèn)申請(qǐng),訪問(wèn)資源控制服務(wù)器,并與之建立連接:客戶(hù)端在本地證書(shū)庫(kù)中進(jìn)行證書(shū)鏈的查找,根據(jù)查找的結(jié)果向資源控制服務(wù)器發(fā)送不同的訪問(wèn)請(qǐng)求:若在本地證書(shū)庫(kù)中找到一條證書(shū)鏈,則直接用自己的私鑰簽名,向資源服務(wù)器發(fā)出資源的訪問(wèn)請(qǐng)求;若在本地證書(shū)庫(kù)中查找不到證書(shū)鏈,則向資源控制發(fā)送訪問(wèn)請(qǐng)求,請(qǐng)求信息要求證書(shū)管理服務(wù)器搜索證書(shū)鏈,資源控制服務(wù)器將該請(qǐng)求信息發(fā)送給證書(shū)管理服務(wù)器。

(2)收到客戶(hù)端的訪問(wèn)請(qǐng)求后,資源控制服務(wù)器根據(jù)客戶(hù)端用戶(hù)請(qǐng)求信息的不同執(zhí)行不同的進(jìn)程:若客戶(hù)端用戶(hù)請(qǐng)求信息中不包含證書(shū)鏈,此時(shí)資源控制服務(wù)器向證書(shū)控制管理器發(fā)出證書(shū)鏈搜索申請(qǐng),在服務(wù)器證書(shū)庫(kù)中進(jìn)行證書(shū)鏈的搜索;若客戶(hù)端用戶(hù)請(qǐng)求信息中包含一條證書(shū)鏈,資源控制服務(wù)器首先驗(yàn)證審核證書(shū)鏈的合法性,驗(yàn)證通過(guò)后,允許客戶(hù)端發(fā)出的訪問(wèn)請(qǐng)求,若客戶(hù)端驗(yàn)證非法,則返回拒絕信息。在進(jìn)行證書(shū)鏈的驗(yàn)證時(shí),若要求在線測(cè)試,則將證書(shū)鏈提交給在線驗(yàn)證服務(wù)器,進(jìn)行驗(yàn)證。在線驗(yàn)證服務(wù)器,返回驗(yàn)證的相關(guān)信息(合法或者非法)給資源控制服務(wù)器。

(3)證書(shū)管理服務(wù)器在收到證書(shū)資源控制器發(fā)出的證書(shū)鏈搜索請(qǐng)求后,在服務(wù)器證書(shū)庫(kù)中進(jìn)行證書(shū)鏈的搜索,若搜索到證書(shū)鏈,則將該證書(shū)鏈返回給資源控制服務(wù)器,然后在資源控制服務(wù)器上進(jìn)行合法性驗(yàn)證;若找不到證書(shū)鏈,返回找不到信息給資源控制服務(wù)器。

(4)證書(shū)管理服務(wù)器將證書(shū)鏈的搜索結(jié)果返回給資源控制服務(wù)器,如果通過(guò)驗(yàn)證,則允許客戶(hù)端用戶(hù)執(zhí)行相應(yīng)的服務(wù)請(qǐng)求,并將證書(shū)鏈返回給客戶(hù)端,保存在本地證書(shū)庫(kù)中,否則返回給客戶(hù)端一條拒絕信息。

按照上述4個(gè)步驟,客戶(hù)端訪問(wèn)資源的具體執(zhí)行流程如圖2所示。

圖2 模型執(zhí)行流

3 基于認(rèn)證的SPKI/SDSI證書(shū)鏈搜索算法

3.1 相關(guān)證書(shū)鏈算法

MIT的Clarke D和Elian J對(duì)SPKI/SDSI做了大量的研究,針對(duì)SPKI/SDSI系統(tǒng)提出算法框架,算法中假定證書(shū)存放在用戶(hù)中,算法的目的是找到一條從ACL(訪問(wèn)控制列表中)授權(quán)源到用戶(hù)申請(qǐng)者公鑰之間的證書(shū)鏈。若能通過(guò)證書(shū)規(guī)約找到如下形式的證書(shū)鏈:K∈G(Y)[1]→…→KA(G(Y)表示資源Y的公鑰集合),則查找成功。設(shè)計(jì)出了如下的算法框架:

(1)在證書(shū)集合Ccert中驗(yàn)證證書(shū)的有效性,去掉那些無(wú)效的證書(shū)。其中無(wú)效證書(shū)是指沒(méi)通過(guò)驗(yàn)證的證書(shū)、超過(guò)有效期內(nèi)的證書(shū)

把證書(shū)集合Ccert中的名字證書(shū)進(jìn)行規(guī)約,計(jì)算名字閉包,將所有的授權(quán)證書(shū)中都轉(zhuǎn)化成如下的形式:K[1]→KA[z](z=1或者 z=0)

(2)在證書(shū)閉包集合Ccert#中,收集對(duì)象是單個(gè)公鑰的授權(quán)證書(shū),去掉其他的證書(shū),收集完后,證書(shū)閉包集合Ccert#中所有的授權(quán)證書(shū)只有如下的形式:

KA[1]→KB[z](z=1或者 z=0)

(3)將第(2)步得到的授權(quán)證書(shū),建立一個(gè)授權(quán)有向圖。

(4)授權(quán)證書(shū)圖中,運(yùn)用深度優(yōu)先搜索算法,查找證書(shū)鏈判斷是否存在一條從請(qǐng)求者到資源擁有者之間的證書(shū)鏈路徑,若是存在返回成功,否則返回失敗。

假定在一個(gè)證書(shū)集C中有N張證書(shū),證書(shū)中最長(zhǎng)的擴(kuò)展名長(zhǎng)度為 L。初始名字閉包中最多有 O(N2L)張證書(shū),每一張名字證書(shū)做多只能匹配O(N)張證書(shū),在沒(méi)有進(jìn)行深度優(yōu)先搜索算法之間,僅僅名字閉包規(guī)約算法復(fù)雜度為O(N3L)

3.2 改進(jìn)的證書(shū)鏈算法

正常情況下,當(dāng)一個(gè)客戶(hù)端用自己的私鑰簽名去申請(qǐng)?jiān)L問(wèn)某項(xiàng)服務(wù)時(shí),只需要將證書(shū)庫(kù)中涉及的某幾個(gè)證書(shū)(授權(quán)證書(shū)或者名字證書(shū))進(jìn)行規(guī)約合并,形成一條證書(shū)鏈,而不必全部訪問(wèn),因此在設(shè)計(jì)算法時(shí),只考慮證書(shū)鏈上與訪問(wèn)請(qǐng)求相關(guān)的證書(shū)。

在ACL(Access Control List)訪問(wèn)控制列表中,授權(quán)證書(shū)用如下形式表示:Self[1]→KA[z](Self[1]→KA Classmates[z]),授權(quán)證書(shū)存放在KA處。

假設(shè)某一實(shí)體關(guān)于資源Y的授權(quán)證書(shū)公鑰KA或者名字存放ACL處,另一實(shí)體的公鑰KB申請(qǐng)關(guān)于資源Y的訪問(wèn)請(qǐng)求。

算法總體框架:

(1)在哈希表中定位到Hash(KB),在鏈表中查找是否存在KA,若存在直接返回(1),否則執(zhí)行步驟(2);

(2)找到某一實(shí)體KA的所有名字證書(shū)和授權(quán)證書(shū);

(3)運(yùn)用深度優(yōu)先算法查找從KA到KB的證書(shū)鏈;

(4)若存在從KA到KB的證書(shū)鏈,在哈希表中Hash(KB)的鏈表中添加KA,返回(1)(成功),否則返回0(代表查找失敗)

算法由算法1和算法2組成:

算法1,本算法查找服務(wù)器上關(guān)于資源Y的對(duì)象為K的名字集合和授權(quán)證書(shū)集合,其中授權(quán)證書(shū)集合放在CAuthor(K,X)中,名字集合放在Name(K)中。

算法1流程如圖3所示。

算法2,本算法共兩個(gè)函數(shù),實(shí)現(xiàn)功能:利用算法1的結(jié)果,在證書(shū)中查找證書(shū)鏈,函數(shù)返回1代表查找成功,返回0代表查找失敗。

算法2流程如圖4所示。

設(shè)計(jì)的證書(shū)鏈搜索算通過(guò)兩個(gè)算法,在存在大量證書(shū)的證書(shū)庫(kù)中,快速地實(shí)現(xiàn)了證書(shū)鏈的搜索。算法采用逆向搜索,從資源請(qǐng)求者開(kāi)始查找,一直查找到ACL表中,算法查找過(guò)程中只規(guī)約與證書(shū)鏈相關(guān)的證書(shū),大大提高了查找效率。同時(shí)需要特別注意的是,算法中利用緩存思想,將以前搜索到的證書(shū)鏈保存到一個(gè)哈希表中,下次查找時(shí),直接查找哈希表,隨著哈希表逐漸增大,查找速度會(huì)進(jìn)一步提高。

圖5 4種算法搜索證書(shū)鏈所用時(shí)間對(duì)比

4 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)過(guò)程中的軟硬件支持環(huán)境為:Windows XP 2000,2.0G的內(nèi)存,VC++6.0。實(shí)驗(yàn)?zāi)康闹饕桥袛嗨惴ǖ男?由于是測(cè)試算法的性能,所以在模擬實(shí)驗(yàn)中沒(méi)有必要使用真實(shí)的證書(shū),使用的是證書(shū)的4元組(名字證書(shū))和5元組(授權(quán)證書(shū))形式。

模擬實(shí)驗(yàn)中,具體使用的實(shí)驗(yàn)數(shù)據(jù)在很大程度上影響著實(shí)驗(yàn)的精度,并決定著實(shí)驗(yàn)的參考價(jià)值。模擬實(shí)驗(yàn)中,用一個(gè)隨機(jī)函數(shù)生成實(shí)驗(yàn)所需要的各種參數(shù),以生成不同的證書(shū)集。主要是生成證書(shū)的密鑰個(gè)數(shù)(K),證書(shū)名字個(gè)數(shù)(m),證書(shū)鏈長(zhǎng)度(H),實(shí)體擁有的授權(quán)證書(shū)個(gè)數(shù)(G),證書(shū)擴(kuò)展名長(zhǎng)度(L),證書(shū)數(shù)量(n)。進(jìn)行實(shí)驗(yàn)時(shí)要設(shè)置不同的證書(shū)集,只需設(shè)置不同的參數(shù)即可。

對(duì)選取的4種算法進(jìn)行實(shí)驗(yàn),通過(guò)數(shù)據(jù)進(jìn)行分析,實(shí)驗(yàn)結(jié)果如圖5所示。

其中,當(dāng)證書(shū)數(shù)量分別為1000、2000、3000、5000和10000、20000、30000、50000時(shí),測(cè)試函數(shù)其他的參數(shù)如表1所示。

表1 參數(shù)表

從圖5的實(shí)驗(yàn)數(shù)據(jù)看出,Clarke D算法和基于雙容器算法花費(fèi)的時(shí)間比較長(zhǎng),Clarke D算法花費(fèi)的時(shí)間最長(zhǎng),這兩種算法都是集中式算法,主要時(shí)間花費(fèi)在證書(shū)縮減上,證書(shū)縮減的復(fù)雜度都是O(N3L),其中N為系統(tǒng)中證書(shū)的總的數(shù)量,其中基于容器算法搜索證書(shū)鏈的時(shí)間比Clarke D算法稍微快一些。

明顯看出,證書(shū)的規(guī)模越大,改進(jìn)算法的性能優(yōu)勢(shì)越明顯。證書(shū)數(shù)量較少時(shí),改進(jìn)的算法優(yōu)勢(shì)并不明顯,證書(shū)數(shù)量越多,改進(jìn)的算法與其他兩種算法相比,優(yōu)勢(shì)越明顯,原因是改進(jìn)算法在證書(shū)鏈搜索時(shí),只是涉及到與證書(shū)鏈搜索相關(guān)的證書(shū),不去規(guī)約大量無(wú)關(guān)的證書(shū),而前兩種算法是集中式算法,進(jìn)行證書(shū)鏈搜索時(shí),無(wú)論證書(shū)鏈多長(zhǎng)都把所有的證書(shū)牽扯進(jìn)來(lái),造成大量無(wú)關(guān)證書(shū)的規(guī)約,致使效率降低,與預(yù)期的想法一致。證書(shū)規(guī)模較小時(shí),上述幾種算法效率相差不大。改進(jìn)的算法對(duì)比前兩種算法,在證書(shū)規(guī)模越大時(shí),算法的優(yōu)勢(shì)越明顯,因此改進(jìn)的算法適合大規(guī)模分布式網(wǎng)絡(luò)環(huán)境。

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

文中以SPKI/SDSI證書(shū)為理論基礎(chǔ),設(shè)計(jì)和實(shí)現(xiàn)了一個(gè)基于SPKI/SDSI的訪問(wèn)控制模型,并提出了一種新的證書(shū)鏈搜索算法,極大地提高了證書(shū)鏈搜索效率,具有可行性和有效性,實(shí)驗(yàn)證明,證書(shū)數(shù)量越大,算法效率提高明顯。

[1] Carl Ellison.SPKI/SDSI and the Web of Trust[J].Journal of Computer Security,2010,11(6):132-141.

[2] Buter W Lampson,Martin Abadi,Michael Burrows,et al.Authentication in Distributed Systems:Theory and Practice[J].ACM Transactions on Computer Systems,2011,10(4):265-310.

[3] B Lampson,Sean Smith.Using SPKI/SDSI for distributed maintenance of attribute release polices in shibbolefth[J].Journal of Computer Security,2010,9(4):235-239.

[4] Nazareth S,B Schneier.Ten Risk of PKI:What You are Not Beinig Told About Public Key Infrastructure[J].Communication of the ACM,2009,32(6).

[5] C Ellison,B Schneier.Risks of PKI:Electronic[J].Communication of the ACM,2010,43(2).

[6] Sameer Ajmani,Dwaine E Clark,Chuang-Hua Moh,etal.ConChord:Cooperative SDSI Certificate Storage and Name Resolution[J].IEEE Communications,2010,11(6):132-141.

[7] Martin Abadi.On SDSI's Linked Local Name Spaces[J].Journal of Computer Security,2008,6(1-2):3-21.

[8] Xavier Orri,J M Mas,Octalis SA.SPKI-XML Certificate Structure.draft-orri-spki-xml-cert-struc-00.ext[EB/OL].http://www.ecom.tifr.res.in/-wvp/pki/SPKI/draft-orri-spki-xml-cert-struc-00.pdf,2010.

[9] Yki Kortesniemi.SPKI Performance and certificate Chain Reduction[J].Journal of Computer Security,2010,15(9):131-137.