本文是基于作者最近發(fā)表于CCSW’14的一篇論文，Distributed Key Generation for Encrypted Deduplication:Achieving the Strongest Privacy，簡要介紹云存儲系統(tǒng)中支持?jǐn)?shù)據(jù)去重的加密算法的最新進(jìn)展。論文的DOI是 http://dx.doi.org/10.1145/2664168.2664169
為了描述方便，本文采用了和論文中完全一致的參考文獻(xiàn)標(biāo)號。讀者可去論文中直接參閱。
1. 背景
大規(guī)模云存儲系統(tǒng)往往面臨兩個矛盾的需求：一方面系統(tǒng)需要壓縮數(shù)據(jù)以節(jié)省存儲空間的開銷;另一方面，用戶出于數(shù)據(jù)安全和隱私的考慮，希望自己的數(shù)據(jù)加密存儲。目前數(shù)據(jù)壓縮非常有效也是很常用的一個手段是去重(deduplication)，即識別數(shù)據(jù)中冗余的數(shù)據(jù)塊，只存儲一份，其余位置存儲類似指針的數(shù)據(jù)結(jié)構(gòu)。研究表明，基于數(shù)據(jù)分布的不同，有效的去重能夠節(jié)省高達(dá)50%甚至90%的存儲空間和帶寬 [32, 17, 27, 21]。去重已經(jīng)被廣泛用于很多商業(yè)化的系統(tǒng)如 Dropbox [3]，EMC [36]，等等。許多Peer-to-Peer (P2P) 系統(tǒng)也使用同樣的技術(shù)來節(jié)省存儲空間 [52, 53, 5, 6].
但是去重卻是和數(shù)據(jù)加密的目標(biāo)直接相矛盾的。為什么這么說呢呢?這是由于加密本身的性質(zhì)和目標(biāo)造成的。人類使用加密手段來保護(hù)數(shù)據(jù)的安全已經(jīng)有上千年的歷史了，最早的密碼可以追溯到公元前1900年的埃及古王國時期。近代，尤其是兩次世界大戰(zhàn)中各方的斗法極大地推動了密碼學(xué)的發(fā)展。步入計(jì)算機(jī)時代，密碼學(xué)更是如虎添翼。90年代興起的互聯(lián)網(wǎng)，特別是迅猛發(fā)展電子商務(wù)，既對密碼技術(shù)提出了更高的需求(從而進(jìn)一步推動了它的發(fā)展)，也使得密碼技術(shù)應(yīng)用到人們生活的各個方面。今天，從網(wǎng)上銀行到在線購物，從電子郵件到社交網(wǎng)絡(luò)甚至游戲，密碼技術(shù)無處不在。
然而，人們對密碼安全性的認(rèn)識卻是直到80年代才有了實(shí)質(zhì)性的進(jìn)展。在此之前，人們對密碼安全性的目標(biāo)缺乏嚴(yán)格的定義，從而缺乏對其度量的尺度。一個加密算法到底怎樣才算是安全的?這個貌似簡單的問題其實(shí)需要非常深刻的對密碼本質(zhì)的思考。加密算法不是孤立地，它會被使用在不同的環(huán)境和條件下。密碼學(xué)家期望能夠?qū)用芩惴ǖ男再|(zhì)做出精確的刻畫和嚴(yán)格的證明，從而避免在數(shù)據(jù)安全上出現(xiàn)百密一疏的漏洞。這一點(diǎn)非常不容易做到，它不僅僅取決于人們對密碼本質(zhì)的理解，還依賴相關(guān)學(xué)科(例如信息論等)的發(fā)展。
1.1 Information-theoretic Security
1949年，信息論的創(chuàng)始人Claude Shannon從信息論的角度考察密文所泄露的關(guān)于原文的信息，提出了information-theoretic security的概念。
簡單地講，一個具有information-theoretic security的加密算法所產(chǎn)生的密文對于一個沒有相應(yīng)秘鑰的人來說，不含有任何關(guān)于原文的信息。
這一性質(zhì)的后果是，即使對手擁有無限的計(jì)算能力和時間，也不可能破譯。這顯然是一個極強(qiáng)的概念，但是在實(shí)際中很難使用，因?yàn)樗笫褂煤驮拈L度一樣的隨機(jī)秘鑰，并且每一個秘鑰只能使用一次。滿足這種性質(zhì)的加密算法只有一種，就是One-time pad(OTP)。
現(xiàn)實(shí)中OTP是不可能實(shí)用的，人們很難安全地分發(fā)和原文長度一樣的秘鑰。于是人們退而追求computational secrecy。即，我們假設(shè)對手的計(jì)算能力是有限的，我們的加密算法只要做到對手在可行的時間內(nèi)無法破譯就可以認(rèn)為是安全的。在這種模式下，我們需要一個新的方式來度量密文所泄露的信息。
1.2 Semantic Security
1982年，當(dāng)時還正在UC Berkeley讀研究生的Shafi Goldwasser和Silvio Micali [39] 提出了semantic security的概念。
這一概念的闡述可以基于比較兩個事件的概率：
1. 給定一個密文，和原文的長度，一個polynomial-time的對手從中算出關(guān)于原文的任何部分信息(如原文是奇數(shù)還是偶數(shù));
2. 只基于原文的長度(沒有密文)，任何一個polynomial-time算法從中算出關(guān)于原文的任何部分信息。
如果1和2的概率足夠接近，則該加密算法被認(rèn)為滿足semantic security。我們試著來理解一下這個定義。在1的情況，對手拿到密文和原文的長度，在2的情況下，對手只拿到原文的長度，完全沒有密文。如果這兩個情況下對手成功獲得原文信息的概率接近的話，說明該加密算法產(chǎn)生的密文不足以使之從中獲取任何關(guān)于原文的信息，因?yàn)橛兴蜎]它差別不大。這顯然是一個安全的狀態(tài)。
稍后Goldwasser和Micali又給出了一個基于密文不可區(qū)分性，即ciphertext indistinguishability (IND) [40]，的等價定義。IND的意思是，給定從兩個原文m0和m1中隨機(jī)選擇一個進(jìn)行加密后產(chǎn)生的密文，對手不能區(qū)分加密的是哪一個。后者因?yàn)楦菀资褂枚粡V泛采納。
這是一個里程碑性的工作，它賦予安全性明確嚴(yán)格的數(shù)學(xué)定義，使得密碼的設(shè)計(jì)和分析都有了明確的方向，它的意義是如何強(qiáng)調(diào)也不過分的。正如ACM對兩位的評價，他們的工作“helped make cryptography a precise science。”部分由于他們的這一開拓性的工作，兩位作者在30年后(2013年)獲得圖靈獎(ACM Turing Award)。
2. 云存儲系統(tǒng)中的去重與加密
回到云存儲的應(yīng)用中來，云存儲系統(tǒng)中使用支持去重的加密問題的主要挑戰(zhàn)有兩點(diǎn)：
1). 加密之后的密文需要保留原文的冗余，即原文相同的數(shù)據(jù)塊加密后的密文仍相同(這里的相同不一定是密文的全等，系統(tǒng)只要一種識別包含相同內(nèi)容的密文的手段即可)，這樣去重才能夠起作用。
2). Cross-user decryption (CUD)，即由某個用戶加密上傳的數(shù)據(jù)塊應(yīng)該能夠被所有有讀取權(quán)限的用戶解密，即使后者不是最初的上傳和加密者。
2可以用“lockbox”或者key encapsulation 的方式解決 [22, 45, 29]，在此不再贅述。而1所需的特性我們稱之為convergent特性，它是基于去重的數(shù)據(jù)壓縮不可或缺的。但是，它與加密算法的安全性定義有不可調(diào)和的矛盾。Semantic security明確禁止原文相等性的檢測，即給定兩個密文，不應(yīng)該能夠允許對手?jǐn)喽ㄋ鼈兗用艿氖欠袷峭瑯拥臄?shù)據(jù)，否則對手可以利用這一性質(zhì)攻破前述IND。可以明確斷言的是，滿足現(xiàn)代加密算法安全性(如semantic security)的所有加密算法都不支持去重。
3. Convergent Encryption (CE)及其安全性
于是退而求其次，即，我們可以適度放寬對安全性的要求，允許密文泄露原文相等性信息，從而使加密后的去重成為可行。最早提出的方案是Convergent Encryption (CE) [27]。它的想法非常簡單：一個數(shù)據(jù)塊d的加密如下：
E(h(d), d)
其中E(key, d)是以key做秘鑰加密數(shù)據(jù)d的對稱加密算法，h(x)是一個hash function。也就是說， 當(dāng)需要加密一個數(shù)據(jù)塊d的時候，CE先用數(shù)據(jù)內(nèi)容生成key，再用一個symmetric encryption算法(如AES等)加密。
嚴(yán)格地講，symmetric encryption加密算法本身通常都是randomized或者stateful，即除了key之外，算法本身會生成一些隨機(jī)數(shù)(例如Initialization vector或IV)，或者維護(hù)一個計(jì)數(shù)器之類的狀態(tài)，這樣即使多次加密同樣的信息也會有不同的結(jié)果，目的還是為了獲得類似semantic security這樣的安全性。這里CE的做法可以理解為h(x)輸出的一部分作為key，另外一部分作為算法所需的隨機(jī)數(shù)(如IV)。這樣做的結(jié)果是，不管是哪個用戶加密，同樣的數(shù)據(jù)塊一定會被加密成同樣的密文，后續(xù)可以做去重了。CE已經(jīng)被廣泛應(yīng)用于很多研究[14, 7]和商業(yè)系統(tǒng)中比如Freenet [5], GNUnet [6], flud [4], Ciphertite [2], Bitcasa[1]等。
但是一個令密碼學(xué)研究者不安的狀況是，雖然CE已經(jīng)被廣泛應(yīng)用，它的安全性卻始終沒有嚴(yán)格的分析。它顯然沒有達(dá)到semantic security。那么它到底提供一種什么樣的保護(hù)呢?這種保護(hù)是否足夠?是否存在很容易的破解方法使得它完全失去作用?在沒有解決這些問題的情況下就廣泛使用它顯然是令人忐忑的。人們曾經(jīng)做過一些邊緣性的工作，比如人們研究過deterministic encryption所能達(dá)到的安全性[9, 16, 11]。直到2013年，Mihir Bellare, et al., 才把這些研究都納入了Message-Locked Encryption(MLE)的框架 [13]。他們同時提出了PRV$-CDA的安全性概念，并證明了PRV$-CDA比其他相關(guān)的安全性都更強(qiáng)。簡單地地講，MLE是這樣一種加密算法，它使用的key是從待加密的原文算出來的(key used for encryption is derived from the message itself)。CE是MLE的一個特例。MLE允許原文相等信息的判斷(equality checking)，從而支持去重。
PRV$-CDA是什么意義呢?PRV$-CDA的命名采用與其他安全性定義相同的慣例：以橫線(-)為界，前面是所達(dá)到的目標(biāo)，后面是所承受的攻擊。$通常表示隨機(jī)數(shù)據(jù)或因素。在PRV$-CDA的例子里，CDA代表chosen-distribution attack，PRV$代表與隨機(jī)數(shù)的不可區(qū)分性。簡單講，PRV$-CDA意味著對手不能夠?qū)⒚芪耐c密文同樣長度的隨機(jī)數(shù)區(qū)分開來。具體的定義這里不在贅述，感興趣的讀者可參看 [13]。
這是一個相當(dāng)強(qiáng)的定義。在應(yīng)用于MLE時，必須對待加密的數(shù)據(jù)有所限制才能達(dá)到。簡單講，數(shù)據(jù)本身必須有足夠大的最小熵(min-entropy)，亦即數(shù)據(jù)必須是不可預(yù)測的，否則達(dá)不到PRV$-CDA的安全性。min-entropy是衡量一個隨機(jī)變量的不可預(yù)測性的度量，具體定義可參看相關(guān)文獻(xiàn)。例如，如果待加密的數(shù)據(jù)只有“進(jìn)攻”和“撤退”兩個可能的話(數(shù)據(jù)分布的不可預(yù)測性很低)，則對手可以很容易地破解一個MLE(只要將所有可能的原文都加密，和欲破解的密文相比即可)。
4. Convergent Encryption的弱點(diǎn)
在MLE的框架下，CE被證明滿足PRV$-CDA安全性 [13]。這是一個有重大意義的成果，人們終于能夠準(zhǔn)確刻畫一個已經(jīng)被廣泛使用的技術(shù)的安全性了。萬事大吉了嗎?NO!至少還剩下兩個問題：
1. PRV$-CDA安全性對于存儲系統(tǒng)來說是否足夠強(qiáng)?
2. 是否還有可能獲得比PRV$-CDA更強(qiáng)的安全性?
對1，我們的判斷是否定的。首先，我們知道，MLE只能保護(hù)具有比較高的不可預(yù)測性的數(shù)據(jù)。而在云存儲系統(tǒng)的實(shí)際使用中，很多用戶數(shù)據(jù)恰恰是可預(yù)測。比如說很多公司的文檔都有共同的模板和格式，這可能導(dǎo)致有些數(shù)據(jù)塊只可能有很少的取值可能。其次，即使數(shù)據(jù)的不可預(yù)測性很高，對手仍然可以很容易地驗(yàn)證一個信息：判斷給定的密文是否加密了一個來自于一個不大的集合的數(shù)據(jù)。只要將該集合內(nèi)的所有元素分別加密后與給定密文比較即可。在很多情況下，這一信息可能是非常嚴(yán)重的泄露。例如，云存儲的提供商可以很容易判斷一個用戶的加密數(shù)據(jù)中是否包括某些受版權(quán)保護(hù)的電影。
對于第二個問題，最新的研究給出的答案是肯定的。我們的CCSW’14工作指出，所有的CE或MLE，有一個關(guān)鍵的特性是public encryption，即任何一個人，只要拿到數(shù)據(jù)，就可以生成合法的密文。所有public encryption的MLE的安全都依賴于數(shù)據(jù)本身的隨機(jī)性，再加上MLE允許equality checking，這就決定了MLE只能保護(hù)具有足夠大的min-entropy的數(shù)據(jù)這一局限性。PRV$-CDA的定義對數(shù)據(jù)分布做了明確的限制。那么這種局限是否可以突破呢?答案是肯定的。MLE之所以采取public encryption的模式，是考慮到不同的用戶需要獨(dú)立地完成數(shù)據(jù)加密，并且需要同樣的數(shù)據(jù)產(chǎn)生同樣的密文。
完成這一目標(biāo)還可以采用另外一種server assisted模式。即引入一個第三方的服務(wù)，該服務(wù)協(xié)助用戶生成加密所需要的數(shù)據(jù)(key和IV等)，并保證去重所需要的convergent特性。引入一個第三方的服務(wù)的好處是，該服務(wù)可以使用所有用戶都不知道的秘密數(shù)據(jù)(比如另外一個key)。這就意味著加密過程不再是公開的，從而杜絕前面提到過的問題。DupLESS [12]和我們最新的工作都是這方面的思路。
5. Encryption with Signature(EwS)及其安全性
我們在加密過程中如何引入額外的秘密且同時保證密文的convergent特性呢?和MLE的思路類似，我們需要由數(shù)據(jù)產(chǎn)生加密的key(從而保證convergent特性)，而我們不希望這一個過程是公開的。一個辦法是，由第三方服務(wù)用自己的秘鑰對數(shù)據(jù)簽名(這里簽名算法必須是deterministic的)，然后用簽名作為偽隨機(jī)數(shù)生成器的種子，從而得到一致的加密key。DupLESS [12]和我們的CCSW’14論文都采用這種方法。我們稱之為Encryption with Signature(EwS)，其過程可以用下圖表示：
其中H和G都是hash function，Sign是數(shù)字簽名算法(如RSA)，SK是Sign所需要的秘鑰，它由第三方服務(wù)掌握，或者用secret sharing的方式分布式地存儲于各個用戶。SE是一個symmetric encryption算法(如AES)。也就是說，EwS先對數(shù)據(jù)進(jìn)行簽名，然后用簽名生成加密的key。只要使用的簽名算法是deterministic的，則每一個數(shù)據(jù)塊都會被加密成唯一的密文。
那么這種方法獲得的安全性是什么樣的呢?我們的論文給出了這個問題的答案。我們提出了一個新的安全性概念，稱為D-IND$并證明D-IND$-CPA嚴(yán)格強(qiáng)于(strictly stronger than)PRV$-CDA。與PRV$-CDA類似，D-IND$也意味著對手不能夠?qū)⒚芪耐c密文同樣長度的隨機(jī)數(shù)區(qū)分開來。但是，D-IND$-CPA不再要求數(shù)據(jù)的分布具有高的min-entropy，從而可以保護(hù)可預(yù)測性比較高的數(shù)據(jù)。我們證明EwS的模式是滿足D-IND$-CPA安全性。
為了更好地理解CE和EwS安全性的區(qū)別，亦即PRV$-CDA和D-IND$-CPA的區(qū)別，我們再來看前面的例子。如果待加密的數(shù)據(jù)只有“進(jìn)攻”和“撤退”兩個可能的話，則對手可以很容易地破解一個CE。但是如果數(shù)據(jù)是用EwS的加密的，則這種攻擊不再可能，因?yàn)閷κ譀]有第三方服務(wù)用來簽名的秘鑰。
與DupLESS [12]相比，我們的方案還有一個優(yōu)勢就是它是分布式的。它不需要第三方的服務(wù)，可以直接將服務(wù)部署在用戶中。它巧妙使用了threshold signature這一工具。Threshold signature是一種分布式的數(shù)字簽名生成技術(shù)，它將簽名所用的秘鑰分布地存儲于多個節(jié)點(diǎn)，使得任何小于t個節(jié)點(diǎn)聯(lián)合起來，既不能夠計(jì)算出簽名的秘鑰，也不能夠生成正確的簽名。相反任何大于t個節(jié)點(diǎn)聯(lián)合起來就能夠生成正確的簽名。其中t是一個系統(tǒng)參數(shù)。這一特性使得threshold signature既具有更高的安全性，也有更好的容錯能力。用在EwS上，簽名的秘鑰不再有單一個服務(wù)器維護(hù)，它會分布在所有用戶中。當(dāng)一個用戶需要加密時，他向大于t個其他用戶發(fā)出請求，在足夠多的用戶的協(xié)助下生成簽名，再使用EwS方式加密。
我們還證明了，EwS，不論是單機(jī)的還是分布式的，僅僅泄露數(shù)據(jù)相等的信(message equality)。而該信息是目前去重手段所依賴的，這表明EwS是支持去重條件下所能達(dá)到的最強(qiáng)的安全性。
6. 結(jié)論
綜上，存儲系統(tǒng)中去重和加密是一對矛盾的需求，要支持去重的話必須降低對加密算法安全性的要求。我們提出了D-IND$的安全性概念并證明了D-IND$強(qiáng)于目前所有的相關(guān)安全性定義。同時又證明了D-IND$是支持去重的加密算法所能達(dá)到的最強(qiáng)的安全性。那么問題來了，這樣的安全性是否足夠?特別是，為了支持去重而不得不泄露的數(shù)據(jù)相等性信息對用戶來講是否可以接受?
如何衡量和控制這種泄露?這些都是后續(xù)待研究的問題。
京公網(wǎng)安備 11010502049343號