深度優先搜索構建證書路徑的算法研究

劉艷

摘 要：隨著互聯網的發展，PKI結構日益復雜。論文分析了目前存在的幾種典型的PKI信任模型，并設計了一種基于深度優先的遞歸算法來構建證書路徑，描述了詳細的算法流程。最后對該算法進行了優化，使其能提前排除無效路徑，減輕路徑驗證的負擔。

關鍵詞：PKI；信任模型；證書路徑構建；LDAP

中圖分類號：TP309 文獻標識碼：A

Abstract： With the development of Internet， PKI structures have become more and more complex. This paper analyzed some existing classical PKI trust models， and designed a recursive algorithm based on depth first to build certification path， and discussed the detailed algorithm flow. At last the algorithm was optimized so that it can exclude invalid paths in advance and reduce the burden of path validation.

Key words： PKI； trust model； certificate path building； LDAP

1 引言

公鑰基礎設施PKI（Public Key Infrastructure）[1]是一種解決Internet上種種安全問題的框架和遵循既定標準的密鑰管理平臺，它已經成為信息安全技術的核心和關鍵技術。由于互聯網不斷發展，PKI信任域互操作性有著越來越強的需求，信任模型越來越復雜。在復雜的信任模型下，不同信任域的實體間需要進行交叉認證，包含交叉證書的證書路徑的跨信任域構建問題成為難題之一。本文提出了一種基于深度優先的遞歸算法來構建證書路徑，并對構建過程進行優化，提高證書驗證的效率。

2 PKI信任模型

信任模型提供了一種用于建立并管理信任關系的框架，在PKI體系中，它的焦點是用戶與CA、CA之間的相互信任的關系。當前PKI系統包含三種最基本的信任模型。

（1）層次模型。該模型中所有的下屬CA及終端實體都信任唯一的根CA，各層CA具有嚴格的上下屬關系，故適合于具有同樣上下級關系的組織內部。這種模型中的路徑構建非常簡單，由于其從端實體到根CA具有單向性，采用前向構建比較合適。

（2）對等模型。該模型中，兩個CA沒有從屬關系，相互獨立，也沒有信任錨根CA。如果想建立雙邊的信任，雙方需要給對方頒發證書。該模型中的信任關系不可傳遞，可擴展性較差。這種模型的路徑構建只簡單涉及到兩個CA之間的交叉認證。

（3）網狀模型。該模型雖然以對等模型為基礎，但對等模型有直接交叉認證的一種限制，而該模型信任具有傳遞性，具有較好的擴展性。該種模型中的路徑構建比較復雜，涉及到多個CA之間的交叉認證。

然而，實際情況要復雜很多，僅用這三種基本的模型無法滿足實際需求。許多企業和機構采用了一些混合信任模型，比較成功的是ISO銀行業模型和橋CA模型[2-3]。

ISO銀行業模型如圖1所示，它是網狀模型與層次模型的結合體。同一信任域內采用層次信任模型，各信任域的根CA之間采用網狀模型。域內或域間連接兩個中介CA的高頻路徑可以建立直接交叉認證。該種模型的路徑構建不僅涉及到根CA之間的交叉認證還涉及到跨信任域中介CA之間的交叉認證。

圖2所示，橋CA實際上是一個中心級的交叉認證機構，用于連接不同的PKI體系。橋CA作為公共信任錨，但并不是所有用戶的，可以用于各參與CA的交叉認證，管理維護各CA間的策略映射。任何結構類型的PKI都可以通過橋CA連接在一起，實現彼此之間的信任。目前，橋CA模型比較成功地運用于美國聯邦政府。

由于要建立統一的第三方（橋CA），所以對于松散型的機構較難實現。任何結構類型的PKI，通過橋CA都可以連接并實現相互之間的信任，因此在該種模型上實現的路徑構建算法，實際上必須支持幾乎所有的信任模型[4]。

3 證書路徑的構建

證書使用前必須先驗證，為了驗證證書，就必須建立一條認證路徑，并驗證此路徑中的每個證書。該認證路徑包括了從待驗證的目標證書到信任錨之間的一系列證書。證書路徑構建通常有兩種方向[4]：一種是前向（Forward）構建，即從目標證書到信任錨；另一種是反向（Reverse）構建，即從信任錨到目標證書。針對各典型的PKI信任模型，本文研究并實現了一種較通用的基于深度優先搜索的前向路徑構建算法。

