一種協(xié)同工作環(huán)境中（分布式）的容錯(cuò)和安全數(shù)據(jù)存儲(chǔ)方法

張小龍

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

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

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

1 ?概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.1 直接方法

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

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

圖1

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

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

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

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

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

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

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

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

5.2 GridSharing方法

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

圖2

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

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

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

圖2給出了其中N=20個(gè)服務(wù)器被布置在具有r=4行的矩形網(wǎng)格中的示例。如果必須容忍b=1拜占庭故障和l=1個(gè)僅漏泄故障，假設(shè)秘密S被編碼成六個(gè)份（s1，s2，s3，s4，s5，s6），使得S=s1[+] s2[+] s3[+] s4[+] s5[+] s6。也就是說，秘密S中的每個(gè)比特是共享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的框架下，通過計(jì)算和分析，可以得出，該框架所需要的最小的服務(wù)器個(gè)數(shù)N與服務(wù)器GridSharing架構(gòu)的行數(shù)r，拜占庭錯(cuò)誤b，泄漏錯(cuò)誤l，崩潰錯(cuò)誤c的關(guān)系如下兩個(gè)方程

N≥4b+l+c+1。

r≥3b+c+1

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

6 ?結(jié)論

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

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

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

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

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

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