基于哈希表的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.