PKI技术 第十八讲 COCA

PKI技术第十八讲COCA1COCA:CornellOnlineCertificationAuthorityCOCA:ASecureDistributedOnlineCertificationAuthorityLIDONGZHOU,MicrosoftResearchFREDB.SCHNEIDERandROBBERTVANRENESSE,CornellUniversityACMTransactionsonComputerSystems,November2002.2本课内容COCA的总体特点同时简要说明门限密码和BQS理论如何使用2种Operation来实现通常意义的证书、签发、更新、撤销、和查询Operations:UpdateandQuery系统结构2种Operation的协议详细过程讨论COCAPrototype3COCA的目标提供高安全的、高可用的证书服务包括证书签发、撤销、更新、证书查询服务通过：对CA密钥的保护证书存储服务器的冗余设置使用同一套的设备，提供了证书签发、证书查询的服务掌握CA密钥的服务器群，同时也存储用户证书容忍一定数量服务器的失效4CA密钥的保护－机密性CA密钥的机密性CA密钥是用于签发用户证书（和CRL）的，如果CA密钥被攻击，则攻击者可以伪造证书（和CRL），危害PKI系统和应用系统使用thresholdcryptography，将密钥分散到k个部件中，其中任意的t个合作，能够完成密码计算（签名操作）通常是分布在网络不同位置的k台服务器5CA密钥的保护－CA密钥的可用性CA密钥的可用性使用thresholdcryptography之后，则至少需要t台服务器在线而不是原先的1台必须保证在各种环境中，至少能够与t台服务器通信，才能实现服务的可用性在分布式网络环境中，路由器、交换机的链路错误，也会影响到可用性6证书撤销的处理—查询要求在COCA中，撤销问题是如下解决的：不签发CRL要求在使用证书之前，到COCA进行证书查询COCA保证能够回复最新的证书用户证书需要撤销时，就进行证书更新操作那么，CA的安全性还包括了证书查询的可靠性服务可用－能够查询到服务正确－得到最新的证书注意：服务器有可能死机、出错、失效等等7CA的安全性－证书查询的可靠冗余配置，多台服务器同时存储了最新的证书保证查询能够获得最新的用户证书、而不是过时的保证有足够数量的服务器回应否则服务不可用前提是将最新的证书写入到足够多的服务器中8COCA的特点CA同时提供了证书查询和更新（签发）服务CertificateUpdate/Query注意：通常，Query服务是由repository提供的使用thresholdcryptography保护CA密钥3t+1服务器，t+1才能合作进行数字签名最多t个服务器被攻占，不会泄漏私钥结合ByzantineQuorumSystem理论—证书查询Internet环境下，能够完成任务，得到最新的证书证书查询的可靠性3t+1服务器，最多t个服务器失效，保证协议能正确执行、执行成功（服务可用）9适用于各种门限密码学方案COCA并非针对特定的thresholdcryptographyscheme，作者认为COCA的系统结构适用于各种（t+1,3t+1）门限密码签名方案私钥由3t+1个服务器分享、任意的其中t+1个服务器可以完成签名操作即能够容忍一部分服务器的失效（t个服务器）BQS理论也有类似能力能容忍部分服务器的失效COCA的创新点不在于提出新的门限密码方案，而在于将门限密码学方案与BQS理论的相结合下面先简单介绍thresholdcryptography和ByzantineQuorumSystem10thresholdcryptography进行密码计算，需要使用密钥Key，要保证Key的安全注意：此处为了方便，签名门限用t表示，而COCA门限是t+1表示不同而已，实质一样将Key进行拆分，分成k个子密钥（SK1,SK2,…,SKk），由k个不同的设备掌握进行密码计算FKey(M)，多个设备分别进行计算（至少t个），得到t个结果F1SK1(M)、F1SK2(M)、F1SK3(M)…1<t<k再将t个结果进行计算F2(F1SK1(M),F1SK2(M),F1SK3(M)…)=FKey(M)F1,F2可以是不同于F的函数F是某种密码计算函数（例如，数字签名、解密）11Thresholdcryptography可继续参考：P.S.Gemmell.AnIntroductiontoThresholdCryptography.InCryptoBytes,atechnicalnewsletterofRSA,1977.机密性攻击者需要攻击t个服务器，才能获得Key，增加了攻击难度，提高机密性等级可用性只要是其中的任意t个服务器，就能够完成密码操作需要攻击(k-t+1)个服务器，使其不可用，才威胁到CA密钥的可用性可以根据机密性和可用性的权衡，调整t/k的大小12门限密码学不同于SecretShare不同于SecretShare秘密分享秘密分享是将某个机密信息X，进行拆分，拆分为k份，其中任意t（1<t<k）个，能够重新组合得到X少于t个，不能组合得到X在thresholdcryptography中，t个合作的结果是“密码运算的结果”，而不是密钥Key也就是说，被拆分的是Key，但是Key始终没有被组合出来运算输出结果仅仅是“数字签名结果”或者是“解密运算结果”13BQSMalkhiandReiter.1998.Byzantinequorumsystems.JournalofDistributedComputing11(4).通过冗余备份、解决分布式环境中的数据存储、读写问题冗余备份的服务器中，可能有failure针对arbitraryfailure，即出错服务器的行为是被攻击者完全控制的、不能预期的任意行为、而不是简单的停机又称为Byzantinefailure，失效的服务器可能发送正确数据、也可能发送错误数据、也可能不响应14BQS的基本原理如图Q表示全体服务器集合Q1：Write操作的目标服务器集合Q2：Read操作的目标服务器集合B表示失效服务器集合Byzantinefailure15BQS的Read/Write为了Read/Write正确执行，也就是能够读取到正确的、最新的数据：一致性：对任意的Q1,Q2，Q2中包含了Q1的元素，且能排除B的干扰得到最新的数据可用性：存在Q1和Q2，使得Q1与B无交集、Q2与B无交集协议能够执行完毕16BQS理论的作用讨论对于各种不同的环境假设（同步、异步）、不同的数据（有无时戳、是否自验证）下，Q/Q1/Q2/B各个集合之间的关系从而有各种不同类型的BQS系统MaskingBQSDisseminationBQSOpaqueMaskingQuorumsystemSmallBQS……17BQS理论的结论之一在异步的、无带宽要求的分布式环境中，读写“带时戳的”、“Self-Verifying”的数据即DisseminationBQS，COCA所使用的证书是Self-Verifying，因为具有CA的签名证书是带时戳的对于2个“Subject一样、具有CA有效签名”的证书使用有效期、或者证书序列号，能够确定其新旧某些CA，后签发的证书将具有更大的序列号；例如COCA结论：假设最多有t台服务器Byzantine失效，要求服务器总数至少是3t+1（满足一致性、可用性）写：至少对2t+1台服务器完成操作（其中可能有失效服务器）读：至少对2t+1台服务器完成操作（其中可能有失效服务器）18COCA对部署环境有如下假设FairLink（有无限小、但大于零的带宽；没有带宽要求）Acommunicationchannelthatdoesnotnecessarilydeliverallmessagessent,butifaprocesssendsinfinitelymanymessagestoasingledestinationtheninfinitelymanyofthosemessagesarecorrectlydelivered.Inaddition,messagesintransitmaybedisclosedtooralteredbyadversaries.所以，COCA要求各个服务器和Clients之间的通信使用数字签名保护，就可以检测到篡改Asynchrony.Thereisnoboundonmessagedeliverydelayorserverexecutionspeed.对于速度没有同步要求上述的链路假设，就是DisseminationBQS的链路假设部署环境要求低19本课内容COCA的总体特点如何使用2种Operation来实现通常意义的证书、签发、更新、撤销、和查询Operations:UpdateandQuery系统结构2种Operation的协议详细过程讨论COCAPrototype20COCA支持的2种OperationUpdate实现了通常意义上的：证书签发，将某个entity与公钥绑定撤销，解除entity与公钥的绑定关系更新，entity原来与某公钥绑定，Update操作后，则与另一公钥绑定Query证书查询，得到某entity的、最新的公钥绑定关系Client发起Update/Query操作请求，COCA回应执行结果21COCA中的Update操作Update操作Alice原来绑定PubKey1，变化为绑定PubKey2旧证书{Alice,PubKey1}产生新证书{Alice,PubKey2}Client得到新的证书新证书是由COCA签名的同时保证：在Update操作之后，至少已经向2t+1个服务器写入了新证书正确实现查询的前提条件也是BQS的“Write”的要求22通常意义的证书功能如何用Update操作实现通常意义的证书功能证书签发系统初始时，所有用户都与某个“无意义的公钥”相绑定将该“无意义的公钥”，Update成为某个新的公钥证书撤销将原有的、与某个公钥的绑定关系，变成与“无意义的公钥”相绑定证书更新更换公钥，进行Update23COCA中的Query操作Query操作Clients查询“Bob的最新证书是什么”COCA回应Bob的最新证书，回应消息也带有CA签名Resp={R,Certsig}sig其中R是请求消息标识Cert是本来就具有CA数字签名而且，整个回应消息Resp，也是具有CA数字签名的保证至少在其中的2t+1个服务器中都进行查询，然后比较证书序列号，得到最新的证书，然后回应24本课内容COCA的总体特点如何使用2种Operation来实现通常意义的证书、签发、更新、撤销、和查询Operations:UpdateandQuery系统结构2种Operation的协议详细过程讨论COCAPrototype25COCA的系统结构包括若干Clients和3t+1台服务器，如图：26COCA的系统结构3t+1台服务器，构成了COCA系统，分享了CA密钥，其中任意t+1能合作完成数字签名操作每台服务器同时各都带有自己的证书库，存储了用户证书除了部分密钥外（CA签名密钥的部分），每个服务器都有自己的公私密钥对、而且是相互知道的才有可能完成服务器之间的相互认证Client仅仅知道CA的公钥即可，不需要知道各服务器的公钥（即，不需要知道系统内部的太多细节）27Operation-ClientsClients向任意t+1个服务器发起请求因为可能正好t服务器已经失效保证至少有1台正确服务器收到请求至少要知道其中的t+1个服务器的地址周期性地重发请求，一直到得到COCA的回应与Link的假设相对应，不断地重复发送将最终会被收到请注意：Clients不一定是PKISubscriber也可能是RA，也可能是最终用户也可能是查询接口服务器等等28请求消息格式Query{Query,c,seq,cid,cred}Query，表示是查询请求c，Clients的名字seq，Clients维护的请求消息标识，每次请求都不同cid，被查询者的名字cred，credential，消息源认证保证信息来自可靠的ClientUpdate{Update,c,seq,cert’,cid,key,cred}Update，表示是Updatecert’，用户的旧证书因为在COCA中，Update新证书的序列号是由旧证书计算出的cid，更新证书的实体名字。c和cid不一定相等，c可能是RA、cid是subscriberkey，新的PublicKey29Operation-Server至少会有1个服务器接收到Clients的请求因为Clients向t+1个服务器不断地重复发送接收到请求后，正确的Server如下处理Update签名新的证书、将新证书发送到2t+1个服务器、签名回应消息、将回应消息返回Client注意：有2次签名操作（回应消息与新证书不一样）Query向2t+1个服务器进行查询、选出序列号最大的证书、签名回应消息回应消息中，包括了查询得到的最新证书上文的签名均指CA签名（利用门限密码方案完成）30本课内容COCA的总体特点如何使用2种Operation来实现通常意义的证书、签发、更新、撤销、和查询Operations:UpdateandQuery系统结构2种Operation的协议详细过程讨论COCAPrototype31COCA的协议详细过程Update协议签发证书、更新证书、撤销证书Query协议获得最新的证书32Update协议－1Clients向任意t+1服务器不停地重发请求{Update,c,seq,cert’,cid,key,cred}某台服务器（后面，称为delegateserver）接收到UpdateRequest之后，与其他服务器进行通信：签名新的证书、将新证书发送到2t+1个服务器、签名回应消息、将回应消息返回Client注意：各COCA服务器都另有自己的密钥对、而且都知道其他人的公钥，用于Server之间通信的签名和验证具体如下：33Update协议－2服务器签名新的证书产生新的证书（未签名的）新的证书序列号是按照预定的方式递增，根据旧证书算出向所有的其他服务器发出“门限签名请求”任意服务器，一旦接收到“门限签名请求”，就检查消息的正确性，然后进行门限签名，回应门限签名结果当收到足够多（至少t个）的门限签名结果，加上自己，共t+1个，将其组成有效的证书如果收不到足够的结果、或者不能组成有效的证书，则不断地重复发出“门限签名请求”34Update协议－3将新证书发送到2t+1个服务器根据t+1个门限签名结果，组成新的证书存储到自己的证书库向所有的其他服务器广播新的证书任意服务器，一旦接收到其他服务器发来的“新的证书”，就与本地存储的证书进行比较，如果的确是新的，就存储在本地，然后发送确认消息接收到2t个确认消息后（包括自己，共有2t+1台服务器拥有新的证书）如果收不到足够的确认消息，就不断地重复广播新的证书35Update协议－4签名“给Client的回应消息”将新的证书写入到2t+1个服务器后BQS理论的要求服务器将会生成1个“给Client的回应消息”回应消息包括：新的证书+表示Update已经成功完成的信息码向所有的其他服务器发出“门限签名请求”，要求签名“给Client的回应消息”过程与前面的签名新证书类似36Update协议－5将签名过的回应消息，发送给Client服务器收集到足够的门限签名结果，并且组成了“签名过的回应消息”发送给Client，完成Update协议Client验证response的有效性37Update协议结果由t+1服务器合作产生新证书将新证书存储到2t+1个服务器计算（最小计算量）2次门限签名2*（t+1部分签名，1次合成计算）（4t+3）次服务器签名如下情况，则计算量更大消息传递有错误失效服务器有意发送错误信息有多个DelegateServer38Query协议－1Clients向任意t+1服务器不停地重发请求{Query,c,seq,cid,cred}某台服务器（后面，称为delegateserver）接收到UpdateRequest之后，与其他服务器进行通信：向2t+1个服务器进行查询、选出序列号最大的证书、签名回应消息注意：各COCA服务器都另有自己的密钥对、而且都知道其他人的公钥，用于Server之间通信的签名和验证具体如下：39Query协议－2服务器查询最新的证书生成查询消息向所有的服务器发出查询消息任意服务器，一定接收到“查询消息”，就从自己的证书库中，找到该entity最新证书，然后回应接收到2t个查询回应后（包括自己，共查询了2t+1台服务器）比较2t+1个证书，选出最新（序列号最大）的证书40Query协议－3签名“给Client的回应消息”生成“给Client的回应消息”（未签名）消息中包括了刚刚选出的最新证书+表示Query已成功完成的信息码向所有的其他服务器发出“门限签名请求”任意服务器，一旦接收到“门限签名请求”，就检查消息的正确性，然后进行门限签名，回应门限签名结果当收到足够多（至少t个）的门限签名结果，加上自己共t+1个，将其组成有效的“给Client的回应消息”如果收不到足够的结果、或者不能组成有效的证书，则不断地重复发出“门限签名请求”41Query协议－4将签名过的回应消息，发送给Client消息中包括了刚刚选出的最新证书+表示Query已成功完成的信息码Client验证response的有效性42Query协议结果比较2t+1个服务器中的证书，取出最新的由t+1服务器合作产生回应消息计算（最小计算量）1次门限签名（3t+2）次服务器签名如下情况，则计算量更大消息传递有错误失效服务器有意发送错误信息有多个DelegateServer432种协议的分析－1回应消息的签名回应消息具有CA的签名，而不是某个特定服务器的签名使得Clients可以不知道各个服务器的实现细节Clients仅仅需要知道COCA的公钥（即CA证书），就可以验证回应消息的有效性可以定期地更换服务器的公私密钥对，不需要告诉Clients所以，在Update操作中，需要进行2次门限签名（1次是签证书，1次是签回应消息）442种协议的分析－2在假设下，Update/Query协议是否能够始终正确执行结束最多t个服务器的Byzantine出错、FairLink/Asynchrony通信均是使用不断重复广播至少1个服务器能接收到ClientRequestYESDelegate能否收到t个门限签名结果YES452种协议的分析－3在假设下，Update/Query协议是否能够始终正确执行结束最多t个服务器的Byzantine出错、FairLink/Asynchrony通信均是使用不断重复广播Delegate能否收到2t个确认消息BQS理论的结论：YES2t个证书中（加上Delegate，共2t+1），是否包含了最新的证书BQS理论的结论：YES46BQS对读写操作的前提要求假设最多有t台服务器失效，要求服务器总数至少是3t+1写：至少对2t+1台服务器完成操作读：至少对2t+1台服务器完成操作前提：“读”“写”操作是分别进行的即，在“写”操作完成之前，不进行“读”操作我们会看到，这导致了在COCA中，也有类似要求Query操作必须在Update操作执行完成后进行，才能保证查询得到最新的证书47本课内容COCA的总体特点系统结构如何使用2种Operation来实现通常意义的证书、签发、更新、撤销、和查询Operations:UpdateandQuery2种Operation的协议详细过程讨论DoSattackBQSProactiveRecoveryCOCAPrototype48COCAvs.DoSattack我们从COCA的协议中，可以看到，存在着很大的DoSattack隐患允许大量的广播和转发服务器之间，可以任意地转发、广播消息每次消息都将导致Server的公钥密码运算公钥计算，将会消耗大量的计算资源49DoSattack－ServerCOCA中的DoSattack假设有1台服务器被攻占虽然不能得到CA密钥，签发虚假证书CompromisedServer可以缓存多个Clientrequest，不断地向其他服务器广播上述行为是允许的、正常的将大量地消耗其他服务器的计算资源需要注意：公钥密码是极其消耗资源的50DoSattack－ClientsCOCA中的DoSattack假设有Client被攻占不断地进行查询，难以和正常Client区分开CompromisedClients可以同时向3t+1个服务器发送QueryRequest整个COCA系统的计算量就是：(3t+1)*(1次门限签名+(3t+2)次服务器签名)Server和Client之间的计算量极端不对称计算资源消耗型的DoS51COCA对于DoS攻击的应对由于在系统整体设计上，COCA引入了巨大的DoSattack隐患所以采取了多种措施来抑制DoSattackRequest的源认证CacheRequest的分类、轮流处理需要注意的是，这些抗DoS措施都是普遍的、并不是COCA专有的52Request的源认证—1Update/Query请求消息中包括credential，Delegate发送的相应门限签名请求，也要包括完整的request(credential)credential也就是Client计算的数据源认证所以，从CompromisedServer发起DoS攻击，要使用缓存的ClientRequest；不能自己伪造credential增加了CompromisedServer发起DoS攻击的难度53Request的源认证—2对于每个Client发出的Request中的seq（请求消息序列号），必须是递增的CompromisedServer只能重发每个Client的、最近的若干request如果正常Server发现：对于某一个Client，seq小于曾经处理过的seq，则拒绝处理54Cache缓存最近几次的计算结果经过上面分析，CompromisedServer只能是转发最近若干次的ClientRequest正常Server缓存了最近的计算结果，则不需要重新计算，仅仅取出缓存结果回复而已如果缓存命中率高，则难以形成DoS55Request的分类、轮流处理每个Server有多个处理队列，进行轮流处理。大致原理如下：来自不同服务器/Client的请求放入不同队列各个队列轮流处理，不让某个服务器/Client独占自己的计算资源，再次降低了DoS攻击的风险如图，处理顺序如下Req11,Req21,Msg11,Msg21,Req12,Req22,Msg22,…56COCA与其他门限密码CA系统的不同引入了BQS理论BQS是对于读写操作的理论Query等同于ReadUpdate接近于WriteUpdate等于：产生数据+Write数据57BQS理论的作用所以，Update操作可以视为2部分产生数据（证书）：普通的门限密码签名向2t+1服务器写入数据：普通的BQSWrite操作Query操作