基于SPKI/SDSI证书链搜索算法与访问控制模型设计

赵晔晖

(宁夏银川河东机场民航宁夏空管分局气象台,宁夏银川750009)

1 研究内容和意义

为解决传统PKI存在的缺陷问题,麻省理工学院(MIT)的教授Butler Lampson、J.C.Mitchell[1-2]、Ronald Rivest[3-4]等在1996年提出“简单分布式安全基础设施(Simple Distributed Security Infrastructure,SDSI)”的概念。然而SPKI/SDSI也存在缺陷:只限于理论上,并没有一个成熟的系统[5-6];SPKI/SDSI最关键的是证书链搜索[7-8]算法,目前存在的证书链搜索算法复杂度高,难以应用于实践。

针对上述情况,主要工作如下:

(1)设计一个分布式访问控制模型:借鉴操作系统中缓存和同步的思想,设计出一个基于SPKI/SDSI证书的分布式访问控制模型,并给出了模型工作的具体流程图。

(2)改进了SPKI/SDSI系统中证书链搜索算法。仔细研究了目前各种SPKI/SDSI证书链搜索算法,分析各种算法优缺点,设计一个高效的证书链改进算法。

(3)对改进的证书链搜索算法进行测试。通过实验数据详细分析了影响证书链搜索效率的参数,最后得出实验结论,证实了改进算法证书规模越大算法优势越明显的推断。

2 基于认证的访问控制模型的设计与实现

2.1 访问控制模型设计思路

以SPKI/SDSI分布式系统为基础进行访问控制,必须考虑证书链的搜索问题。在海量证书库中进行证书链的搜索是一件非常耗费资源的事情,目前对证书链搜索的处理主要有两种方式:

(1)在资源服务器端进行证书链的搜索[9]。采用这种方式时,大量证书的更新、访问会影响服务器的性能,会导致服务器的阻塞;而且,证书链的搜索是非常耗费资源的,在服务器上进行搜索证书无疑进一步加重服务器的负担。

(2)在客户端进行证书链的搜索。采用这种方式,使证书库管理不便,证书库分散存放到客户端。难以对证书进行更新,会造成多个客户端证书库不统一的现象。

基于上述两种设计方式的优缺点,访问控制模型设计策略是:

(1)服务器端设计

分解资源服务器功能,将传统的资源服务器按照功能分解成资源控制服务器、在线验证服务器、证书管理服务器3部分。

(2)客户端设计

设计思想:采用计算机内存管理中cache缓存思想,在客户端构建一个规模较小的证书库,里面存储的证书只与当地客户端访问的资源有关,搜索任务可以不必由证书管理服务器做,减轻了服务器的负担,有利于系统整体性能的提高。模型设计如图1所示。

图1 访问控制模型

2.2 模型工作流程

模型主要有以下几部分组成:资源控制服务器、在线验证服务器、证书管理服务器、本地证书库、服务器证书库、授权实体、访问控制列表(ACL)等。

资源控制服务器主要功能是采用相关控制策略,审核验证访问者的合法权限,限制访问者的具体相关操作权限,保证资源的受控和合法使用。

证书管理服务器主要任务是:管理证书库,将颁发的证书存放到证书库中;进行证书链的搜索。在线验证服务器,主要是验证证书是否有效,其中设置一在线验证进程,若在资源管理服务器中有证书在线测试申请,调用该进程进行在线测试,并返回给资源控制器相关信息。

客户端,主要指发出访问请求的用户的集合,在客户端采用内存管理中的缓存思想,设置一个较小的证书库,保存与本客户端访问相关的证书。

具体来说,一个用户访问资源的过程有以下几步:

(1)首先客户端发出访问申请,访问资源控制服务器,并与之建立连接:客户端在本地证书库中进行证书链的查找,根据查找的结果向资源控制服务器发送不同的访问请求:若在本地证书库中找到一条证书链,则直接用自己的私钥签名,向资源服务器发出资源的访问请求;若在本地证书库中查找不到证书链,则向资源控制发送访问请求,请求信息要求证书管理服务器搜索证书链,资源控制服务器将该请求信息发送给证书管理服务器。

