張小龍

摘 要：我們描述了一種新的方法建立一個安全和容錯在協(xié)同工作環(huán)境和數(shù)據(jù)存儲服務(wù)，以完美的秘密共享方案來存儲數(shù)據(jù)。由于較高的計算開銷，完美的秘密共享方案已發(fā)現(xiàn)很少使用在管理通用數(shù)據(jù)上了。為此我們提出的方法使用了一種新的建立在異或（XOR）算法上的新型加密方式，從而大大降低計算開銷。秘密共享再加上復(fù)制機(jī)制所形成的一個系統(tǒng)機(jī)制是一個不錯的方案，它可以通過改變自身的一些性質(zhì)，從而達(dá)到平衡各個指標(biāo)的功能。我們評估所提出的框架的屬性和性能，并顯示完美的秘密共享和復(fù)制相結(jié)合，可以用來建立高效的容錯和安全的分布式數(shù)據(jù)存儲系統(tǒng)。

關(guān)鍵詞：拜占庭容錯;協(xié)同環(huán)境;機(jī)密性;分布式數(shù)據(jù)存儲;復(fù)制;秘密共享

中圖分類號： TP333 ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ?文章編號： 1673-1069（2017）01-146-3

1 ?概述

無論是從加密秘鑰還是通用數(shù)據(jù)，敏感數(shù)據(jù)的存儲已經(jīng)在不同的環(huán)境中被人們廣泛探討和研究。本文認(rèn)為，為了實(shí)現(xiàn)存儲敏感數(shù)據(jù)的安全性，敏感數(shù)據(jù)必須存儲在分布式的服務(wù)器上，并且要保證數(shù)據(jù)的一致性和正確性，即使一臺或者多臺機(jī)器被攻破，數(shù)據(jù)仍然可以保持正確性。傳統(tǒng)的解決方案是：把要保護(hù)的敏感數(shù)據(jù)進(jìn)行加密，并且通過做復(fù)制處理來實(shí)現(xiàn)系統(tǒng)容錯。這種解決方案的好處在于可以計算量小，并且節(jié)省空間。但是在分布式的環(huán)境中，會有多個用戶同時有權(quán)限來得到數(shù)據(jù)，為了保證每個用戶的數(shù)據(jù)安全，那么他們每個人必須擁有一個可以解密數(shù)據(jù)的密鑰。這些密鑰也必須存在于服務(wù)器中，這就很占空間了。并且為了防止秘密鑰匙的泄漏，秘密鑰匙往往還要額外加密，這樣就增加了額外開銷。本文要提出的解決方案就是“秘密共享”方法。

2 ?秘密共享機(jī)制

秘密共享方案是這樣的技術(shù)，其中秘密被編碼成幾個片段，稱為共享在完全秘密共享方案中，共享的無效組合不給出關(guān)于編碼秘密的信息，只有當(dāng)用戶成功得到所有正確的共享組合，原始信息才會被得到。因此，完美的秘密共享方案是信息理論安全的。完美的秘密共享方案還允許共享更新，這是分布式改變共享的過程，使得編碼的秘密是相同的。頻繁的共享單元更新可以提供強(qiáng)大的數(shù)據(jù)保密性。通過將這些共享存儲在不同的服務(wù)器，只要沒有足夠的服務(wù)器被破壞，編碼數(shù)據(jù)就會是安全的。保密性在沒有任何額外加密的情況下實(shí)現(xiàn)，因此避免了對附加密碼密鑰的存儲和管理的需要。完美的秘密共享方案具有可以分布地改變或“更新”共享單元的附加屬性，使得編碼數(shù)據(jù)仍然保持相同。這種共享更新的過程，經(jīng)常執(zhí)行時，可以提供強(qiáng)大的數(shù)據(jù)機(jī)密性。這種方案的安全性取決于對手在兩次連續(xù)的共享更新之間的時間內(nèi)無法攻破足夠數(shù)量的服務(wù)器。

