基于门限签名方案的BQS系统的服务器协议

ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],Vol.21,No.10,October2010,pp.2631−2641:[phone]©byInstituteofSoftware,theChineseAcademyofSciences.Allrightsreserved.基于门限签名方案的BQS系统的服务器协议∗荆继武1,王晶1,2,林璟锵1+,谢永泉1,顾青31(中国科学院研究生院信息安全国家重点实验室,北京100049)2(中国科学技术大学电子工程与信息科学系,安徽合肥230027)3(国家863计划信息安全基础设施研究中心,上海200336)ServerProtocolsofByzantineQuorumSystemsImplementedUtilizingThresholdSignatureSchemesJINGJi-Wu1,WANGJing1,2,LINJing-Qiang1+,XIEYong-Quan1,GUQing31(StateKeyLaboratoryofInformationSecurity,GraduateUniversity,TheChineseAcademyofSciences,Beijing100049,China)2(DepartmentofElectronicEngineeringandInformationScience,UniversityofScienceandTechnologyofChina,Hefei230027,China)3(InformationSecurityInfrastructureResearchCenterofNational863Program,Shanghai200336,China)+Correspondingauthor:E-mail:[e-mail],WangJ,LinJQ,XieYQ,GuQ.ServerprotocolsofByzantinequorumsystemsimplementedutilizingthresholdsignatureschemes.JournalofSoftware,2010,21(10):2631−2641.:Byzantinequorumsystems(BQSs)provideattack-resilientstorageservicesoverasynchronouschannelsandtoleratefservers’Byzantinefailures.COCA(Cornellonlinecertificationauthority)andCODEX(COrnellDataEXchange)havedesignedaserverprotocoltoimplementBQSsthresholdsignatureschemes(TSS-BQSs),whichcanexecuteproactiverecovery,conveniently,andcansimplifythekeymanagementandcommunicationofclients.Underthesamesystemmodelandchannelassumptions,anewserverprotocolthatsatisfiesthesecurityrequirementsofTSS-BQSisproposed.TheproposedprotocolinvolveslessroundsofcommunicationandperformsbetterthanthatofCOCA/CODEXinthecaseofconcurrentread-writeoperations.Keywords:Byzantinequorumsystem;thresholdsignaturescheme;attack-resilience;serverprotocol;fault-tolerance摘要:利用冗余复制技术,BQS(Byzantinequorumsystem)系统在异步信道上提供了能容忍f台服务器拜占庭失效的存储服务.COCA系统和CODEX系统设计了一种结合门限签名方案和BQS系统的服务器协议,完成了TSS-BQS(thresholdsignatureschemes-BQS)系统.与普通BQS系统相比,具有更易于支持ProactiveRecovery,简化客户端密钥管理和客户端通信的优点.基于相同的系统模型和信道假设,提出了一种新的服务器协议,满足TSS-BQS系统的安全要求;而且与已有协议相比,该协议只需更少的通信轮数,在读/写并发情况下执行效果更优.∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.70890084/G021102(国家自然科学基金);theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2006AA01Z454(国家高技术研究发展计划(863))Received2009-01-15;Revised2009-04-29;Accepted2009-06-012632JournalofSoftware软件学报Vol.21,No.10,October2010关键词:拜占庭选举系统;门限签名方案;攻击容忍;服务器协议;容错中图法分类号:TP393文献标识码:ABQS(Byzantinequorumsystem)系统[1]是利用冗余复制技术、容忍服务器拜占庭失效(Byzantinefailure,即任意失效arbitraryfailure)、运行于异步信道的存储系统.BQS系统由n台服务器组成,客户端每次操作都要与其中任意q(1qn)台服务器通信:写操作时,将数据写入q台服务器;读操作时,从任意q台服务器读出数据,再从中选出正确的结果.BQS系统的基本原理是:使执行读/写操作的服务器有足够大的交集,从而排除失效服务器的错误影响,保证读出的结果是最后一次写入的数据.更具体地,对于自验证数据(self-verifyingdata,例如数字证书),为了容忍f台失效服务器系统,共需要3f+1台服务器,每一次读/写操作在2f+1台服务器上进行.在实现BQS系统时,客户端需要与每台服务器之间建立双向安全信道(reliableandauthenticatedchannel)[1].最基本的方式是使用公钥算法来实现该信道[2]:所有客户端和服务器都具有自己的密钥对,发送者对消息进行数字签名,周期性地重发消息、直至收到接收者的确认消息(也带有接收者的数字签名).COCA(Cornellonlinecertificationauthority)系统[3]和CODEX(Cornelldataexchange)系统[4]设计了新的通信协议,完成了基于门限签名方案[5−9]的BQS系统(本文称为TSS-BQS(thresholdsignatureschemes-BQS)系统).在TSS-BQS系统中,系统配置有一对公私密钥对(称为ServiceKey),其私钥由n台服务器分享,任意h(hn)台服务器可使用私钥执行数字签名.对于TSS-BQS系统的每一次读/写操作,客户端只需收到具有ServiceKey数字签名的响应消息即完成操作:由ServiceKey门限签名保证该操作已在q台服务器上执行且返回正确结果.需要说明的是,TSS-BQS系统与特定算法无关,可使用多种不同(n,h)门限签名算法.TSS-BQS系统也同样运行于异步信道,可容忍f台服务器的拜占庭失效,且具有如下优点:•客户端配置唯一固定的ServiceKey公钥、不需要配置n台服务器的公钥,简化客户端的密钥管理;•客户端只需与任意f+1台服务器通信,收到1台服务器的响应消息后即可结束操作,简化客户端通信;•可在不影响客户端的情况下更方便地执行ProactiveRecovery[10]、更新服务器.相比而言,如果普通BQS系统更新服务器,就必须同时更新所有客户端上配置的服务器公钥.本文提出了一种新的服务器协议,具有TSS-BQS系统的优点,而且与COCA/CODEX系统的原有协议相比,需要更少的通信轮数、在读/写并发情况下执行效果更好.本文第1节介绍相关研究工作.第2节给出TSS-BQS系统的系统模型和信道假设.第3节描述两种服务器协议.第4节给出两种协议在安全性、效率和读/写并发等方面的分析.最后是总结.1相关工作Malkhi和Reiter在1998年首先给出了容忍f台服务器拜占庭失效的、运行于异步信道的存储系统理论[1],被称为BQS系统理论.使用不同的配置(分别称为MaskingQuorumSystem和DisseminationQuorumSystem),BQS系统可用于存储自验证数据或普通数据(genericdata).然后,他们基于BQS系统理论实现了Phalanx系统[2].在Phalanx系统中,所有客户端都需要配置至少2f+1台服务器的公钥,每一次读/写操作要同时与至少2f+1台服务器通信,接收2f+1个响应消息.在BQS系统理论的基础上,研究人员还给出了用于同步信道[11,12]、根据信道延迟优化操作[13]、动态参数配置[14,15]、存储秘密分享数据[16,17]等多种BQS系统扩展.COCA系统[3]首次利用门限签名方案来实现TSS-BQS系统,由多台服务器合作对读/写响应消息进行门限签名,从而保证操作已经按照BQS系统理论要求在2f+1台服务器上执行.基于TSS-BQS系统的基本存储功能,COCA系统又进一步实现了容错的数字证书(即自验证数据)的签发/查询服务.使用相同的TSS-BQS系统服务器协议,CODEX系统[4]实现了容错的机密性数据存储服务.2基于门限签名方案的BQS系统我们使用与COCA/CODEX系统完全一致的信道假设和系统模型.TSS-BQS系统运行于异步FairLink信荆继武等:基于门限签名方案的BQS系统的服务器协议2633道:信道可能丢失消息;但当发送者无限地发送消息时,则接收者可以收到消息.攻击者可以篡改、延迟、截获或删除消息.而且,信道没有最大延迟假设(即异步信道).TSS-BQS系统首先是BQS系统,由n台独立的服务器组成(记为Si,n≥i≥1),存储的数据记为x.每一台服务器Si都独立地提供读/写操作功能,Si存储的x值和时戳,记为[vi,ti].根据BQS系统理论,为了容忍f台服务器的拜占庭失效:•对自验证数据,系统由n=3f+1台服务器构成、客户端每次读/写q=2f+1台服务器;•对普通数据,系统由n=4f+1台服务器构成、客户端每次读/写q=3f+1台服务器.受篇幅所限,本文只详细讨论自验证数据的情况.在第5.4节大致说明了普通数据的情况.注意,由于写操作只在其中的任意q台服务器上执行,且服务器可能处于失效状态,所以各服务器存储的[vi,ti]可以不一致.对于自验证数据,使用如下Result()函数获得正确结果[1]:对读出的2f+1个结果,先排除验证无效的数据,然后取出时戳最大的结果.在TSS-BQS系统中,使用唯一固定的ServiceKey来实现对读/写响应消息的数字签名和验证.客户端只接受具有ServiceKey数字签名的响应消息.ServiceKey私钥(记为SK)由n台服务器分享、各服务器具有部分私钥,其中任意h(1hn)台服务器可利用门限签名方案执行数字签名.TSS-BQS系统同时还要求,各服务器具有自己的公私密钥对(不同于Se