本文是基于作者最近發(fā)表于CCSW’14的一篇論文，Distributed Key Generation for Encrypted Deduplication:Achieving the Strongest Privacy，簡要介紹云存儲(chǔ)系統(tǒng)中支持?jǐn)?shù)據(jù)去重的加密算法的最新進(jìn)展。論文的DOI是 http://dx.doi.org/10.1145/2664168.2664169

為了描述方便，本文采用了和論文中完全一致的參考文獻(xiàn)標(biāo)號(hào)。讀者可去論文中直接參閱。

1. 背景

大規(guī)模云存儲(chǔ)系統(tǒng)往往面臨兩個(gè)矛盾的需求：一方面系統(tǒng)需要壓縮數(shù)據(jù)以節(jié)省存儲(chǔ)空間的開銷;另一方面，用戶出于數(shù)據(jù)安全和隱私的考慮，希望自己的數(shù)據(jù)加密存儲(chǔ)。目前數(shù)據(jù)壓縮非常有效也是很常用的一個(gè)手段是去重(deduplication)，即識(shí)別數(shù)據(jù)中冗余的數(shù)據(jù)塊，只存儲(chǔ)一份，其余位置存儲(chǔ)類似指針的數(shù)據(jù)結(jié)構(gòu)。研究表明，基于數(shù)據(jù)分布的不同，有效的去重能夠節(jié)省高達(dá)50%甚至90%的存儲(chǔ)空間和帶寬 [32, 17, 27, 21]。去重已經(jīng)被廣泛用于很多商業(yè)化的系統(tǒng)如 Dropbox [3]，EMC [36]，等等。許多Peer-to-Peer (P2P) 系統(tǒng)也使用同樣的技術(shù)來節(jié)省存儲(chǔ)空間 [52, 53, 5, 6].

但是去重卻是和數(shù)據(jù)加密的目標(biāo)直接相矛盾的。為什么這么說呢呢?這是由于加密本身的性質(zhì)和目標(biāo)造成的。人類使用加密手段來保護(hù)數(shù)據(jù)的安全已經(jīng)有上千年的歷史了，最早的密碼可以追溯到公元前1900年的埃及古王國時(shí)期。近代，尤其是兩次世界大戰(zhàn)中各方的斗法極大地推動(dòng)了密碼學(xué)的發(fā)展。步入計(jì)算機(jī)時(shí)代，密碼學(xué)更是如虎添翼。90年代興起的互聯(lián)網(wǎng)，特別是迅猛發(fā)展電子商務(wù)，既對(duì)密碼技術(shù)提出了更高的需求(從而進(jìn)一步推動(dòng)了它的發(fā)展)，也使得密碼技術(shù)應(yīng)用到人們生活的各個(gè)方面。今天，從網(wǎng)上銀行到在線購物，從電子郵件到社交網(wǎng)絡(luò)甚至游戲，密碼技術(shù)無處不在。

然而，人們對(duì)密碼安全性的認(rèn)識(shí)卻是直到80年代才有了實(shí)質(zhì)性的進(jìn)展。在此之前，人們對(duì)密碼安全性的目標(biāo)缺乏嚴(yán)格的定義，從而缺乏對(duì)其度量的尺度。一個(gè)加密算法到底怎樣才算是安全的?這個(gè)貌似簡單的問題其實(shí)需要非常深刻的對(duì)密碼本質(zhì)的思考。加密算法不是孤立地，它會(huì)被使用在不同的環(huán)境和條件下。密碼學(xué)家期望能夠?qū)用芩惴ǖ男再|(zhì)做出精確的刻畫和嚴(yán)格的證明，從而避免在數(shù)據(jù)安全上出現(xiàn)百密一疏的漏洞。這一點(diǎn)非常不容易做到，它不僅僅取決于人們對(duì)密碼本質(zhì)的理解，還依賴相關(guān)學(xué)科(例如信息論等)的發(fā)展。

1.1 Information-theoretic Security

1949年，信息論的創(chuàng)始人Claude Shannon從信息論的角度考察密文所泄露的關(guān)于原文的信息，提出了information-theoretic security的概念。

簡單地講，一個(gè)具有information-theoretic security的加密算法所產(chǎn)生的密文對(duì)于一個(gè)沒有相應(yīng)秘鑰的人來說，不含有任何關(guān)于原文的信息。

這一性質(zhì)的后果是，即使對(duì)手擁有無限的計(jì)算能力和時(shí)間，也不可能破譯。這顯然是一個(gè)極強(qiáng)的概念，但是在實(shí)際中很難使用，因?yàn)樗笫褂煤驮拈L度一樣的隨機(jī)秘鑰，并且每一個(gè)秘鑰只能使用一次。滿足這種性質(zhì)的加密算法只有一種，就是One-time pad(OTP)。

