基于哈希表的RPKI證書驗證優(yōu)化方法①

安春林,馬 迪,王 偉2,,毛 偉2,

1(中國科學院 計算機網(wǎng)絡(luò)信息中心,北京 100190)

2(中國科學院大學,北京 100190)

3(互聯(lián)網(wǎng)域名系統(tǒng)北京市工程研究中心,北京 100190)

RPKI是一種用于保障互聯(lián)網(wǎng)基礎(chǔ)碼號資源(包含IP地址,AS號)安全使用的公鑰基礎(chǔ)設(shè)施[1].通過對X.509公鑰證書進行擴展,RPKI依托資源證書實現(xiàn)了對互聯(lián)網(wǎng)基礎(chǔ)碼號資源使用授權(quán)的認證,并以路由源聲明(Route Origin Authorization,ROA)的形式幫助域間路由系統(tǒng),驗證某個AS針對特定IP地址前綴的路由通告是否合法[2].

RPKI體系可以分為三個組成部件:認證權(quán)威(Certificate Authority,CA)、依賴方(Relying Party,RP)和資料庫(Repository).分別負責簽發(fā)、驗證、存儲各類數(shù)字對象(包括各種簽名對象和證書)來彼此協(xié)作,共同完成RPKI的功能;其中CA簽發(fā)的各類簽名對象分為資源證書(Resource Certificate,RC)、ROAs[3]、Manifests[4]、Ghostbusters[5].資料庫負責收集保存所有的簽名對象,同時當有新的簽名對象被創(chuàng)建時也要上傳到資料庫,以供全球RPs同步下載[6].RP負責從資料庫中同步下載資源證書和簽名對象,并驗證資源證書和簽名對象的有效性,而后將有效的ROA處理成IP地址塊和AS號的真實授權(quán)關(guān)系,用于指導BGP路由.

同時,RP端作為同步和驗證INR分配/授權(quán)關(guān)系與實際BGP路由之前溝通的橋梁,RP的運行效率影響著整個RPKI體系的效率.針對RP同步簽名對象的效率研究,有htsync[7]和Delta協(xié)議[8].目前RPKI體系中的RP在驗證證書的過程中,將已經(jīng)處理過的證書信息保存到數(shù)據(jù)庫中,而后在驗證當前證書的時候,通過循環(huán)查詢數(shù)據(jù)庫來完成當前證書到信任錨點(Trust anchor,TA)的證書鏈的構(gòu)建,并將構(gòu)建好的證書鏈交由OpenSSL處理來完成整個驗證證書的過程[9].因此數(shù)據(jù)庫查詢的操作影響著整個驗證證書過程的效率.

