一種協同工作環境中（分布式）的容錯和安全數據存儲方法

張小龍

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

關鍵詞：拜占庭容錯;協同環境;機密性;分布式數據存儲;復制;秘密共享

中圖分類號： TP333 ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ?文章編號： 1673-1069（2017）01-146-3

1 ?概述

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

2 ?秘密共享機制

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

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

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

3 ?XORGridSharing機制、復制和投票機制

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

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

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

4 ?服務器故障類型分析

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

崩潰故障：如果服務器停止執行所有計算，并且既不發送也不接收網絡上的消息，則說服務器崩潰。

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

僅泄漏故障：如果服務器能夠向入侵者（黑客）揭示其共享和狀態，但是忠實地執行其指定的協議，則服務器被認為表現出泄漏故障。

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

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

5 ?秘密共享和復制的組合

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

5.1 直接方法

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

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

圖1

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

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

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

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

當秘密S將在稍后被讀取時，相同的用戶或不同的用戶將需要僅聯系一些服務器集合以讀取所有共享。考慮在我們的示例中如何讀取共享s1。共享s1存儲在由x個服務器組成的行1中。用戶需要僅聯系（2b+1）個這些服務器以確定s1，因為只有最多的b個服務器可能是拜占庭故障。至少（b+1）臺服務器返回的共享s1必須由至少一個不是拜占庭式故障的服務器返回，因此應該是正確的。用戶必須至少獲得（2b+1）對命令s1的響應，但是最多（c+b）個服務器可能無法返回任何響應。假設客戶端通過異步網絡連接到服務器，使得它們無法檢測到服務器故障，則每個共享必須至少寫入（（2b+1）+（c+b））=（3b+c+1）服務器，以便在系統中存在b拜占庭故障和c崩潰故障時成功讀取。

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

所描述的方法僅足以導出存儲每個共享所需的服務器數量的下限。該下限將基于對系統模型的假設和要實現的讀寫選擇的種類而改變。維護每個共享所需的最小服務器數量是框架設計中唯一取決于復制協議及其基本假設的選擇。

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

5.2 GridSharing方法

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

圖2

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

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

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

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

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

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

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

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

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

N≥4b+l+c+1。

r≥3b+c+1

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

6 ?結論

本文提出了一種在協作工作環境中實現安全和容錯數據存儲服務的新方法。我們的工作重點是：

①完美的秘密共享機制提供比基于加密的技術更強的安全性，并且促進在協作工作環境中更容易地共享數據。

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

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

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

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