現(xiàn)實(shí)中OTP是不可能實(shí)用的，人們很難安全地分發(fā)和原文長度一樣的秘鑰。于是人們退而追求computational secrecy。即，我們假設(shè)對(duì)手的計(jì)算能力是有限的，我們的加密算法只要做到對(duì)手在可行的時(shí)間內(nèi)無法破譯就可以認(rèn)為是安全的。在這種模式下，我們需要一個(gè)新的方式來度量密文所泄露的信息。

1.2 Semantic Security

1982年，當(dāng)時(shí)還正在UC Berkeley讀研究生的Shafi Goldwasser和Silvio Micali [39] 提出了semantic security的概念。

這一概念的闡述可以基于比較兩個(gè)事件的概率：

1. 給定一個(gè)密文，和原文的長度，一個(gè)polynomial-time的對(duì)手從中算出關(guān)于原文的任何部分信息(如原文是奇數(shù)還是偶數(shù));

2. 只基于原文的長度(沒有密文)，任何一個(gè)polynomial-time算法從中算出關(guān)于原文的任何部分信息。

如果1和2的概率足夠接近，則該加密算法被認(rèn)為滿足semantic security。我們試著來理解一下這個(gè)定義。在1的情況，對(duì)手拿到密文和原文的長度，在2的情況下，對(duì)手只拿到原文的長度，完全沒有密文。如果這兩個(gè)情況下對(duì)手成功獲得原文信息的概率接近的話，說明該加密算法產(chǎn)生的密文不足以使之從中獲取任何關(guān)于原文的信息，因?yàn)橛兴蜎]它差別不大。這顯然是一個(gè)安全的狀態(tài)。

稍后Goldwasser和Micali又給出了一個(gè)基于密文不可區(qū)分性，即ciphertext indistinguishability (IND) [40]，的等價(jià)定義。IND的意思是，給定從兩個(gè)原文m0和m1中隨機(jī)選擇一個(gè)進(jìn)行加密后產(chǎn)生的密文，對(duì)手不能區(qū)分加密的是哪一個(gè)。后者因?yàn)楦菀资褂枚粡V泛采納。

這是一個(gè)里程碑性的工作，它賦予安全性明確嚴(yán)格的數(shù)學(xué)定義，使得密碼的設(shè)計(jì)和分析都有了明確的方向，它的意義是如何強(qiáng)調(diào)也不過分的。正如ACM對(duì)兩位的評(píng)價(jià)，他們的工作“helped make cryptography a precise science。”部分由于他們的這一開拓性的工作，兩位作者在30年后(2013年)獲得圖靈獎(jiǎng)(ACM Turing Award)。

2. 云存儲(chǔ)系統(tǒng)中的去重與加密

回到云存儲(chǔ)的應(yīng)用中來，云存儲(chǔ)系統(tǒng)中使用支持去重的加密問題的主要挑戰(zhàn)有兩點(diǎn)：

1). 加密之后的密文需要保留原文的冗余，即原文相同的數(shù)據(jù)塊加密后的密文仍相同(這里的相同不一定是密文的全等，系統(tǒng)只要一種識(shí)別包含相同內(nèi)容的密文的手段即可)，這樣去重才能夠起作用。

2). Cross-user decryption (CUD)，即由某個(gè)用戶加密上傳的數(shù)據(jù)塊應(yīng)該能夠被所有有讀取權(quán)限的用戶解密，即使后者不是最初的上傳和加密者。

2可以用“lockbox”或者key encapsulation 的方式解決 [22, 45, 29]，在此不再贅述。而1所需的特性我們稱之為convergent特性，它是基于去重的數(shù)據(jù)壓縮不可或缺的。但是，它與加密算法的安全性定義有不可調(diào)和的矛盾。Semantic security明確禁止原文相等性的檢測，即給定兩個(gè)密文，不應(yīng)該能夠允許對(duì)手?jǐn)喽ㄋ鼈兗用艿氖欠袷峭瑯拥臄?shù)據(jù)，否則對(duì)手可以利用這一性質(zhì)攻破前述IND。可以明確斷言的是，滿足現(xiàn)代加密算法安全性(如semantic security)的所有加密算法都不支持去重。

3. Convergent Encryption (CE)及其安全性

于是退而求其次，即，我們可以適度放寬對(duì)安全性的要求，允許密文泄露原文相等性信息，從而使加密后的去重成為可行。最早提出的方案是Convergent Encryption (CE) [27]。它的想法非常簡單：一個(gè)數(shù)據(jù)塊d的加密如下：

E(h(d), d)