傳統(tǒng)方法具有的缺點(diǎn)是加密數(shù)據(jù)的安全性僅僅依賴于保持密鑰的保密性。對手可以通過系統(tǒng)中其他地方的漏洞找到關(guān)鍵，例如在客戶端使用的應(yīng)用程序中偷取用戶密碼。向?qū)κ直┞都用苊荑€將會泄露所有敏感數(shù)據(jù)。我們提出的克服這個缺點(diǎn)的方法是使用完美的秘密共享來存儲敏感信息本身。此外，向?qū)κ止_一些敏感數(shù)據(jù)仍然不會影響存儲在存儲服務(wù)處的其余敏感數(shù)據(jù)的機(jī)密性。然而，與私鑰加密方案不同，大多數(shù)完美的秘密共享方案在計算上是昂貴的?？沈?yàn)證的秘密共享方案通常與完美的秘密共享方案一起使用以檢測可能由故障或泄密的服務(wù)器返回的不正確的共享，并且還在寫入期間檢測不正確的秘密共享。這樣的技術(shù)進(jìn)一步增加了在數(shù)據(jù)的編碼和解碼期間的計算時間。

為了解決這一問題我們可以使用XOR秘密共享進(jìn)行快速計算，并且使用基于復(fù)制的方案來檢測故障或惡意服務(wù)器可能返回的不正確的共享，來解決這些問題。這種秘密共享和復(fù)制的組合形成了一個架構(gòu)框架，其中服務(wù)器以矩形或網(wǎng)格的形式布置。所提出的架構(gòu)框架，我們稱之為GridSharing，它具有有用的屬性，那就是其維度可以變化以折中幾個性能度量。在協(xié)作環(huán)境的分布式系統(tǒng)中，可以想象到被授權(quán)讀取或更新敏感數(shù)據(jù)的客戶是不斷變化的。當(dāng)使用傳統(tǒng)方法時，訪問列表的改變將需要用新的加密密鑰重新加密所存儲的數(shù)據(jù)，這可能是麻煩的。對于細(xì)粒度的訪問列表管理，存儲在數(shù)據(jù)存儲服務(wù)處的每個文件或文檔將需要唯一的密鑰。鍵的數(shù)量可能變得很大并且難以管理。如果敏感數(shù)據(jù)本身使用秘密共享技術(shù)存儲，則避免在訪問列表中的改變期間的這種昂貴的操作，這就是筆者在本文中要提到的基于XOR操作的秘密共享機(jī)制。

3 ?XORGridSharing機(jī)制、復(fù)制和投票機(jī)制

完美共享機(jī)制可以通過用XOR位操作來加以實(shí)現(xiàn)。如果每個數(shù)據(jù)位被認(rèn)為是單獨(dú)的秘密，則每個共享是單個位，并且q個共享（或q個位）的異或給出編碼的秘密位。如果想得到原始的未加密數(shù)據(jù)，只需要反向操作，將加密位和所有的共享進(jìn)行XOR操作，這樣就得到了原始數(shù)據(jù)。非原始數(shù)據(jù)的共享位可以隨機(jī)產(chǎn)生，并把它們存儲起來，以備以后使用。在實(shí)踐中，為了效率，可以用字寬操作來實(shí)現(xiàn)XOR秘密共享。注意XOR秘密共享也是一個完美的選擇共享方案。與具有k<q的一般（k，q）閾值方案相比的唯一約束是必須重新得到所有q個分量以重構(gòu)秘密。由于計算簡單，XOR秘密共享的計算時間要低得多。

為了檢測在讀取期間可能由惡意服務(wù)器返回的不正確的共享，我們建議每個共享在足夠的服務(wù)器上被復(fù)制，使得如果至少一個閾值的服務(wù)器在讀取期間返回相同的共享，則該共享是正確的，并且可以用于秘密恢復(fù)計算。這是用于管理復(fù)制數(shù)據(jù)的傳統(tǒng)技術(shù)，我們應(yīng)用于每個共享。如果惡意服務(wù)器的數(shù)量用b表示，則對于每個共享，必須至少（2b+1）個響應(yīng)被接收。至少（b+1）臺服務(wù)器返回的值是正在讀取的共享的正確值。

總結(jié)，完美的秘密共享方案可以用于容錯和安全的分布式數(shù)據(jù)存儲，通過將它們與可驗(yàn)證的秘密共享方案相結(jié)合。使用Rijndael的計算能力作為基準(zhǔn)，我們已經(jīng)知道，眾所周知的可驗(yàn)證秘密共享技術(shù)，如費(fèi)爾德曼方案與Shamir方案的組合太慢，無法用于大量數(shù)據(jù)。通過使用（q，q）完美秘密共享方案（即，XOR秘密共享）以及復(fù)制和表決機(jī)制，可以大大減少計算開銷。

