PKI技術 第十八講 COCA

PKI技術第十八講COCA1COCA:CornellOnlineCertificationAuthorityCOCA:ASecureDistributedOnlineCertificationAuthorityLIDONGZHOU,MicrosoftResearchFREDB.SCHNEIDERandROBBERTVANRENESSE,CornellUniversityACMTransactionsonComputerSystems,November2002.2本課內容COCA的總體特點同時簡要說明門限密碼和BQS理論如何使用2種Operation來實現通常意義的證書、簽發(fā)、更新、撤銷、和查詢Operations:UpdateandQuery系統(tǒng)結構2種Operation的協(xié)議詳細過程討論COCAPrototype3COCA的目標提供高安全的、高可用的證書服務包括證書簽發(fā)、撤銷、更新、證書查詢服務通過：對CA密鑰的保護證書存儲服務器的冗余設置使用同一套的設備，提供了證書簽發(fā)、證書查詢的服務掌握CA密鑰的服務器群，同時也存儲用戶證書容忍一定數量服務器的失效4CA密鑰的保護－機密性CA密鑰的機密性CA密鑰是用于簽發(fā)用戶證書（和CRL）的，如果CA密鑰被攻擊，則攻擊者可以偽造證書（和CRL），危害PKI系統(tǒng)和應用系統(tǒng)使用thresholdcryptography，將密鑰分散到k個部件中，其中任意的t個合作，能夠完成密碼計算（簽名操作）通常是分布在網絡不同位置的k臺服務器5CA密鑰的保護－CA密鑰的可用性CA密鑰的可用性使用thresholdcryptography之后，則至少需要t臺服務器在線而不是原先的1臺必須保證在各種環(huán)境中，至少能夠與t臺服務器通信，才能實現服務的可用性在分布式網絡環(huán)境中，路由器、交換機的鏈路錯誤，也會影響到可用性6證書撤銷的處理—查詢要求在COCA中，撤銷問題是如下解決的：不簽發(fā)CRL要求在使用證書之前，到COCA進行證書查詢COCA保證能夠回復最新的證書用戶證書需要撤銷時，就進行證書更新操作那么，CA的安全性還包括了證書查詢的可靠性服務可用－能夠查詢到服務正確－得到最新的證書注意：服務器有可能死機、出錯、失效等等7CA的安全性－證書查詢的可靠冗余配置，多臺服務器同時存儲了最新的證書保證查詢能夠獲得最新的用戶證書、而不是過時的保證有足夠數量的服務器回應否則服務不可用前提是將最新的證書寫入到足夠多的服務器中8COCA的特點CA同時提供了證書查詢和更新（簽發(fā)）服務CertificateUpdate/Query注意：通常，Query服務是由repository提供的使用thresholdcryptography保護CA密鑰3t+1服務器，t+1才能合作進行數字簽名最多t個服務器被攻占，不會泄漏私鑰結合ByzantineQuorumSystem理論—證書查詢Internet環(huán)境下，能夠完成任務，得到最新的證書證書查詢的可靠性3t+1服務器，最多t個服務器失效，保證協(xié)議能正確執(zhí)行、執(zhí)行成功（服務可用）9適用于各種門限密碼學方案COCA并非針對特定的thresholdcryptographyscheme，作者認為COCA的系統(tǒng)結構適用于各種（t+1,3t+1）門限密碼簽名方案私鑰由3t+1個服務器分享、任意的其中t+1個服務器可以完成簽名操作即能夠容忍一部分服務器的失效（t個服務器）BQS理論也有類似能力能容忍部分服務器的失效COCA的創(chuàng)新點不在于提出新的門限密碼方案，而在于將門限密碼學方案與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可繼續(xù)參考：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).通過冗余備份、解決分布式環(huán)境中的數據存儲、讀寫問題冗余備份的服務器中，可能有failure針對arbitraryfailure，即出錯服務器的行為是被攻擊者完全控制的、不能預期的任意行為、而不是簡單的停機又稱為Byzantinefailure，失效的服務器可能發(fā)送正確數據、也可能發(fā)送錯誤數據、也可能不響應14BQS的基本原理如圖Q表示全體服務器集合Q1：Write操作的目標服務器集合Q2：Read操作的目標服務器集合B表示失效服務器集合Byzantinefailure15BQS的Read/Write為了Read/Write正確執(zhí)行，也就是能夠讀取到正確的、最新的數據：一致性：對任意的Q1,Q2，Q2中包含了Q1的元素，且能排除B的干擾得到最新的數據可用性：存在Q1和Q2，使得Q1與B無交集、Q2與B無交集協(xié)議能夠執(zhí)行完畢16BQS理論的作用討論對于各種不同的環(huán)境假設（同步、異步）、不同的數據（有無時戳、是否自驗證）下，Q/Q1/Q2/B各個集合之間的關系從而有各種不同類型的BQS系統(tǒng)MaskingBQSDisseminationBQSOpaqueMaskingQuorumsystemSmallBQS……17BQS理論的結論之一在異步的、無帶寬要求的分布式環(huán)境中，讀寫“帶時戳的”、“Self-Verifying”的數據即DisseminationBQS，COCA所使用的證書是Self-Verifying，因為具有CA的簽名證書是帶時戳的對于2個“Subject一樣、具有CA有效簽名”的證書使用有效期、或者證書序列號，能夠確定其新舊某些CA，后簽發(fā)的證書將具有更大的序列號；例如COCA結論：假設最多有t臺服務器Byzantine失效，要求服務器總數至少是3t+1（滿足一致性、可用性）寫：至少對2t+1臺服務器完成操作（其中可能有失效服務器）讀：至少對2t+1臺服務器完成操作（其中可能有失效服務器）18COCA對部署環(huán)境有如下假設FairLink（有無限小、但大于零的帶寬；沒有帶寬要求）Acommunicationchannelthatdoesnotnecessarilydeliverallmessagessent,butifaprocesssendsinfinitelymanymessagestoasingledestinationtheninfinitelymanyofthosemessagesarecorrectlydelivered.Inaddition,messagesintransitmaybedisclosedtooralteredbyadversaries.所以，COCA要求各個服務器和Clients之間的通信使用數字簽名保護，就可以檢測到篡改Asynchrony.Thereisnoboundonmessagedeliverydelayorserverexecutionspeed.對于速度沒有同步要求上述的鏈路假設，就是DisseminationBQS的鏈路假設部署環(huán)境要求低19本課內容COCA的總體特點如何使用2種Operation來實現通常意義的證書、簽發(fā)、更新、撤銷、和查詢Operations:UpdateandQuery系統(tǒng)結構2種Operation的協(xié)議詳細過程討論COCAPrototype20COCA支持的2種OperationUpdate實現了通常意義上的：證書簽發(fā)，將某個entity與公鑰綁定撤銷，解除entity與公鑰的綁定關系更新，entity原來與某公鑰綁定，Update操作后，則與另一公鑰綁定Query證書查詢，得到某entity的、最新的公鑰綁定關系Client發(fā)起Update/Query操作請求，COCA回應執(zhí)行結果21COCA中的Update操作Update操作Alice原來綁定PubKey1，變化為綁定PubKey2舊證書{Alice,PubKey1}產生新證書{Alice,PubKey2}Client得到新的證書新證書是由COCA簽名的同時保證：在Update操作之后，至少已經向2t+1個服務器寫入了新證書正確實現查詢的前提條件也是BQS的“Write”的要求22通常意義的證書功能如何用Update操作實現通常意義的證書功能證書簽發(fā)系統(tǒng)初始時，所有用戶都與某個“無意義的公鑰”相綁定將該“無意義的公鑰”，Update成為某個新的公鑰證書撤銷將原有的、與某個公鑰的綁定關系，變成與“無意義的公鑰”相綁定證書更新更換公鑰，進行Update23COCA中的Query操作Query操作Clients查詢“Bob的最新證書是什么”COCA回應Bob的最新證書，回應消息也帶有CA簽名Resp={R,Certsig}sig其中R是請求消息標識Cert是本來就具有CA數字簽名而且，整個回應消息Resp，也是具有CA數字簽名的保證至少在其中的2t+1個服務器中都進行查詢，然后比較證書序列號，得到最新的證書，然后回應24本課內容COCA的總體特點如何使用2種Operation來實現通常意義的證書、簽發(fā)、更新、撤銷、和查詢Operations:UpdateandQuery系統(tǒng)結構2種Operation的協(xié)議詳細過程討論COCAPrototype25COCA的系統(tǒng)結構包括若干Clients和3t+1臺服務器，如圖：26COCA的系統(tǒng)結構3t+1臺服務器，構成了COCA系統(tǒng)，分享了CA密鑰，其中任意t+1能合作完成數字簽名操作每臺服務器同時各都帶有自己的證書庫，存儲了用戶證書除了部分密鑰外（CA簽名密鑰的部分），每個服務器都有自己的公私密鑰對、而且是相互知道的才有可能完成服務器之間的相互認證Client僅僅知道CA的公鑰即可，不需要知道各服務器的公鑰（即，不需要知道系統(tǒng)內部的太多細節(jié)）27Operation-ClientsClients向任意t+1個服務器發(fā)起請求因為可能正好t服務器已經失效保證至少有1臺正確服務器收到請求至少要知道其中的t+1個服務器的地址周期性地重發(fā)請求，一直到得到COCA的回應與Link的假設相對應，不斷地重復發(fā)送將最終會被收到請注意：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個服務器不斷地重復發(fā)送接收到請求后，正確的Server如下處理Update簽名新的證書、將新證書發(fā)送到2t+1個服務器、簽名回應消息、將回應消息返回Client注意：有2次簽名操作（回應消息與新證書不一樣）Query向2t+1個服務器進行查詢、選出序列號最大的證書、簽名回應消息回應消息中，包括了查詢得到的最新證書上文的簽名均指CA簽名（利用門限密碼方案完成）30本課內容COCA的總體特點如何使用2種Operation來實現通常意義的證書、簽發(fā)、更新、撤銷、和查詢Operations:UpdateandQuery系統(tǒng)結構2種Operation的協(xié)議詳細過程討論COCAPrototype31COCA的協(xié)議詳細過程Update協(xié)議簽發(fā)證書、更新證書、撤銷證書Query協(xié)議獲得最新的證書32Update協(xié)議－1Clients向任意t+1服務器不停地重發(fā)請求{Update,c,seq,cert’,cid,key,cred}某臺服務器（后面，稱為delegateserver）接收到UpdateRequest之后，與其他服務器進行通信：簽名新的證書、將新證書發(fā)送到2t+1個服務器、簽名回應消息、將回應消息返回Client注意：各COCA服務器都另有自己的密鑰對、而且都知道其他人的公鑰，用于Server之間通信的簽名和驗證具體如下：33Update協(xié)議－2服務器簽名新的證書產生新的證書（未簽名的）新的證書序列號是按照預定的方式遞增，根據舊證書算出向所有的其他服務器發(fā)出“門限簽名請求”任意服務器，一旦接收到“門限簽名請求”，就檢查消息的正確性，然后進行門限簽名，回應門限簽名結果當收到足夠多（至少t個）的門限簽名結果，加上自己，共t+1個，將其組成有效的證書如果收不到足夠的結果、或者不能組成有效的證書，則不斷地重復發(fā)出“門限簽名請求”34Update協(xié)議－3將新證書發(fā)送到2t+1個服務器根據t+1個門限簽名結果，組成新的證書存儲到自己的證書庫向所有的其他服務器廣播新的證書任意服務器，一旦接收到其他服務器發(fā)來的“新的證書”，就與本地存儲的證書進行比較，如果的確是新的，就存儲在本地，然后發(fā)送確認消息接收到2t個確認消息后（包括自己，共有2t+1臺服務器擁有新的證書）如果收不到足夠的確認消息，就不斷地重復廣播新的證書35Update協(xié)議－4簽名“給Client的回應消息”將新的證書寫入到2t+1個服務器后BQS理論的要求服務器將會生成1個“給Client的回應消息”回應消息包括：新的證書+表示Update已經成功完成的信息碼向所有的其他服務器發(fā)出“門限簽名請求”，要求簽名“給Client的回應消息”過程與前面的簽名新證書類似36Update協(xié)議－5將簽名過的回應消息，發(fā)送給Client服務器收集到足夠的門限簽名結果，并且組成了“簽名過的回應消息”發(fā)送給Client，完成Update協(xié)議Client驗證response的有效性37Update協(xié)議結果由t+1服務器合作產生新證書將新證書存儲到2t+1個服務器計算（最小計算量）2次門限簽名2*（t+1部分簽名，1次合成計算）（4t+3）次服務器簽名如下情況，則計算量更大消息傳遞有錯誤失效服務器有意發(fā)送錯誤信息有多個DelegateServer38Query協(xié)議－1Clients向任意t+1服務器不停地重發(fā)請求{Query,c,seq,cid,cred}某臺服務器（后面，稱為delegateserver）接收到UpdateRequest之后，與其他服務器進行通信：向2t+1個服務器進行查詢、選出序列號最大的證書、簽名回應消息注意：各COCA服務器都另有自己的密鑰對、而且都知道其他人的公鑰，用于Server之間通信的簽名和驗證具體如下：39Query協(xié)議－2服務器查詢最新的證書生成查詢消息向所有的服務器發(fā)出查詢消息任意服務器，一定接收到“查詢消息”，就從自己的證書庫中，找到該entity最新證書，然后回應接收到2t個查詢回應后（包括自己，共查詢了2t+1臺服務器）比較2t+1個證書，選出最新（序列號最大）的證書40Query協(xié)議－3簽名“給Client的回應消息”生成“給Client的回應消息”（未簽名）消息中包括了剛剛選出的最新證書+表示Query已成功完成的信息碼向所有的其他服務器發(fā)出“門限簽名請求”任意服務器，一旦接收到“門限簽名請求”，就檢查消息的正確性，然后進行門限簽名，回應門限簽名結果當收到足夠多（至少t個）的門限簽名結果，加上自己共t+1個，將其組成有效的“給Client的回應消息”如果收不到足夠的結果、或者不能組成有效的證書，則不斷地重復發(fā)出“門限簽名請求”41Query協(xié)議－4將簽名過的回應消息，發(fā)送給Client消息中包括了剛剛選出的最新證書+表示Query已成功完成的信息碼Client驗證response的有效性42Query協(xié)議結果比較2t+1個服務器中的證書，取出最新的由t+1服務器合作產生回應消息計算（最小計算量）1次門限簽名（3t+2）次服務器簽名如下情況，則計算量更大消息傳遞有錯誤失效服務器有意發(fā)送錯誤信息有多個DelegateServer432種協(xié)議的分析－1回應消息的簽名回應消息具有CA的簽名，而不是某個特定服務器的簽名使得Clients可以不知道各個服務器的實現細節(jié)Clients僅僅需要知道COCA的公鑰（即CA證書），就可以驗證回應消息的有效性可以定期地更換服務器的公私密鑰對，不需要告訴Clients所以，在Update操作中，需要進行2次門限簽名（1次是簽證書，1次是簽回應消息）442種協(xié)議的分析－2在假設下，Update/Query協(xié)議是否能夠始終正確執(zhí)行結束最多t個服務器的Byzantine出錯、FairLink/Asynchrony通信均是使用不斷重復廣播至少1個服務器能接收到ClientRequestYESDelegate能否收到t個門限簽名結果YES452種協(xié)議的分析－3在假設下，Update/Query協(xié)議是否能夠始終正確執(zhí)行結束最多t個服務器的Byzantine出錯、FairLink/Asynchrony通信均是使用不斷重復廣播Delegate能否收到2t個確認消息BQS理論的結論：YES2t個證書中（加上Delegate，共2t+1），是否包含了最新的證書BQS理論的結論：YES46BQS對讀寫操作的前提要求假設最多有t臺服務器失效，要求服務器總數至少是3t+1寫：至少對2t+1臺服務器完成操作讀：至少對2t+1臺服務器完成操作前提：“讀”“寫”操作是分別進行的即，在“寫”操作完成之前，不進行“讀”操作我們會看到，這導致了在COCA中，也有類似要求Query操作必須在Update操作執(zhí)行完成后進行，才能保證查詢得到最新的證書47本課內容COCA的總體特點系統(tǒng)結構如何使用2種Operation來實現通常意義的證書、簽發(fā)、更新、撤銷、和查詢Operations:UpdateandQuery2種Operation的協(xié)議詳細過程討論DoSattackBQSProactiveRecoveryCOCAPrototype48COCAvs.DoSattack我們從COCA的協(xié)議中，可以看到，存在著很大的DoSattack隱患允許大量的廣播和轉發(fā)服務器之間，可以任意地轉發(fā)、廣播消息每次消息都將導致Server的公鑰密碼運算公鑰計算，將會消耗大量的計算資源49DoSattack－ServerCOCA中的DoSattack假設有1臺服務器被攻占雖然不能得到CA密鑰，簽發(fā)虛假證書CompromisedServer可以緩存多個Clientrequest，不斷地向其他服務器廣播上述行為是允許的、正常的將大量地消耗其他服務器的計算資源需要注意：公鑰密碼是極其消耗資源的50DoSattack－ClientsCOCA中的DoSattack假設有Client被攻占不斷地進行查詢，難以和正常Client區(qū)分開CompromisedClients可以同時向3t+1個服務器發(fā)送QueryRequest整個COCA系統(tǒng)的計算量就是：(3t+1)*(1次門限簽名+(3t+2)次服務器簽名)Server和Client之間的計算量極端不對稱計算資源消耗型的DoS51COCA對于DoS攻擊的應對由于在系統(tǒng)整體設計上，COCA引入了巨大的DoSattack隱患所以采取了多種措施來抑制DoSattackRequest的源認證CacheRequest的分類、輪流處理需要注意的是，這些抗DoS措施都是普遍的、并不是COCA專有的52Request的源認證—1Update/Query請求消息中包括credential，Delegate發(fā)送的相應門限簽名請求，也要包括完整的request(credential)credential也就是Client計算的數據源認證所以，從CompromisedServer發(fā)起DoS攻擊，要使用緩存的ClientRequest；不能自己偽造credential增加了CompromisedServer發(fā)起DoS攻擊的難度53Request的源認證—2對于每個Client發(fā)出的Request中的seq（請求消息序列號），必須是遞增的CompromisedServer只能重發(fā)每個Client的、最近的若干request如果正常Server發(fā)現：對于某一個Client，seq小于曾經處理過的seq，則拒絕處理54Cache緩存最近幾次的計算結果經過上面分析，CompromisedServer只能是轉發(fā)最近若干次的ClientRequest正常Server緩存了最近的計算結果，則不需要重新計算，僅僅取出緩存結果回復而已如果緩存命中率高，則難以形成DoS55Request的分類、輪流處理每個Server有多個處理隊列，進行輪流處理。大致原理如下：來自不同服務器/Client的請求放入不同隊列各個隊列輪流處理，不讓某個服務器/Client獨占自己的計算資源，再次降低了DoS攻擊的風險如圖，處理順序如下Req11,Req21,Msg11,Msg21,Req12,Req22,Msg22,…56COCA與其他門限密碼CA系統(tǒng)的不同引入了BQS理論BQS是對于讀寫操作的理論Query等同于ReadUpdate接近于WriteUpdate等于：產生數據+Write數據57BQS理論的作用所以，Update操作可以視為2部分產生數據（證書）：普通的門限密碼簽名向2t+1服務器寫入數據：普通的BQSWrite操作Query操作