其中E(key, d)是以key做秘鑰加密數(shù)據(jù)d的對(duì)稱加密算法，h(x)是一個(gè)hash function。也就是說， 當(dāng)需要加密一個(gè)數(shù)據(jù)塊d的時(shí)候，CE先用數(shù)據(jù)內(nèi)容生成key，再用一個(gè)symmetric encryption算法(如AES等)加密。

嚴(yán)格地講，symmetric encryption加密算法本身通常都是randomized或者stateful，即除了key之外，算法本身會(huì)生成一些隨機(jī)數(shù)(例如Initialization vector或IV)，或者維護(hù)一個(gè)計(jì)數(shù)器之類的狀態(tài)，這樣即使多次加密同樣的信息也會(huì)有不同的結(jié)果，目的還是為了獲得類似semantic security這樣的安全性。這里CE的做法可以理解為h(x)輸出的一部分作為key，另外一部分作為算法所需的隨機(jī)數(shù)(如IV)。這樣做的結(jié)果是，不管是哪個(gè)用戶加密，同樣的數(shù)據(jù)塊一定會(huì)被加密成同樣的密文，后續(xù)可以做去重了。CE已經(jīng)被廣泛應(yīng)用于很多研究[14, 7]和商業(yè)系統(tǒng)中比如Freenet [5], GNUnet [6], flud [4], Ciphertite [2], Bitcasa[1]等。

但是一個(gè)令密碼學(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]。他們同時(shí)提出了PRV$-CDA的安全性概念，并證明了PRV$-CDA比其他相關(guān)的安全性都更強(qiáng)。簡單地地講，MLE是這樣一種加密算法，它使用的key是從待加密的原文算出來的(key used for encryption is derived from the message itself)。CE是MLE的一個(gè)特例。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意味著對(duì)手不能夠?qū)⒚芪耐c密文同樣長度的隨機(jī)數(shù)區(qū)分開來。具體的定義這里不在贅述，感興趣的讀者可參看 [13]。

這是一個(gè)相當(dāng)強(qiáng)的定義。在應(yīng)用于MLE時(shí)，必須對(duì)待加密的數(shù)據(jù)有所限制才能達(dá)到。簡單講，數(shù)據(jù)本身必須有足夠大的最小熵(min-entropy)，亦即數(shù)據(jù)必須是不可預(yù)測的，否則達(dá)不到PRV$-CDA的安全性。min-entropy是衡量一個(gè)隨機(jī)變量的不可預(yù)測性的度量，具體定義可參看相關(guān)文獻(xiàn)。例如，如果待加密的數(shù)據(jù)只有“進(jìn)攻”和“撤退”兩個(gè)可能的話(數(shù)據(jù)分布的不可預(yù)測性很低)，則對(duì)手可以很容易地破解一個(gè)MLE(只要將所有可能的原文都加密，和欲破解的密文相比即可)。

4. Convergent Encryption的弱點(diǎn)

在MLE的框架下，CE被證明滿足PRV$-CDA安全性 [13]。這是一個(gè)有重大意義的成果，人們終于能夠準(zhǔn)確刻畫一個(gè)已經(jīng)被廣泛使用的技術(shù)的安全性了。萬事大吉了嗎?NO!至少還剩下兩個(gè)問題：

1. PRV$-CDA安全性對(duì)于存儲(chǔ)系統(tǒng)來說是否足夠強(qiáng)?

2. 是否還有可能獲得比PRV$-CDA更強(qiáng)的安全性?

對(duì)1，我們的判斷是否定的。首先，我們知道，MLE只能保護(hù)具有比較高的不可預(yù)測性的數(shù)據(jù)。而在云存儲(chǔ)系統(tǒng)的實(shí)際使用中，很多用戶數(shù)據(jù)恰恰是可預(yù)測。比如說很多公司的文檔都有共同的模板和格式，這可能導(dǎo)致有些數(shù)據(jù)塊只可能有很少的取值可能。其次，即使數(shù)據(jù)的不可預(yù)測性很高，對(duì)手仍然可以很容易地驗(yàn)證一個(gè)信息：判斷給定的密文是否加密了一個(gè)來自于一個(gè)不大的集合的數(shù)據(jù)。只要將該集合內(nèi)的所有元素分別加密后與給定密文比較即可。在很多情況下，這一信息可能是非常嚴(yán)重的泄露。例如，云存儲(chǔ)的提供商可以很容易判斷一個(gè)用戶的加密數(shù)據(jù)中是否包括某些受版權(quán)保護(hù)的電影。

