基于哈希表的RPKI證書驗證優化方法①

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

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

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

3(互聯網域名系統北京市工程研究中心,北京 100190)

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

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

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

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

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

圖1 https驗證過程

圖2 RPKI運行機制

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

1 背景

1.1 基于數據庫查詢的原理

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

?

上述過程為向上構建證書鏈并驗證自身的過程.

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

1.2 基于數據庫查詢方法的弊端

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

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

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

圖3 RPKI全球部署情況

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

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

2 基于哈希表的證書鏈構造方法

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

而在本文中,實驗是基于Python實現的,使用的數據結構即為Python中的哈希表—字典(Dictionary).

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

2.1 數據結構設計

在實際應用場景下,數據結構應該包含證書的所有信息,并增加一個區別證書有效性的字段.在證書驗證的過程中逐層的向上查找待驗證證書的“有效父證書”,構建一個完整的證書鏈,然后調用OpenSSL驗證構建的證書鏈的有效性.當驗證為有效后,遞歸查找所有“待驗證子證書”,并驗證其有效性.

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

因此,數據結構中只需要保存構建證書鏈需要的信息,即證書的主題標識subject和簽發人標識issuer.而查找父證書和子證書的方法與基于數據庫查詢的方法相同.

考慮到驗證證書不僅需要完成向上構建證書鏈的過程,還需要完成向下構建證書鏈,因此本文設計實現了兩個數據結構:chain_up和chain_down,分別用于向上和向下構建證書鏈.

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

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

假設證書結構如圖4所示.

根據前文的描述,chain_up應該如下所示:

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

chain_down應該如下所示:

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

圖4 證書結構

2.2 向上構建證書鏈

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

基于哈希表的向上構建證書鏈算法如算法3.

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

在程序的初始情況下,字典chain_up應該為空,隨著程序的不斷執行,在程序將所有的RPKI資料庫中的證書文件全部遍歷完全之后,chain_up應該包含每一個RPKI資料庫證書的主體標識和簽發人標識.

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

2.3 向下構建證書鏈

與向上構建證書鏈類似,向下構建證書鏈的算法也只實現循環遍歷所有子證書的功能.

基于哈希表的向下構建證書鏈算法如算法4.

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

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

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

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

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

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

假設RPKI資料庫中證書文件的個數為N,且證書樹的結構與當下情況類似,如圖5.

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

N*(O(向上構建)+O(向下構建))

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

圖5 RPKI證書結構

3 實驗分析

3.1 實驗設計

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

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

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

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

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

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

表1 實驗環境

3.2 實驗結果

3.2.1 初始驗證

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

表2 初始驗證性能對比

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

3.2.2 增量驗證

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

表3 增量驗證性能對比

可以看出,基于哈希表的方法仍然優于基于數據庫查詢的方法,6種環境下的平均時間加速比為98.45%.

3.2.3 無更改驗證

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

表4 無更改驗證性能對比

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

4 結語

針對RPKI中RP服務器使用基于數據庫查詢的方法進行證書鏈構建時效率低下的問題,本文結合了RPKI運行機制中將計算代價轉移至RP服務器的特點和“空間換時間”的思想,設計實現了一種基于哈希表的RPKI證書驗證優化方法,有效的提升RP服務器在驗證證書時的性能.實驗結果表明,與基于數據庫查詢的方法相比,基于哈希表的方法在構建證書鏈時效率顯著提升,在設計的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概覽.電信網技術,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資料庫數據同步方法.計算機系統應用,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.