3.1 侯選證書的獲取

證書以及CRL存儲于諸如FTP、HTTP或LDAP服務器、X.500目錄服務器等載體中，這些載體一般都是公共且易于訪問的。證書中具有一些擴展項，可以用來提供URI信息。主體信息訪問擴展SIA（Subject Info Access）可以獲得由該證書所頒發的下級證書，具有該擴展的證書適合采用反向路徑構建方法。權威信息訪問擴展AIA（Authority Info Access），可以用來獲得上級頒發者證書信息或OCSP服務器的URI信息。通過AIA可以獲得一個或多個頒發者的證書，這些證書可以是CA證書也可以是交叉證書。具有AIA擴展的證書適合采用前向路徑構建，這也是本算法實現時獲取侯選證書所采用的主要方法。除此以外，還有很多其他的方法可以獲得證書，這主要依賴于PKI體系中證書的存儲結構和方式。本論文在具體實現時，證書和CRL存放于支持LDAP[5-6]的OpenLDAP目錄服務器[7]中。

Openssl函數庫[8]以及OpenLdap函數庫提供了很多底層函數，以下其中兩個關鍵函數：

int X509_get_ext_by_NID（X509 * x， int nid， int lastpos）；

X509_EXTENSION * X509_get_ext（X509 * x， int loc）；

X509_get_ext_by_NID函數通過給定的參數nid從證書擴展中對其進行定位，函數X509_get_ext通過定位loc，獲得該擴展。當想要獲得AIA擴展時，參數nid為NID_info_access，當想要獲得SIA擴展時，參數nid為NID_sinfo_access。

3.2 路徑構建算法

路徑構建的過程類似于對圖中兩頂點之間的路徑進行搜索的過程，PKI體系中的實體相當于圖的頂點，證書相當于圖中的?。ㄓ深C發者指向被頒發者）。搜索算法動態地從證書存儲庫中獲得候選證書（指向當前頂點的弧）。本文采用的這種深度優先的遞歸算法能夠返回所有存在的路徑。通過對算法進行優化，還能夠排除部分肯定無效的路徑，從而提高所得路徑的健壯性，減輕證書路徑驗證的負擔。本算法基于Openssl庫實現，主要函數如下：

STACK_OF（PATH） * getPath_depthfirst（X509* endCert， X509* anchor， int CurrentDepth）

CurrentDepth即路徑長度，該算法將建立從目標證書endCert到信任錨之間的多條路徑，anchor為信任錨證書。PATH表示一條路徑，其定義為STACK_OF（X509）。所有路徑以棧的形式返回。其調用遞歸函數為：

void certPathbuildNodes（ X509 *currentCert， X509 *anchor， PathNode *previousNode， STACK_OF（PathNode） *endNodes， int CurrentDepth， int MaxDepth）。

PathNode數據結構為：

typedef struct path_node_st PathNode；

struct path_node_st {

X509* referenceCert；

PathNode* previousPathNode； } ；

流程為圖3所示。endNods中存放每條路徑最后一個結點。該遞歸函數執行完成后，其參數endNodes中的PathNode建立完成。PathNode中都具有前向指針previousPathNode，通過這個指針，可以由最后結點向前，從而建立出一個完整的路徑。

由流程圖可以看出，路徑終止原因可能是超過路徑最大長度MaxDepth，某個證書無符合要求的頒發者證書（排除可能形成回路的頒發者證書），或者是已經到達信任錨。如何判斷CurrentCert是否已經到達信任錨是一個難點。參數anchor是信任錨的證書，但并不意味著CurrentCert必須與anchor為同一張證書才表明已到達信任錨。例如anchor是信任錨的CA證書，而CurrentCert為其他CA頒發給信任錨的交叉證書，二張證書雖然不同，但是實際上已經搜索到信任錨了。本算法采用可區分名DN和公鑰相結合的方法解決此問題。如果CurrentCert與anchor只是DN相同，并不能表示二者都為信任錨的證書。很可能CurrentCert只是碰巧和信任錨具有相同DN的實體的證書。所以采用DN加上公鑰進行判斷是最合適的方法。