對(duì)于第二個(gè)問題，最新的研究給出的答案是肯定的。我們的CCSW’14工作指出，所有的CE或MLE，有一個(gè)關(guān)鍵的特性是public encryption，即任何一個(gè)人，只要拿到數(shù)據(jù)，就可以生成合法的密文。所有public encryption的MLE的安全都依賴于數(shù)據(jù)本身的隨機(jī)性，再加上MLE允許equality checking，這就決定了MLE只能保護(hù)具有足夠大的min-entropy的數(shù)據(jù)這一局限性。PRV$-CDA的定義對(duì)數(shù)據(jù)分布做了明確的限制。那么這種局限是否可以突破呢?答案是肯定的。MLE之所以采取public encryption的模式，是考慮到不同的用戶需要獨(dú)立地完成數(shù)據(jù)加密，并且需要同樣的數(shù)據(jù)產(chǎn)生同樣的密文。

完成這一目標(biāo)還可以采用另外一種server assisted模式。即引入一個(gè)第三方的服務(wù)，該服務(wù)協(xié)助用戶生成加密所需要的數(shù)據(jù)(key和IV等)，并保證去重所需要的convergent特性。引入一個(gè)第三方的服務(wù)的好處是，該服務(wù)可以使用所有用戶都不知道的秘密數(shù)據(jù)(比如另外一個(gè)key)。這就意味著加密過程不再是公開的，從而杜絕前面提到過的問題。DupLESS [12]和我們最新的工作都是這方面的思路。

5. Encryption with Signature(EwS)及其安全性

我們在加密過程中如何引入額外的秘密且同時(shí)保證密文的convergent特性呢?和MLE的思路類似，我們需要由數(shù)據(jù)產(chǎn)生加密的key(從而保證convergent特性)，而我們不希望這一個(gè)過程是公開的。一個(gè)辦法是，由第三方服務(wù)用自己的秘鑰對(duì)數(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的方式分布式地存儲(chǔ)于各個(gè)用戶。SE是一個(gè)symmetric encryption算法(如AES)。也就是說，EwS先對(duì)數(shù)據(jù)進(jìn)行簽名，然后用簽名生成加密的key。只要使用的簽名算法是deterministic的，則每一個(gè)數(shù)據(jù)塊都會(huì)被加密成唯一的密文。

那么這種方法獲得的安全性是什么樣的呢?我們的論文給出了這個(gè)問題的答案。我們提出了一個(gè)新的安全性概念，稱為D-IND$并證明D-IND$-CPA嚴(yán)格強(qiáng)于(strictly stronger than)PRV$-CDA。與PRV$-CDA類似，D-IND$也意味著對(duì)手不能夠?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)攻”和“撤退”兩個(gè)可能的話，則對(duì)手可以很容易地破解一個(gè)CE。但是如果數(shù)據(jù)是用EwS的加密的，則這種攻擊不再可能，因?yàn)閷?duì)手沒有第三方服務(wù)用來簽名的秘鑰。

與DupLESS [12]相比，我們的方案還有一個(gè)優(yōu)勢就是它是分布式的。它不需要第三方的服務(wù)，可以直接將服務(wù)部署在用戶中。它巧妙使用了threshold signature這一工具。Threshold signature是一種分布式的數(shù)字簽名生成技術(shù)，它將簽名所用的秘鑰分布地存儲(chǔ)于多個(gè)節(jié)點(diǎn)，使得任何小于t個(gè)節(jié)點(diǎn)聯(lián)合起來，既不能夠計(jì)算出簽名的秘鑰，也不能夠生成正確的簽名。相反任何大于t個(gè)節(jié)點(diǎn)聯(lián)合起來就能夠生成正確的簽名。其中t是一個(gè)系統(tǒng)參數(shù)。這一特性使得threshold signature既具有更高的安全性，也有更好的容錯(cuò)能力。用在EwS上，簽名的秘鑰不再有單一個(gè)服務(wù)器維護(hù)，它會(huì)分布在所有用戶中。當(dāng)一個(gè)用戶需要加密時(shí)，他向大于t個(gè)其他用戶發(fā)出請求，在足夠多的用戶的協(xié)助下生成簽名，再使用EwS方式加密。

我們還證明了，EwS，不論是單機(jī)的還是分布式的，僅僅泄露數(shù)據(jù)相等的信(message equality)。而該信息是目前去重手段所依賴的，這表明EwS是支持去重條件下所能達(dá)到的最強(qiáng)的安全性。

6. 結(jié)論

綜上，存儲(chǔ)系統(tǒng)中去重和加密是一對(duì)矛盾的需求，要支持去重的話必須降低對(duì)加密算法安全性的要求。我們提出了D-IND$的安全性概念并證明了D-IND$強(qiáng)于目前所有的相關(guān)安全性定義。同時(shí)又證明了D-IND$是支持去重的加密算法所能達(dá)到的最強(qiáng)的安全性。那么問題來了，這樣的安全性是否足夠?特別是，為了支持去重而不得不泄露的數(shù)據(jù)相等性信息對(duì)用戶來講是否可以接受?

如何衡量和控制這種泄露?這些都是后續(xù)待研究的問題。