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

趙曄暉

(寧夏銀川河東機場民航寧夏空管分局氣象臺,寧夏銀川750009)

1 研究內容和意義

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

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

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

(2)改進了SPKI/SDSI系統中證書鏈搜索算法。仔細研究了目前各種SPKI/SDSI證書鏈搜索算法,分析各種算法優缺點,設計一個高效的證書鏈改進算法。

(3)對改進的證書鏈搜索算法進行測試。通過實驗數據詳細分析了影響證書鏈搜索效率的參數,最后得出實驗結論,證實了改進算法證書規模越大算法優勢越明顯的推斷。

2 基于認證的訪問控制模型的設計與實現

2.1 訪問控制模型設計思路

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

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

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

基于上述兩種設計方式的優缺點,訪問控制模型設計策略是:

(1)服務器端設計

分解資源服務器功能,將傳統的資源服務器按照功能分解成資源控制服務器、在線驗證服務器、證書管理服務器3部分。

(2)客戶端設計

設計思想:采用計算機內存管理中cache緩存思想,在客戶端構建一個規模較小的證書庫,里面存儲的證書只與當地客戶端訪問的資源有關,搜索任務可以不必由證書管理服務器做,減輕了服務器的負擔,有利于系統整體性能的提高。模型設計如圖1所示。

圖1 訪問控制模型

2.2 模型工作流程

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

資源控制服務器主要功能是采用相關控制策略,審核驗證訪問者的合法權限,限制訪問者的具體相關操作權限,保證資源的受控和合法使用。

證書管理服務器主要任務是:管理證書庫,將頒發的證書存放到證書庫中;進行證書鏈的搜索。在線驗證服務器,主要是驗證證書是否有效,其中設置一在線驗證進程,若在資源管理服務器中有證書在線測試申請,調用該進程進行在線測試,并返回給資源控制器相關信息。

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

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

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

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

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

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

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

圖2 模型執行流

3 基于認證的SPKI/SDSI證書鏈搜索算法

3.1 相關證書鏈算法

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

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

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

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

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

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

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

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

3.2 改進的證書鏈算法

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

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

假設某一實體關于資源Y的授權證書公鑰KA或者名字存放ACL處,另一實體的公鑰KB申請關于資源Y的訪問請求。

算法總體框架:

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

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

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

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

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

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

算法1流程如圖3所示。

算法2,本算法共兩個函數,實現功能:利用算法1的結果,在證書中查找證書鏈,函數返回1代表查找成功,返回0代表查找失敗。

算法2流程如圖4所示。

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

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

4 實驗結果分析

實驗過程中的軟硬件支持環境為:Windows XP 2000,2.0G的內存,VC++6.0。實驗目的主要是判斷算法的效率,由于是測試算法的性能,所以在模擬實驗中沒有必要使用真實的證書,使用的是證書的4元組(名字證書)和5元組(授權證書)形式。

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

對選取的4種算法進行實驗,通過數據進行分析,實驗結果如圖5所示。

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

表1 參數表

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

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

5 結束語

文中以SPKI/SDSI證書為理論基礎,設計和實現了一個基于SPKI/SDSI的訪問控制模型,并提出了一種新的證書鏈搜索算法,極大地提高了證書鏈搜索效率,具有可行性和有效性,實驗證明,證書數量越大,算法效率提高明顯。

[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.