獲得currentCert的頒發者證書集 lookupCertPool，意思即為獲得當前證書currentCert所簽發出去的所有證書，可以通過SIA擴展項到對應的LDAP目錄中獲得。對lookupCertPool中的證書優化排序后，一部分中間證書被排除，另一部分中間證書將按照優先級別進行排序。iNocrossSubjectFound標志是否已經沒有后續證書了，如果為是則將對應結點放入endNodes棧中。

3.3 證書路徑構建中的優化

認證路徑處理由路徑構建和路徑驗證兩個階段組成[9-11]。并非所有的路徑都能通過驗證。在構建過程中，本算法通過對侯選證書（頒發者證書集）排序來使最有希望的路徑最先被搜索到。給證書排序類似給每個證書一個權值，權值越大優先級越高，當權值很小或者能明確判斷經過該證書的路徑無效，則可直接排除該證書。

（1）基本約束（Basic Constraints）

當證書中含有基本約束擴展項時， 如果CA=FALSE，則排除該證書，因為前向構建中的侯選證書不可能是非CA證書。

（2）簽名算法（Signature Algorithms）

證書中的簽名和公鑰算法是不可識別的則排除該侯選證書，因為證書中的簽名無法處理，證書路徑必定無效；如果侯選證書中的公鑰算法與當前證書簽名算法不匹配，則排除該證書。

（3）密鑰用途（KeyUsage）

當證書中含有密鑰用途擴展時，若沒有包含證書簽名項（keyCertSign）則排除該證書。

（4）證書有效期（Certificate Validity）

如果證書不在有效期內則排除該證書。路徑中如果有某張證書無效，則該路徑必定無效。

（5）路徑長度約束（Length Constraints）

當證書基本約束擴展中的路徑長度約束存在時，如果當前路徑長度（本算法中的CurrentDepth）超過該約束則證書被排除。

（6）名稱約束（Name Constraints）

當證書中包含名稱約束擴展，如果該名稱約束與已經存在于路徑中的證書發生矛盾，則排除該侯選證書。

（7）密鑰標識符的匹配

侯選證書中的主體密鑰標識符SKID（Subject Key Identify）如果與當前證書（本算法中的currentCert）的權威密鑰標識符AKID（Authority Key Identify）匹配，則該證書權值增加一個較大值，如果該侯選證書沒有SKID，則權值增加一個較小值。如果當前證書在AKID中有發行者名和序列號，則與之都匹配的侯選證書權值增加較大值，如果只匹配發行者名，則權值增加較小值。

（8）策略（Policy）處理

證書策略并非只有在反向構建時可以處理，侯選證書若能夠滿足前向策略鏈（Forward Policy Chaining）[4]則該證書權值增加。此外如果侯選證書中的策略與初始可接受策略集合有交集，則權值增加。

（9）可區分名（DN）匹配

證書的頒發者DN與信任錨的主體DN完全匹配的侯選證書權值增加較大值。

（10）相對可區分名（RDN）匹配

證書頒發者DN與信任錨DN間有越多RDN匹配的侯選證書權值增加越大。

證書的主體DN與目標證書發行者DN間有越多RDN匹配的侯選證書權值越大。

（11）證書存儲的目錄屬性

cACertificate，通過該目錄屬性獲得候選證書后，權值增加一較大值，通過crossCertificatePair目錄屬性，獲得候選證書后，權值增加一較小值。這使得證書路徑傾向于在同一個信任域內構建。在相同信任域內，由于距離以及網速使得PKI的操作更加高效。

證書完整性的驗證與撤銷狀態的驗證仍應該屬于證書驗證階段的工作[9]。因為在一個運轉正常的PKI系統中，從證書庫中能夠獲得的證書很少會是已經被撤銷的，而驗證簽名花費的時間較大，所以這兩項在完整的路徑構建完成后再驗證效率更高。

3.4 路徑構建需解決的問題

（1） 死端（Dead Ends）

在非層次模型中，可能會由于“死端”而使得某條路徑構建失敗。以圖4為例。