(2)收到客户端的访问请求后,资源控制服务器根据客户端用户请求信息的不同执行不同的进程:若客户端用户请求信息中不包含证书链,此时资源控制服务器向证书控制管理器发出证书链搜索申请,在服务器证书库中进行证书链的搜索;若客户端用户请求信息中包含一条证书链,资源控制服务器首先验证审核证书链的合法性,验证通过后,允许客户端发出的访问请求,若客户端验证非法,则返回拒绝信息。在进行证书链的验证时,若要求在线测试,则将证书链提交给在线验证服务器,进行验证。在线验证服务器,返回验证的相关信息(合法或者非法)给资源控制服务器。

(3)证书管理服务器在收到证书资源控制器发出的证书链搜索请求后,在服务器证书库中进行证书链的搜索,若搜索到证书链,则将该证书链返回给资源控制服务器,然后在资源控制服务器上进行合法性验证;若找不到证书链,返回找不到信息给资源控制服务器。

(4)证书管理服务器将证书链的搜索结果返回给资源控制服务器,如果通过验证,则允许客户端用户执行相应的服务请求,并将证书链返回给客户端,保存在本地证书库中,否则返回给客户端一条拒绝信息。

按照上述4个步骤,客户端访问资源的具体执行流程如图2所示。

图2 模型执行流

3 基于认证的SPKI/SDSI证书链搜索算法

3.1 相关证书链算法

MIT的Clarke D和Elian J对SPKI/SDSI做了大量的研究,针对SPKI/SDSI系统提出算法框架,算法中假定证书存放在用户中,算法的目的是找到一条从ACL(访问控制列表中)授权源到用户申请者公钥之间的证书链。若能通过证书规约找到如下形式的证书链:K∈G(Y)[1]→…→KA(G(Y)表示资源Y的公钥集合),则查找成功。设计出了如下的算法框架:

(1)在证书集合Ccert中验证证书的有效性,去掉那些无效的证书。其中无效证书是指没通过验证的证书、超过有效期内的证书

把证书集合Ccert中的名字证书进行规约,计算名字闭包,将所有的授权证书中都转化成如下的形式:K[1]→KA[z](z=1或者 z=0)

(2)在证书闭包集合Ccert#中,收集对象是单个公钥的授权证书,去掉其他的证书,收集完后,证书闭包集合Ccert#中所有的授权证书只有如下的形式:

KA[1]→KB[z](z=1或者 z=0)

(3)将第(2)步得到的授权证书,建立一个授权有向图。

(4)授权证书图中,运用深度优先搜索算法,查找证书链判断是否存在一条从请求者到资源拥有者之间的证书链路径,若是存在返回成功,否则返回失败。

假定在一个证书集C中有N张证书,证书中最长的扩展名长度为 L。初始名字闭包中最多有 O(N2L)张证书,每一张名字证书做多只能匹配O(N)张证书,在没有进行深度优先搜索算法之间,仅仅名字闭包规约算法复杂度为O(N3L)

3.2 改进的证书链算法

正常情况下,当一个客户端用自己的私钥签名去申请访问某项服务时,只需要将证书库中涉及的某几个证书(授权证书或者名字证书)进行规约合并,形成一条证书链,而不必全部访问,因此在设计算法时,只考虑证书链上与访问请求相关的证书。

在ACL(Access Control List)访问控制列表中,授权证书用如下形式表示:Self[1]→KA[z](Self[1]→KA Classmates[z]),授权证书存放在KA处。

假设某一实体关于资源Y的授权证书公钥KA或者名字存放ACL处,另一实体的公钥KB申请关于资源Y的访问请求。

算法总体框架:

(1)在哈希表中定位到Hash(KB),在链表中查找是否存在KA,若存在直接返回(1),否则执行步骤(2);

(2)找到某一实体KA的所有名字证书和授权证书;

(3)运用深度优先算法查找从KA到KB的证书链;

(4)若存在从KA到KB的证书链,在哈希表中Hash(KB)的链表中添加KA,返回(1)(成功),否则返回0(代表查找失败)

算法由算法1和算法2组成:

算法1,本算法查找服务器上关于资源Y的对象为K的名字集合和授权证书集合,其中授权证书集合放在CAuthor(K,X)中,名字集合放在Name(K)中。

算法1流程如图3所示。

算法2,本算法共两个函数,实现功能:利用算法1的结果,在证书中查找证书链,函数返回1代表查找成功,返回0代表查找失败。

算法2流程如图4所示。