在常用的PKI身份認證中,計算代價由終端用戶負載.如圖1,在訪問https網(wǎng)站的過程中,首先目標網(wǎng)站(https://a.com)會將向CA(如CA1)申請的證書a.cer發(fā)送給終端用戶,然后終端用戶會通過本地保存的CA1.cer(通常由系統(tǒng)內(nèi)置)來驗證a.cer的有效性,以此來驗證目標網(wǎng)站的身份真實性.在此過程中,驗證證書的計算代價由終端用戶(通常是瀏覽器)負擔.

而在RPKI運行機制中,終端用戶為BGP路由器,而為了減輕BGP路由器的負擔,優(yōu)化效率,需要將證書驗證的計算代價轉(zhuǎn)移.如圖2,RPKI將計算代價轉(zhuǎn)移到一個單獨的服務(wù)器(RP服務(wù)器),RP服務(wù)器負責同步資料庫和驗證證書,而終端用戶(BGP路由器)只需要向RP服務(wù)器發(fā)起源驗證請求并根據(jù)RP服務(wù)器返回的驗證結(jié)果更新路由表即可,有效的減輕了BGP路由器的負擔.

圖1 https驗證過程

圖2 RPKI運行機制

基于這種特點,結(jié)合“空間換時間”的思想,針對RP服務(wù)器在構(gòu)建證書鏈是效率不足的問題,本文設(shè)計并實現(xiàn)了一種基于哈希表的RPKI證書驗證優(yōu)化方法.通過將證書的主體標識(subject)和簽發(fā)人標識(issuer)當作一個鍵值對(key-value)保存到哈希表中,來實現(xiàn)時間復雜度為O(1)的查詢操作.本文基于上述的原理,設(shè)計實現(xiàn)了構(gòu)建證書鏈的程序,并設(shè)計實驗對比基于數(shù)據(jù)庫查詢和基于哈希表的性能.實驗結(jié)果表明,與基于數(shù)據(jù)庫查詢的方法相比,基于哈希表的方法耗時更短,在當前RPKI部署環(huán)境下,3種實驗場景中,平均時間加速比分別為99.03%、98.45%和97.48%,有效的減少了構(gòu)建證書鏈的時間消耗.

1 背景

1.1 基于數(shù)據(jù)庫查詢的原理

現(xiàn)有RP端的實現(xiàn)(Relying Party Security Technology for Internet Routing,RPSTIR)中,構(gòu)建證書鏈采用的策略為數(shù)據(jù)庫查詢,假設(shè)當前待驗證證書A的主體標識為A.subject、簽發(fā)人標識為A.issuer、待驗證證書鏈CTX,具體的過程如算法1.

?

上述過程為向上構(gòu)建證書鏈并驗證自身的過程.

但是,在驗證證書的過程中,證書加載的順序并非是嚴格的由上而下進行,因此在完成向上構(gòu)建證書鏈并完成驗證有效之后還需要向下構(gòu)建證書鏈并驗證.過程與向上構(gòu)建證書鏈類似,假設(shè)當前驗證為有效的證書為A,具體過程如算法2.

1.2 基于數(shù)據(jù)庫查詢方法的弊端

數(shù)據(jù)庫是為了方便用戶或系統(tǒng)對數(shù)據(jù)進行存儲和管理,但在構(gòu)建證書鏈的過程中需要頻繁的涉及到數(shù)據(jù)的查詢,并且還需要對前一次的查詢結(jié)果進行遞歸查詢.而在這種情況下,數(shù)據(jù)庫查詢效率的弊端就會更加凸顯出來.

截止2017年05月,RPKI全球部署率僅僅7.36%(如圖3),證書文件總量19897個 (.cer文件,包括ROA等簽名對象中的EE證書).

整個RPKI證書體系又可以看作5個(5個RIR的TA證書為根)N叉樹,而經(jīng)過對數(shù)據(jù)庫中數(shù)據(jù)的分析,發(fā)現(xiàn)66.25%左右的證書處于整個證書樹的第3層(假設(shè)根為第0層),32.81%左右的證書處于證書樹的第2層.基于數(shù)據(jù)庫查詢的方法構(gòu)建證書鏈的原理是通過循環(huán)遍歷逐個向上查詢父證書,直到找到TA證書,因此整個RPKI體系中構(gòu)建證書鏈過程的時間復雜度可以近似為O(n4).如果RPKI在全球廣泛部署(部署率超過80%),則整個RPKI體系中證書文件量預計將會超過26萬個,此時構(gòu)建證書鏈的時間將會急劇增大,將會影響整個RP服務(wù)器運行的效率.

圖3 RPKI全球部署情況

由此可以看出,由于證書驗證過程的特殊性(需要逐層遞歸查詢),數(shù)據(jù)庫查詢的方法并不完全適合RPKI體系.

同時,RPKI機制中的RP服務(wù)器相對于使用PKI的瀏覽器有更高的性能,因此可以使用犧牲空間換時間的方式優(yōu)化構(gòu)建證書鏈的過程.根據(jù)上述的原理,本文實現(xiàn)了一個基于哈希表的RPKI證書驗證優(yōu)化方法.

2 基于哈希表的證書鏈構(gòu)造方法

哈希表是一種根據(jù)“鍵”來直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu).也就是說,它通過計算一個關(guān)于鍵值的函數(shù),將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄,這加快了查找速度.這個映射函數(shù)稱為散列函數(shù),存放記錄的數(shù)組稱作哈希表.

而在本文中,實驗是基于Python實現(xiàn)的,使用的數(shù)據(jù)結(jié)構(gòu)即為Python中的哈希表—字典(Dictionary).

字典是Python中最常用的數(shù)據(jù)類型之一,它是一個鍵值對的集合,字典通過“鍵”來索引,關(guān)聯(lián)到相對的值,理論上它的查詢復雜度是O(1).因此,本文實現(xiàn)的基于哈希表的證書鏈構(gòu)造方法將會大大的減少耗時,從而顯著的提高RP的效率.

2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計

在實際應(yīng)用場景下,數(shù)據(jù)結(jié)構(gòu)應(yīng)該包含證書的所有信息,并增加一個區(qū)別證書有效性的字段.在證書驗證的過程中逐層的向上查找待驗證證書的“有效父證書”,構(gòu)建一個完整的證書鏈,然后調(diào)用OpenSSL驗證構(gòu)建的證書鏈的有效性.當驗證為有效后,遞歸查找所有“待驗證子證書”,并驗證其有效性.