4 ?服務(wù)器故障類型分析

由于我們的數(shù)據(jù)存儲服務(wù)必須為存儲的數(shù)據(jù)提供可用性、完整性和機(jī)密性保證，因此我們確定以下三種類型的服務(wù)器故障：

崩潰故障：如果服務(wù)器停止執(zhí)行所有計算，并且既不發(fā)送也不接收網(wǎng)絡(luò)上的消息，則說服務(wù)器崩潰。

拜占庭故障（Byzantine）：拜占庭式故障服務(wù)器可以任意偏離其指定的協(xié)議。拜占庭式故障服務(wù)器還可以向入侵者（黑客）顯示存儲在本地的共享及其內(nèi)部狀態(tài)。

僅泄漏故障：如果服務(wù)器能夠向入侵者（黑客）揭示其共享和狀態(tài)，但是忠實(shí)地執(zhí)行其指定的協(xié)議，則服務(wù)器被認(rèn)為表現(xiàn)出泄漏故障。

所提出的故障模型允許對存儲服務(wù)的可用性、完整性和保密性的直接推理。在可用性攻擊（例如拒絕服務(wù)攻擊）中，可用于服務(wù)的合法使用的資源受限于例如限制網(wǎng)絡(luò)帶寬和通過增加服務(wù)器負(fù)載。崩潰故障是更嚴(yán)重的攻擊形式，其中服務(wù)器完全和永久地停止執(zhí)行。能夠容忍大量崩潰故障的存儲服務(wù)也是高度可用的存儲服務(wù)，并且將能夠更大程度地容忍拒絕服務(wù)攻擊。在我們考慮的存儲服務(wù)模型中，完整性攻擊可能包括損害服務(wù)器和改變其行為或損害服務(wù)器，以及任意修改存儲在其中的共享。這種攻擊由拜占庭錯誤表示。只有通過折中服務(wù)器獲取足夠的共享，才能啟動保密攻擊，因?yàn)槲覀儍H關(guān)注共享分配問題，而不是實(shí)際協(xié)議。這些是由拜占庭和僅漏泄故障建模的。

我們對三種類型的故障中的每一種使用閾值故障模型。我們假設(shè)不超過c個服務(wù)器可能崩潰，不超過b個服務(wù)器可以是拜占庭故障，并且不超過l個服務(wù)器可以顯示僅漏泄故障。

5 ?秘密共享和復(fù)制的組合

我們的容錯和安全數(shù)據(jù)存儲服務(wù)的方法是使用完美的閾值秘密共享來實(shí)現(xiàn)數(shù)據(jù)機(jī)密性，并使用基于復(fù)制的機(jī)制來管理每個共享以實(shí)現(xiàn)崩潰和拜占庭容錯。

5.1 直接方法

直接方法：服務(wù)器被布置在具有（1+b+1）行的邏輯網(wǎng)格中，每行中至少有（3b+c+1）個服務(wù)器。秘密共享跨行完成，并為每一行分配一個不同的共享。共享沿行復(fù)制。（見圖1）我們首先描述一種使用這種方法的簡單方法，稱為直接方法，并且表明它需要大量的存儲服務(wù)器。然后我們介紹GridSharing框架，其中實(shí)現(xiàn)所需的服務(wù)器數(shù)量和每個服務(wù)器所需的存儲空間之間的折中。這是一個值得應(yīng)用的折中，因?yàn)榇鎯臻g更加少且有效。

<E：＼123＼中小企業(yè)管理與科技·上旬刊201701＼1-197＼63-1.jpg>

圖1

我們有興趣在N個存儲服務(wù)器設(shè)計一個共享分配方案，其中不超過l個服務(wù)器可能是泄漏一直有故障，不超過b個服務(wù)器可能是Byzantine故障，并且不超過c個服務(wù)器可能崩潰。對此的直接解決方案是使用（1+b+1，l+b+1）閾值完全秘密共享方案。每個共享都分配給一組不同的x服務(wù)器。該設(shè)置可以被設(shè)想為以具有（1+b+1）行和x列的邏輯網(wǎng)格的形式布置的N個服務(wù)器，如圖1所示。

