基于SPKI/SDSI證書鏈搜索算法與訪問控制模型設(shè)計

趙曄暉

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

1 研究內(nèi)容和意義

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

針對上述情況,主要工作如下:

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

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

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

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

2.1 訪問控制模型設(shè)計思路

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

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

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

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

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

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

(2)客戶端設(shè)計

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

圖1 訪問控制模型

2.2 模型工作流程

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

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

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

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

具體來說,一個用戶訪問資源的過程有以下幾步:

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

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

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

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

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

圖2 模型執(zhí)行流

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法總體框架:

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

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

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

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

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

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

算法1流程如圖3所示。

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

算法2流程如圖4所示。

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

圖5 4種算法搜索證書鏈所用時間對比

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

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

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

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

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

表1 參數(shù)表

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

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

5 結(jié)束語

文中以SPKI/SDSI證書為理論基礎(chǔ),設(shè)計和實(shí)現(xiàn)了一個基于SPKI/SDSI的訪問控制模型,并提出了一種新的證書鏈搜索算法,極大地提高了證書鏈搜索效率,具有可行性和有效性,實(shí)驗(yàn)證明,證書數(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.