由于本文主要針對構(gòu)建證書鏈的過程的優(yōu)化,所以為了排除調(diào)用OpenSSL驗證證書鏈的時間消耗以及其他的干擾項,特將證書驗證的過程簡化為逐層向上查找“父證書”而非“有效父證書”,直到查找到TA或者找不到“父證書”,然后遞歸查找所有“子證書”而非“待驗證子證書”,直到查找失敗.也即盡可能的向上查找父證書和向下查找子證書,忽略證書的有效性和調(diào)用OpenSSL驗證證書鏈的過程.

因此,數(shù)據(jù)結(jié)構(gòu)中只需要保存構(gòu)建證書鏈需要的信息,即證書的主題標識subject和簽發(fā)人標識issuer.而查找父證書和子證書的方法與基于數(shù)據(jù)庫查詢的方法相同.

考慮到驗證證書不僅需要完成向上構(gòu)建證書鏈的過程,還需要完成向下構(gòu)建證書鏈,因此本文設(shè)計實現(xiàn)了兩個數(shù)據(jù)結(jié)構(gòu):chain_up和chain_down,分別用于向上和向下構(gòu)建證書鏈.

chain_up用來保存向上構(gòu)建證書鏈需要用到的信息.向上構(gòu)建證書鏈即為查找一條滿足B.subject=A.issuer條件的記錄(A為待驗證證書),因此chain_up中的每條記錄的“鍵”為每個證書的主體標識subject,“值”為對應(yīng)證書的簽發(fā)人標識issuer.且由于每個證書的主體標識具有唯一性,因此chain_up數(shù)據(jù)結(jié)構(gòu)中不存在“鍵”沖突的情況.

chain_down用來保存向下構(gòu)建證書鏈需要用到的信息.向下構(gòu)建證書鏈即為查找每一個滿足B.issuer=A.subject條件的記錄(A為待驗證證書),因此chain_down中每條記錄的“鍵”為每個證書的簽發(fā)人標識issuer.而由于父證書與子證書的對應(yīng)關(guān)系為1:N,所以存在一個“鍵”(issuer)對應(yīng)多個“值”(subject)的情況,所以“值”應(yīng)該為所有簽發(fā)人標識issuer等于“鍵”的所有證書的主體標識subject的數(shù)組集合.

假設(shè)證書結(jié)構(gòu)如圖4所示.

根據(jù)前文的描述,chain_up應(yīng)該如下所示:

{"A":"A","B":"A","C":"A","D":"B","E":"C","F":"C","G":"C"}

chain_down應(yīng)該如下所示:

{"A":["A","B","C"],"B":["D"],"C":["E","F","G"]}

圖4 證書結(jié)構(gòu)

2.2 向上構(gòu)建證書鏈

為了排除其他實驗項對結(jié)論的影響,本文實驗僅涉及證書鏈的構(gòu)建,并不對證書鏈進行有效性驗證.因此向上構(gòu)建證書鏈的算法只進行逐層查找父證書的功能.

基于哈希表的向上構(gòu)建證書鏈算法如算法3.

算法3.哈希表向上構(gòu)建證書鏈輸入:RPKI資料庫證書文件A,chain_up文件(Json格式)1.令變量subject=A.subject,issuer=A.issuer.2.若subject=issuer,說明已經(jīng)逐層向上找到根節(jié)點,即TA證書,跳轉(zhuǎn)第6步;若subject!=issuer,繼續(xù)第3步.3.令subject=issuer,issuer=chain_up[issuer].4.若第3步出現(xiàn)錯誤:KeyError,說明在進行chain_up[issuer]時出錯,表明當前字典chain_up中沒有“鍵”=issuer的數(shù)據(jù),跳轉(zhuǎn)第6步.5.若第3步?jīng)]有錯誤出現(xiàn),以在第3步中重新賦值的subject和issuer跳轉(zhuǎn)第2步.6.向字典chain_up中插入新數(shù)據(jù)chain_up[A.subject]=A.issuer;結(jié)束.

在程序的初始情況下,字典chain_up應(yīng)該為空,隨著程序的不斷執(zhí)行,在程序?qū)⑺械腞PKI資料庫中的證書文件全部遍歷完全之后,chain_up應(yīng)該包含每一個RPKI資料庫證書的主體標識和簽發(fā)人標識.

由于Json文件的特性(鍵值對),且Python對Json文件的解析結(jié)果即為Python中的字典,因此在程序退出之前,應(yīng)該將最終的chain_up保存成Json文件,以供下一次使用.

2.3 向下構(gòu)建證書鏈

與向上構(gòu)建證書鏈類似,向下構(gòu)建證書鏈的算法也只實現(xiàn)循環(huán)遍歷所有子證書的功能.