目標證書為EE，信任錨為CA1。CA1.1有兩張證書，一個是由CA2.1頒發的交叉證書，一個是由信任錨CA1頒發的中介CA證書。路徑構建算法能夠得到路徑EE（CA1.1），CA1.1（CA2.1），CA2.1（CA2），CA2（CA2）。CA2沒有其他實體給其頒發證書，并且CA2并非目標證書信任錨，因此此路徑不完整而且無效。采用本算法，則此例中CA2 的自簽名證書也會生成PathNode結點入endNodes棧。但是本算法規定若endNodes棧中的結點所對應的證書不是信任錨證書，則不再通過該結點的前向指針previousPathNode向前建立完整路徑，該條無效路徑將被放棄。

（2）回路檢測

當信任模型中出現回路時，可能會導致路徑構建算法的死循環。回路檢測不僅僅要判斷同一張證書是否出現兩次，還要檢查相同主體名與主體可選名以及主體公鑰是否都出現了兩次。本文采用certPath_isinPath（STACK_OF（X509） * pathCerts， X509 * cert）函數來判斷是否有回路。首先通過X509_find_by_subject函數來判斷是否找到相同的subjectName，X509_check_private_key （cert， pKey ）再判斷兩個公鑰是否相同，相同則表示路徑有回路。但是由于環境搭建時，可能主題名不同，比如相差一個email，但是事實上可能還是到達了同一個CA，造成了回路，所以還是要通過for循環進行公鑰判斷。

int certPath_isinPath（STACK_OF（X509） * pathCerts， X509 * cert）

{

int i；

X509 *tempCert；

EVP_PKEY *pKey；

tempCert=X509_find_by_subject（pathCerts， X509_get_subject_name（ cert ））；

if （ tempCert ） {

pKey = X509_get_pubkey（ tempCert ）；

if （ X509_check_private_key （cert， pKey ） ）

return 1； }

for （i=0； i

tempCert = sk_X509_value（pathCerts，i）；

if （CmpsubjectaltName（ tempCert，cert） == 0）{

pKey = X509_get_pubkey（ tempCert ）；

if （ X509_check_private_key （cert， pKey ） ）

return 1； }

}

return 0；

}

4 結束語

本文針對日益復雜的PKI信任模型，提出了一種基于深度優先搜索的前向路徑構建算法，并對該算法進行了優化，使得構建出的路徑更加健壯。本算法解決了路徑構建過程中出現的死端和回路問題。對于具有多個信任錨的情況，本算法采用了多進程并行處理的方式。今后可以增加Cache機制，來進一步提高路徑構建的效率。

參考文獻

[1] Yee P. Updates to the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List （CRL） Profile[S].RFC 6818， January 2013.

[2] [美] Andrew Nash.公鑰基礎設施 （PKI） 實現和管理電子安全[M].張玉清，譯.北京： 清華大學出版社，2002： 249-251.

[3] Qinghai Bai. Research on Mechanism of PKI Trust Model： Proc of 2011 IEEE International Conference on Information Theory and Information Security（ICITIS 2011）， 2011[C]. Washington DC： IEEE Computer Society， 2011： 151-153.

[4] Cooper M， Dzambasow Y， Hesse P， Joseph S， Nicholas R. Internet X.509 Public Key Infrastructure： Certification Path Building[S]. RFC 4158， September 2005.

[5] zeilenga K. Lightweight Directory Access Protocol （LDAP） Schema Definitions for X.509 Certificates[S]. RFC4523， June 2006.

[6] Zeilenga K， Lightweight Directory Access Protocol （LDAP） Transactions[S]. RFC5805， March 2010.

[7] http：//www.openldap.org.

[8] http：//www.openssl.org.

[9] Freeman T， Housley R， Malpani A， Cooper D， Polk W. Server-Based Certificate Validation Protocol （SCVP）[S]. RFC5055， December 2007.

[10] 徐蕾，孫尚波.基于嚴格二叉樹的證書路徑構造方法[J]. 計算機應用，2010， 12：107-109.

[11] Fujishiro T， Sato A， Kumagai T， et al. Development of hi-speed X.509 certification path validation system： Proc of the 4th International Conference on Advanced Information Networking and Applications Workshops， 2010[C]. Washington DC： IEEE Computer Society， 2010：269-274.