设计的证书链搜索算通过两个算法,在存在大量证书的证书库中,快速地实现了证书链的搜索。算法采用逆向搜索,从资源请求者开始查找,一直查找到ACL表中,算法查找过程中只规约与证书链相关的证书,大大提高了查找效率。同时需要特别注意的是,算法中利用缓存思想,将以前搜索到的证书链保存到一个哈希表中,下次查找时,直接查找哈希表,随着哈希表逐渐增大,查找速度会进一步提高。

图5 4种算法搜索证书链所用时间对比

4 实验结果分析

实验过程中的软硬件支持环境为:Windows XP 2000,2.0G的内存,VC++6.0。实验目的主要是判断算法的效率,由于是测试算法的性能,所以在模拟实验中没有必要使用真实的证书,使用的是证书的4元组(名字证书)和5元组(授权证书)形式。

模拟实验中,具体使用的实验数据在很大程度上影响着实验的精度,并决定着实验的参考价值。模拟实验中,用一个随机函数生成实验所需要的各种参数,以生成不同的证书集。主要是生成证书的密钥个数(K),证书名字个数(m),证书链长度(H),实体拥有的授权证书个数(G),证书扩展名长度(L),证书数量(n)。进行实验时要设置不同的证书集,只需设置不同的参数即可。

对选取的4种算法进行实验,通过数据进行分析,实验结果如图5所示。

其中,当证书数量分别为1000、2000、3000、5000和10000、20000、30000、50000时,测试函数其他的参数如表1所示。

表1 参数表

从图5的实验数据看出,Clarke D算法和基于双容器算法花费的时间比较长,Clarke D算法花费的时间最长,这两种算法都是集中式算法,主要时间花费在证书缩减上,证书缩减的复杂度都是O(N3L),其中N为系统中证书的总的数量,其中基于容器算法搜索证书链的时间比Clarke D算法稍微快一些。

明显看出,证书的规模越大,改进算法的性能优势越明显。证书数量较少时,改进的算法优势并不明显,证书数量越多,改进的算法与其他两种算法相比,优势越明显,原因是改进算法在证书链搜索时,只是涉及到与证书链搜索相关的证书,不去规约大量无关的证书,而前两种算法是集中式算法,进行证书链搜索时,无论证书链多长都把所有的证书牵扯进来,造成大量无关证书的规约,致使效率降低,与预期的想法一致。证书规模较小时,上述几种算法效率相差不大。改进的算法对比前两种算法,在证书规模越大时,算法的优势越明显,因此改进的算法适合大规模分布式网络环境。

5 结束语

文中以SPKI/SDSI证书为理论基础,设计和实现了一个基于SPKI/SDSI的访问控制模型,并提出了一种新的证书链搜索算法,极大地提高了证书链搜索效率,具有可行性和有效性,实验证明,证书数量越大,算法效率提高明显。

[1] Carl Ellison.SPKI/SDSI and the Web of Trust[J].Journal of Computer Security,2010,11(6):132-141.

[2] Buter W Lampson,Martin Abadi,Michael Burrows,et al.Authentication in Distributed Systems:Theory and Practice[J].ACM Transactions on Computer Systems,2011,10(4):265-310.

[3] B Lampson,Sean Smith.Using SPKI/SDSI for distributed maintenance of attribute release polices in shibbolefth[J].Journal of Computer Security,2010,9(4):235-239.

[4] Nazareth S,B Schneier.Ten Risk of PKI:What You are Not Beinig Told About Public Key Infrastructure[J].Communication of the ACM,2009,32(6).

[5] C Ellison,B Schneier.Risks of PKI:Electronic[J].Communication of the ACM,2010,43(2).

[6] Sameer Ajmani,Dwaine E Clark,Chuang-Hua Moh,etal.ConChord:Cooperative SDSI Certificate Storage and Name Resolution[J].IEEE Communications,2010,11(6):132-141.

[7] Martin Abadi.On SDSI's Linked Local Name Spaces[J].Journal of Computer Security,2008,6(1-2):3-21.

[8] Xavier Orri,J M Mas,Octalis SA.SPKI-XML Certificate Structure.draft-orri-spki-xml-cert-struc-00.ext[EB/OL].http://www.ecom.tifr.res.in/-wvp/pki/SPKI/draft-orri-spki-xml-cert-struc-00.pdf,2010.

[9] Yki Kortesniemi.SPKI Performance and certificate Chain Reduction[J].Journal of Computer Security,2010,15(9):131-137.