基于哈希表的向下構(gòu)建證書鏈算法如算法4.

算法4.哈希表向下構(gòu)建證書鏈輸入:RPKI資料庫證書文件A,chain_down文件(Json格式存儲)1.令變量subject=A.subject,issuer=A.issuer.2.令臨時變量subject_arrary=chain_down[subject],issuer=subject.3.若第2步出現(xiàn)錯誤:KeyError,說明在進行chain_down[subject]時出錯,表示當前字典chain_down中沒有“鍵”=subject的數(shù)據(jù),跳轉(zhuǎn)至第6步.

與向上構(gòu)建證書鏈類似,字典chain_down在初始情況下應(yīng)該為空,隨著程序的不斷進行而不斷的填充數(shù)據(jù).在程序完成所有RPKI資料庫中證書文件的遍歷之后,chain_down應(yīng)該包含所有位于證書樹中的非葉子節(jié)點的證書的主體標識和對應(yīng)的所有子證書的主體標識.

同樣,在程序退出之前應(yīng)該將字典chain_down保存成Json文件.

總的來說,本文實驗分為兩大步驟:使用基于數(shù)據(jù)庫查詢的方法實現(xiàn)類似算法3和算法4的構(gòu)建證書鏈方法;使用基于哈希表的方法構(gòu)建證書鏈.

在基于數(shù)據(jù)庫查詢的方法中,首先遍歷整個RPKI資料庫,并過濾出所有的證書文件.然后對每一個證書文件,使用 Python中的 OpenSSL庫pyOpenSSL解析文件,并提取出證書文件的主體標識A.subject和簽發(fā)人標識A.issuer.接著查詢數(shù)據(jù)庫中滿足條件B.subject=A.issuer的記錄,并遞歸查詢,完成向上構(gòu)建證書鏈的過程.然后查詢數(shù)據(jù)庫中滿足條件B.issuer=A.subject的所有子證書,并遞歸的對每一個子證書執(zhí)行向下構(gòu)建證書鏈的過程.

在基于哈希表的方法中,同樣先遍歷整個RPKI資料庫,并過濾出所有證書文件,對每一個證書完成向上和向下構(gòu)建證書鏈的過程.

假設(shè)RPKI資料庫中證書文件的個數(shù)為N,且證書樹的結(jié)構(gòu)與當下情況類似,如圖5.

證書最深層數(shù)為5,且有66.25%的證書處于證書樹的第3層(圖5中TA為1層).那么,構(gòu)建證書鏈的時間復雜度為:

N*(O(向上構(gòu)建)+O(向下構(gòu)建))

由于基于數(shù)據(jù)庫查詢的方法,每一次查找父證書或查找子證書都相當于遍歷一次數(shù)據(jù)庫表,因此基于數(shù)據(jù)庫查詢的方法復雜度就近似為O(N*(N3+N2)),也即O(N4).而基于哈希表的方法,對于每一個查詢操作的復雜度在最優(yōu)情況下(所有的“鍵”的散列值均不同)為O(1),最差的情況下(所有的“鍵”的散列值都相同)為O(N).因此基于哈希表的方法,在最優(yōu)情況下的復雜度為O(N),最差情況下與基于數(shù)據(jù)庫查詢的方法相同,為O(N4).

圖5 RPKI證書結(jié)構(gòu)

3 實驗分析

3.1 實驗設(shè)計

RP服務(wù)器在驗證RPKI資料庫中證書文件時,可能存在三種場景:初始驗證、增量驗證和無更改驗證.

初始驗證:RP服務(wù)器在收到RPKI資料庫之后從無到有的驗證每一個證書;

增量驗證:RP服務(wù)器已經(jīng)完成RPKI資料庫中的證書的驗證,此次驗證時RPKI資料庫有新的證書文件;

無更改驗證:RPKI資料庫沒有任何變化,重新完成一遍驗證過程.

當RP服務(wù)器第一次啟動時,RP服務(wù)器沒有任何RPKI資料庫文件,因此會發(fā)生“初始驗證”,此時RP服務(wù)器的數(shù)據(jù)庫中也沒有任何數(shù)據(jù),哈希表chain_up和chain_down也為空,需要下載RPKI資料庫并完成驗證;當RPKI資料庫中有新的證書文件時,RP服務(wù)器將會進行“增量驗證”,遍歷新的RPKI資料庫,對新的證書文件進行驗證;當RPKI資料庫沒有任何變動的時候,RP服務(wù)器將會進行“無更改驗證”,此時RP服務(wù)器將會遍歷RPKI資料庫,并檢查每一個證書是否已經(jīng)被記錄到數(shù)據(jù)庫或chain_up和chain_down中.

