一种协同工作环境中（分布式）的容错和安全数据存储方法

张小龙

摘 要：我们描述了一种新的方法建立一个安全和容错在协同工作环境和数据存储服务，以完美的秘密共享方案来存储数据。由于较高的计算开销，完美的秘密共享方案已发现很少使用在管理通用数据上了。为此我们提出的方法使用了一种新的建立在异或（XOR）算法上的新型加密方式，从而大大降低计算开销。秘密共享再加上复制机制所形成的一个系统机制是一个不错的方案，它可以通过改变自身的一些性质，从而达到平衡各个指标的功能。我们评估所提出的框架的属性和性能，并显示完美的秘密共享和复制相结合，可以用来建立高效的容错和安全的分布式数据存储系统。

关键词：拜占庭容错;协同环境;机密性;分布式数据存储;复制;秘密共享

中图分类号： TP333            文献标识码： A            文章编号： 1673-1069（2017）01-146-3

1  概述

无论是从加密秘钥还是通用数据，敏感数据的存储已经在不同的环境中被人们广泛探讨和研究。本文认为，为了实现存储敏感数据的安全性，敏感数据必须存储在分布式的服务器上，并且要保证数据的一致性和正确性，即使一台或者多台机器被攻破，数据仍然可以保持正确性。传统的解决方案是：把要保护的敏感数据进行加密，并且通过做复制处理来实现系统容错。这种解决方案的好处在于可以计算量小，并且节省空间。但是在分布式的环境中，会有多个用户同时有权限来得到数据，为了保证每个用户的数据安全，那么他们每个人必须拥有一个可以解密数据的密钥。这些密钥也必须存在于服务器中，这就很占空间了。并且为了防止秘密钥匙的泄漏，秘密钥匙往往还要额外加密，这样就增加了额外开销。本文要提出的解决方案就是“秘密共享”方法。

2  秘密共享机制

秘密共享方案是这样的技术，其中秘密被编码成几个片段，称为共享在完全秘密共享方案中，共享的无效组合不给出关于编码秘密的信息，只有当用户成功得到所有正确的共享组合，原始信息才会被得到。因此，完美的秘密共享方案是信息理论安全的。完美的秘密共享方案还允许共享更新，这是分布式改变共享的过程，使得编码的秘密是相同的。频繁的共享单元更新可以提供强大的数据保密性。通过将这些共享存储在不同的服务器，只要没有足够的服务器被破坏，编码数据就会是安全的。保密性在没有任何额外加密的情况下实现，因此避免了对附加密码密钥的存储和管理的需要。完美的秘密共享方案具有可以分布地改变或“更新”共享单元的附加属性，使得编码数据仍然保持相同。这种共享更新的过程，经常执行时，可以提供强大的数据机密性。这种方案的安全性取决于对手在两次连续的共享更新之间的时间内无法攻破足够数量的服务器。

传统方法具有的缺点是加密数据的安全性仅仅依赖于保持密钥的保密性。对手可以通过系统中其他地方的漏洞找到关键，例如在客户端使用的应用程序中偷取用户密码。向对手暴露加密密钥将会泄露所有敏感数据。我们提出的克服这个缺点的方法是使用完美的秘密共享来存储敏感信息本身。此外，向对手公开一些敏感数据仍然不会影响存储在存储服务处的其余敏感数据的机密性。然而，与私钥加密方案不同，大多数完美的秘密共享方案在计算上是昂贵的。可验证的秘密共享方案通常与完美的秘密共享方案一起使用以检测可能由故障或泄密的服务器返回的不正确的共享，并且还在写入期间检测不正确的秘密共享。这样的技术进一步增加了在数据的编码和解码期间的计算时间。

为了解决这一问题我们可以使用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，其维度可以变化，以在所需的服务器数量和存储溢出和秘密共享和恢复计算时间之间进行权衡。该性质被证明对于获得不同故障阈值的最佳配置是有价值的。

⑤我们引入一个新的故障模型，包括崩溃，拜占庭和泄漏故障分析。我们相信这种新的故障模型将被证明对于分析容错和安全领域中常见的作品是有用的。