同一行中的服務(wù)器存儲相同的共享。共享的復(fù)制用于實(shí)現(xiàn)崩潰和拜占庭容錯。使用秘密共享實(shí)現(xiàn)數(shù)據(jù)機(jī)密性。秘密共享跨行完成。因此，需要（l+b+1）行，每個共享被分配給不同的行。任何（1+b）服務(wù)器的折中將僅給對手一個（l+b）份額，但是需要全部（l+b+1）份額來恢復(fù)該秘密。

當(dāng)讀寫秘密時，使用基于復(fù)制的協(xié)議讀取和寫入共享。為了這個和隨后的分析的目的，我們假設(shè)以下簡單的復(fù)制協(xié)議。為了寫秘密S，用戶生成（1+b+1）份額，使得它們

的按位異或給出秘密S用戶向每個服務(wù)器寫入其分配的份額。因此，在圖1所示的示例中，用戶將向行1中的每個服務(wù)器寫入共享s1，向行2中的每個服務(wù)器寫入共享s2等。

當(dāng)秘密S將在稍后被讀取時，相同的用戶或不同的用戶將需要僅聯(lián)系一些服務(wù)器集合以讀取所有共享?？紤]在我們的示例中如何讀取共享s1。共享s1存儲在由x個服務(wù)器組成的行1中。用戶需要僅聯(lián)系（2b+1）個這些服務(wù)器以確定s1，因?yàn)橹挥凶疃嗟腷個服務(wù)器可能是拜占庭故障。至少（b+1）臺服務(wù)器返回的共享s1必須由至少一個不是拜占庭式故障的服務(wù)器返回，因此應(yīng)該是正確的。用戶必須至少獲得（2b+1）對命令s1的響應(yīng)，但是最多（c+b）個服務(wù)器可能無法返回任何響應(yīng)。假設(shè)客戶端通過異步網(wǎng)絡(luò)連接到服務(wù)器，使得它們無法檢測到服務(wù)器故障，則每個共享必須至少寫入（（2b+1）+（c+b））=（3b+c+1）服務(wù)器，以便在系統(tǒng)中存在b拜占庭故障和c崩潰故障時成功讀取。

因此，每個共享必須存儲在至少（3b+c+1）個服務(wù)器上。因此，x=（3b+c+1），其給出N≥（1+b+1）（3b+c+1）。請注意，寫入和讀取的給定描述僅是用于管理共享的可能的基于復(fù)制的協(xié)議的方法。我們忽略了使用所有共享單元共有的時間戳的需要。所有共享必須作為單個寫操作的一部分寫入。

所描述的方法僅足以導(dǎo)出存儲每個共享所需的服務(wù)器數(shù)量的下限。該下限將基于對系統(tǒng)模型的假設(shè)和要實(shí)現(xiàn)的讀寫選擇的種類而改變。維護(hù)每個共享所需的最小服務(wù)器數(shù)量是框架設(shè)計中唯一取決于復(fù)制協(xié)議及其基本假設(shè)的選擇。

因此，為了容忍l個泄漏故障，b個拜占庭故障和c個崩潰故障，這種方法需要至少（1+b+1）（3b+c+1）個服務(wù)器。對于l=b=c=2，需要至少45個服務(wù)器。也就是說，只有高達(dá)6/45=13.3%的服務(wù)器可能出現(xiàn)故障。這在所需的存儲服務(wù)器的數(shù)量方面是低效的。然而，每個服務(wù)器處的存儲器泄漏是一個，因?yàn)槊總€共享的大小與編碼的秘密的大小相同。此外，生成裸最小數(shù)量的共享，其是（1+b+1）。因此，在客戶端處的秘密共享（寫入）和秘密恢復(fù)（讀?。┢陂g的計算時間保持盡可能小。

5.2 GridSharing方法

<E：＼123＼中小企業(yè)管理與科技·上旬刊201701＼1-197＼63-2.jpg>

圖2

GridSharing框架：N個服務(wù)器排列在具有r行的邏輯網(wǎng)格中。秘密共享跨行完成，共享沿行復(fù)制。對于N=20，l=1，b=1和c=6所示的設(shè)置。注意每個服務(wù)器持有3個共享單元。（見圖2）