根據(jù)以上三種情況設(shè)計實驗對比基于數(shù)據(jù)庫查詢和基于哈希表的時間消耗.實驗環(huán)境如表1所示.實驗數(shù)據(jù)來自全球RPKI資料庫,實驗數(shù)據(jù)截止到2017年5月9日,共19 897個證書文件.

表1 實驗環(huán)境

3.2 實驗結(jié)果

3.2.1 初始驗證

設(shè)定RPKI資料庫大小分別為2000、5000、8000、11 000、14 000、17 000、19 897個證書文件.7種環(huán)境下的RP服務(wù)器中的已驗證證書個數(shù)均為0.基于數(shù)據(jù)庫查詢(Database)和基于哈希表(Hash)的性能對比如表2所示.

表2 初始驗證性能對比

可以看出,基于哈希表的方法在時間上明顯更少,且隨著證書文件個數(shù)的增多,時間加速比呈線性增大,也即證書文件越多,基于哈希表的方法就相對越有效.7種環(huán)境下的平均時間加速比為99.03%.

3.2.2 增量驗證

設(shè)定RP服務(wù)器已驗證的證書個數(shù)分別為2000、5000、8000、11 000、14 000、17 000 個,在增量驗證的實驗中,RPKI資料庫發(fā)生更新,有新的證書文件,增量均為3000個(17000個文件的初始環(huán)境下的增量為2897個).基于數(shù)據(jù)庫查詢和基于哈希表的性能對比如表3所示.

表3 增量驗證性能對比

可以看出,基于哈希表的方法仍然優(yōu)于基于數(shù)據(jù)庫查詢的方法,6種環(huán)境下的平均時間加速比為98.45%.

3.2.3 無更改驗證

設(shè)定RP服務(wù)器的資料庫證書個數(shù)分別為2000、5000、8000、11 000、14 000、17 000和 19 897 個時,RPKI資料庫未發(fā)生變化,RP服務(wù)器此時進行無更改驗證,僅需要對資料庫中的每一個證書文件進行一次查詢是否存在于數(shù)據(jù)庫或chain_up和chain_down中即可.兩種方法的性能對比如表4所示.

表4 無更改驗證性能對比

可以看出,基于哈希表的方法仍優(yōu)于基于數(shù)據(jù)庫查詢的方法,且加速比有隨著文件個數(shù)增大而增大的趨勢.7種環(huán)境下的平均時間加速比為97.48%.

4 結(jié)語

針對RPKI中RP服務(wù)器使用基于數(shù)據(jù)庫查詢的方法進行證書鏈構(gòu)建時效率低下的問題,本文結(jié)合了RPKI運行機制中將計算代價轉(zhuǎn)移至RP服務(wù)器的特點和“空間換時間”的思想,設(shè)計實現(xiàn)了一種基于哈希表的RPKI證書驗證優(yōu)化方法,有效的提升RP服務(wù)器在驗證證書時的性能.實驗結(jié)果表明,與基于數(shù)據(jù)庫查詢的方法相比,基于哈希表的方法在構(gòu)建證書鏈時效率顯著提升,在設(shè)計的3種實驗場景下,平均時間加速比分別為99.03%、98.45%和97.48%,有效的減少了驗證證書的時間消耗.

1Phokeer AD.Interdomain routing security:Motivation and challenges of RPKI.Timss Technical Report RHUL-MA-2014-14,Egham,UK:Royal Holloway,University of London,2014.

2馬迪.RPKI概覽.電信網(wǎng)技術(shù),2012,(9):30-33.

3Lepinski M,Kent S,Kong D.RFC 6482:A profile for route origin authorizations (ROAs).IETF,2012.

4Austein R,Huston G,Kent S,et al.RFC 6486:Manifests for the resource public key infrastructure (RPKI).IETF,2012.

5Bush R.RFC 6493:The resource public key infrastructure(RPKI)ghostbusters record.IETF,2012.

6Huston G,Loomans R,Michaelson G.RFC 6481:A profile for resource certificate repository structure.IETF,2012.

7許圣明,馬迪,毛偉,等.基于有序哈希樹的RPKI資料庫數(shù)據(jù)同步方法.計算機系統(tǒng)應(yīng)用,2016,25(6):141-146.[doi:10.15888/j.cnki.csa.005203]

8Bruijnzeels T,Muravskiy O,Weber B,et al.Draft-ietf-sidrdelta-protocol,2014.

9Reynolds MC,Kent S.A high performance software architecture for a secure internet routing PKI.Proceedings of Cybersecurity Applications &Technology Conference for Homeland Security.Washington,DC,USA.2009.49-53.