深度優(yōu)先搜索構(gòu)建證書路徑的算法研究

劉艷

摘 要：隨著互聯(lián)網(wǎng)的發(fā)展，PKI結(jié)構(gòu)日益復(fù)雜。論文分析了目前存在的幾種典型的PKI信任模型，并設(shè)計了一種基于深度優(yōu)先的遞歸算法來構(gòu)建證書路徑，描述了詳細(xì)的算法流程。最后對該算法進(jìn)行了優(yōu)化，使其能提前排除無效路徑，減輕路徑驗證的負(fù)擔(dān)。

關(guān)鍵詞：PKI；信任模型；證書路徑構(gòu)建；LDAP

中圖分類號：TP309 文獻(xiàn)標(biāo)識碼：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 引言

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

2 PKI信任模型

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

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

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

（3）網(wǎng)狀模型。該模型雖然以對等模型為基礎(chǔ)，但對等模型有直接交叉認(rèn)證的一種限制，而該模型信任具有傳遞性，具有較好的擴展性。該種模型中的路徑構(gòu)建比較復(fù)雜，涉及到多個CA之間的交叉認(rèn)證。

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

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

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

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

3 證書路徑的構(gòu)建

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

3.1 侯選證書的獲取

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

Openssl函數(shù)庫[8]以及OpenLdap函數(shù)庫提供了很多底層函數(shù)，以下其中兩個關(guān)鍵函數(shù)：

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函數(shù)通過給定的參數(shù)nid從證書擴展中對其進(jìn)行定位，函數(shù)X509_get_ext通過定位loc，獲得該擴展。當(dāng)想要獲得AIA擴展時，參數(shù)nid為NID_info_access，當(dāng)想要獲得SIA擴展時，參數(shù)nid為NID_sinfo_access。

3.2 路徑構(gòu)建算法

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

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

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

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

PathNode數(shù)據(jù)結(jié)構(gòu)為：

typedef struct path_node_st PathNode；

struct path_node_st {

X509* referenceCert；

PathNode* previousPathNode； } ；

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

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

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

3.3 證書路徑構(gòu)建中的優(yōu)化

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

（1）基本約束（Basic Constraints）

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

（2）簽名算法（Signature Algorithms）

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

（3）密鑰用途（KeyUsage）

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

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

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

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

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

（6）名稱約束（Name Constraints）

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

（7）密鑰標(biāo)識符的匹配

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

（8）策略（Policy）處理

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

（9）可區(qū)分名（DN）匹配

證書的頒發(fā)者DN與信任錨的主體DN完全匹配的侯選證書權(quán)值增加較大值。

（10）相對可區(qū)分名（RDN）匹配

證書頒發(fā)者DN與信任錨DN間有越多RDN匹配的侯選證書權(quán)值增加越大。

證書的主體DN與目標(biāo)證書發(fā)行者DN間有越多RDN匹配的侯選證書權(quán)值越大。

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

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

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

3.4 路徑構(gòu)建需解決的問題

（1） 死端（Dead Ends）

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

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

（2）回路檢測

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

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 結(jié)束語

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

參考文獻(xiàn)

[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.公鑰基礎(chǔ)設(shè)施 （PKI） 實現(xiàn)和管理電子安全[M].張玉清，譯.北京： 清華大學(xué)出版社，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] 徐蕾，孫尚波.基于嚴(yán)格二叉樹的證書路徑構(gòu)造方法[J]. 計算機應(yīng)用，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.