與直接方法類似，GridSharing框架由N個服務(wù)器組成，其中不超過c個服務(wù)器可以崩潰，不超過b個服務(wù)器可以是Byzantine故障，并且不超過I個服務(wù)器可以顯示僅漏泄故障。N個服務(wù)器以具有r行和N/r列的邏輯矩形網(wǎng)格的形式布置，其中為了簡化，假設(shè)N是r的倍數(shù)。該布置在圖2中示出。

同一行中的服務(wù)器存儲相同的共享。因此，實(shí)現(xiàn)了對崩潰和拜占庭故障的容忍。使用秘密共享實(shí)現(xiàn)數(shù)據(jù)機(jī)密性。秘密共享跨行完成。Ito等人的共享分配方案用于向行分配共享。

圖2給出了其中N=20個服務(wù)器被布置在具有r=4行的矩形網(wǎng)格中的示例。如果必須容忍b=1拜占庭故障和l=1個僅漏泄故障，假設(shè)秘密S被編碼成六個份（s1，s2，s3，s4，s5，s6），使得S=s1[+] s2[+] s3[+] s4[+] s5[+] s6。也就是說，秘密S中的每個比特是共享s1，s2，s3，s4，s5，s6中的相應(yīng)比特的異或：

第1行中的服務(wù)器獲取共享（s4，s5，s6）

第2行中的服務(wù)器獲取共享（s2，s3，s6）

第3行中的服務(wù)器獲取共享（s1，s3，s5）

第4行中的服務(wù)器獲取共享（s1，s2，s4）

在GridSharing的框架下，通過計算和分析，可以得出，該框架所需要的最小的服務(wù)器個數(shù)N與服務(wù)器GridSharing架構(gòu)的行數(shù)r，拜占庭錯誤b，泄漏錯誤l，崩潰錯誤c的關(guān)系如下兩個方程

N≥4b+l+c+1。

r≥3b+c+1

因此，當(dāng)行數(shù)r從（1+b+1）增加到（4b+1+c+1）時，所需的服務(wù)器的最小數(shù)量將減少。當(dāng)r=（4b+1+c+1）時，將會達(dá)到容忍b次拜占庭，c崩潰和l個僅漏泄故障所需的最小服務(wù)器數(shù)量。對于r>（4b+1+c+1），將只有一列，服務(wù)器數(shù)量N將與行數(shù)r相同，N將隨r增加。

6 ?結(jié)論

本文提出了一種在協(xié)作工作環(huán)境中實(shí)現(xiàn)安全和容錯數(shù)據(jù)存儲服務(wù)的新方法。我們的工作重點(diǎn)是：

①完美的秘密共享機(jī)制提供比基于加密的技術(shù)更強(qiáng)的安全性，并且促進(jìn)在協(xié)作工作環(huán)境中更容易地共享數(shù)據(jù)。

②可驗(yàn)證的秘密共享方案通常與完全秘密共享方案一起使用，以實(shí)現(xiàn)拜占庭容錯。但是顯示可驗(yàn)證的秘密共享方案招致大量的計算量，并且比Rijndael加密算法慢得多。

③我們使用（n，n）閾值完全秘密共享方案，即XOR秘密共享方案，用于機(jī)密性，并使用基于復(fù)制的協(xié)議來管理每個共享，用于拜占庭和崩潰容錯。與可驗(yàn)證的秘密共享方案相比，計算開銷大大減少，但需要每個服務(wù)器上的額外服務(wù)器和存儲容量。其中秘密恢復(fù)計算時間僅比Rijndael解密算法慢6至8倍的示例。

④我們提出了一個架構(gòu)框架，稱為GridSharing，其維度可以變化，以在所需的服務(wù)器數(shù)量和存儲溢出和秘密共享和恢復(fù)計算時間之間進(jìn)行權(quán)衡。該性質(zhì)被證明對于獲得不同故障閾值的最佳配置是有價值的。

⑤我們引入一個新的故障模型，包括崩潰，拜占庭和泄漏故障分析。我們相信這種新的故障模型將被證明對于分析容錯和安全領(lǐng)域中常見的作品是有用的。