劉艷

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

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

中圖分類(lèi)號(hào)：TP309 文獻(xiàn)標(biāo)識(shí)碼：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上種種安全問(wèn)題的框架和遵循既定標(biāo)準(zhǔn)的密鑰管理平臺(tái)，它已經(jīng)成為信息安全技術(shù)的核心和關(guān)鍵技術(shù)。由于互聯(lián)網(wǎng)不斷發(fā)展，PKI信任域互操作性有著越來(lái)越強(qiáng)的需求，信任模型越來(lái)越復(fù)雜。在復(fù)雜的信任模型下，不同信任域的實(shí)體間需要進(jìn)行交叉認(rèn)證，包含交叉證書(shū)的證書(shū)路徑的跨信任域構(gòu)建問(wèn)題成為難題之一。本文提出了一種基于深度優(yōu)先的遞歸算法來(lái)構(gòu)建證書(shū)路徑，并對(duì)構(gòu)建過(guò)程進(jìn)行優(yōu)化，提高證書(shū)驗(yàn)證的效率。

2 PKI信任模型

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

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

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

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

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

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

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

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

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

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

3.1 侯選證書(shū)的獲取

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

Openssl函數(shù)庫(kù)[8]以及OpenLdap函數(shù)庫(kù)提供了很多底層函數(shù)，以下其中兩個(gè)關(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ù)通過(guò)給定的參數(shù)nid從證書(shū)擴(kuò)展中對(duì)其進(jìn)行定位，函數(shù)X509_get_ext通過(guò)定位loc，獲得該擴(kuò)展。當(dāng)想要獲得AIA擴(kuò)展時(shí)，參數(shù)nid為NID_info_access，當(dāng)想要獲得SIA擴(kuò)展時(shí)，參數(shù)nid為NID_sinfo_access。

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

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

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

CurrentDepth即路徑長(zhǎng)度，該算法將建立從目標(biāo)證書(shū)endCert到信任錨之間的多條路徑，anchor為信任錨證書(shū)。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中存放每條路徑最后一個(gè)結(jié)點(diǎn)。該遞歸函數(shù)執(zhí)行完成后，其參數(shù)endNodes中的PathNode建立完成。PathNode中都具有前向指針previousPathNode，通過(guò)這個(gè)指針，可以由最后結(jié)點(diǎn)向前，從而建立出一個(gè)完整的路徑。

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

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

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

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

（1）基本約束（Basic Constraints）

當(dāng)證書(shū)中含有基本約束擴(kuò)展項(xiàng)時(shí)， 如果CA=FALSE，則排除該證書(shū)，因?yàn)榍跋驑?gòu)建中的侯選證書(shū)不可能是非CA證書(shū)。

（2）簽名算法（Signature Algorithms）

證書(shū)中的簽名和公鑰算法是不可識(shí)別的則排除該侯選證書(shū)，因?yàn)樽C書(shū)中的簽名無(wú)法處理，證書(shū)路徑必定無(wú)效；如果侯選證書(shū)中的公鑰算法與當(dāng)前證書(shū)簽名算法不匹配，則排除該證書(shū)。

（3）密鑰用途（KeyUsage）

當(dāng)證書(shū)中含有密鑰用途擴(kuò)展時(shí)，若沒(méi)有包含證書(shū)簽名項(xiàng)（keyCertSign）則排除該證書(shū)。

（4）證書(shū)有效期（Certificate Validity）

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

（5）路徑長(zhǎng)度約束（Length Constraints）

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

（6）名稱(chēng)約束（Name Constraints）

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

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

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

（8）策略（Policy）處理

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

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

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

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

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

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

（11）證書(shū)存儲(chǔ)的目錄屬性

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

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

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

（1） 死端（Dead Ends）

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

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

（2）回路檢測(cè)

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

本文針對(duì)日益復(fù)雜的PKI信任模型，提出了一種基于深度優(yōu)先搜索的前向路徑構(gòu)建算法，并對(duì)該算法進(jìn)行了優(yōu)化，使得構(gòu)建出的路徑更加健壯。本算法解決了路徑構(gòu)建過(guò)程中出現(xiàn)的死端和回路問(wèn)題。對(duì)于具有多個(gè)信任錨的情況，本算法采用了多進(jìn)程并行處理的方式。今后可以增加Cache機(jī)制，來(lái)進(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） 實(shí)現(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)格二叉樹(shù)的證書(shū)路徑構(gòu)造方法[J]. 計(jì)算機(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.