无线Ad Hoc网络中高效广播加密机制的研究和评估

理论计算机科学电子笔记171（2007）57-69www.elsevier.com/locate/entcs无线Ad Hoc网络中通信效率高的广播加密机制Reza Curtmola1Seny Kamara2美国巴尔的摩约翰霍普金斯大学计算机科学系摘要由于其低通信成本，有状态广播加密是一个有吸引力的解决方案，在移动自组织无线网络（MANDO）的安全内容分发。不幸的是，MANNETWORK的固有限制阻止了这种方案的标准应用，因为它们要求接收机在线。在本文中，我们提出了一个可靠的消息传递机制的MANNETWORK，是基于纠删码，并利用节点的移动性，以实现非交互式恢复丢失的消息。 然后，我们将展示如何使用我们的机制来可靠地提供有状态广播加密方案的密钥更新。我们的解决方案有几个有用的属性：它允许在每个节点所需的存储量和消息恢复的速度之间进行权衡;并且它能够利用未经授权的节点的资源。我们通过仿真评估我们的方法的性能，并表明它具有高节点密度的网络实现了良好的性能。关键词：可靠的讯息传递，广播加密，金钥更新，储存，移动性，无线网路。1引言我们认为在移动自组织网络（MANDO），其中一个单一的源传播数据到一个动态变化的授权接收器组的安全内容分发的问题。在这种情况下，源和接收器是多跳自组织无线网络的移动节点的一部分。一种确保数据保密的简单方法（即，只有授权的用户子集能够恢复它），是源（在应用层）使用广播加密方案来在传输之前加密所有消息。这保证了即使所有用户都接收到加密数据，也只有授权的子集能够恢复内容。1电子邮件：crix@cs.jhu.edu2电子邮件：seny@cs.jhu.edu1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.11.00958R. Curtmola，S.卡马拉/电子笔记在理论计算机科学171（2007）57广播加密首先由Fiat和Naor [8]引入，此后在许多变体下进行了研究[19，11，10，27，26]。通常，广播加密方案分为有状态加密和无状态加密。无状态方案为用户提供在系统的整个生命周期中永远不会改变的长期密钥，而有状态方案提供可以在加入或撤销事件之后更新的密钥。虽然前者要求接收者在线以接收密钥更新消息，但一个简单的参数表明，在对数（以用户数计）数量的更新发生后，有状态方案通常比无状态方案实现更低的通信成本（参见附录A）。移动自组网的特性，包括低带宽、有损链路和移动性，使得部署广播加密具有挑战性，原因如下。在这样的网络中，有限的带宽强调了最小通信成本的重要性，并有利于使用有状态方案。然而，有状态广播加密的标准应用是不可能的，因为它要求接收器在线，这在移动性可能导致节点从网络中分区，因此在移动自组网中不能保证。在这项工作中，我们提出了一个可靠的消息传递机制，保证分区节点可以恢复丢失的消息在合理的时间内。直观地说，我们要求网络中的每个节点存储一条消息，并且我们利用节点移动性来允许分区节点在遇到指定数量的节点后恢复丢失的消息。我们的机制是基于纠删码，并具有允许消息恢复时间和节点存储之间的交易的优势。然后，我们将展示如何实现通信效率的安全内容分发在MANNETWORK使用有状态的广播加密方案提供了我们的可靠的消息传递机制。特别是，我们使用我们的机制，以可靠的方式提供该计划因此，我们能够保持的优势，在降低通信成本的来源，有状态的广播加密方案的优势，无状态的计划。除了通信效率之外，我们注意到，由于我们的可靠性机制独立于我们的安全内容分发机制（即，的基础广播加密方案），我们的解决方案有能力利用未经授权的节点的资源。换句话说，我们的内容分发方案的可靠性不仅随着授权用户的数量而提高，而且随着未授权用户的数量而提高。2相关工作可以使用交互式或非交互式方式来实现可靠的消息传递，这取决于客户端是否与源联系以检索丢失的消息。在ad hoc无线设置中，其特征在于相对较高的分组丢失和有限的带宽，交互式解决方案[20，29，31，23]是不期望的，因为增加的通信成本可能导致源处的分组内爆此外，如果节点被分区并且不能联系到R. Curtmola，S.卡马拉/电子笔记在理论计算机科学171（2007）5759中心为了避免这些可扩展性和连接性问题，在这项工作中，我们只考虑非交互式解决方案。这些交互式解决方案中的一些[28，29]使用前向纠错码来提高多播密钥更新的可靠性。在基于流言的可靠多播协议[6，16]中，多播组的成员主动地与随机选择的一组其他组成员交换关于组的“状态”的这允许丢失的数据包的概率恢复，代价是由重复的八卦消息交换引起的增加的流量此类协议尚未在安全框架内加以考虑。在[25]中提出并在[14]中改进的自愈密钥分发可以用于可靠地（非交互式地）向用户提供密钥更新自我修复方案允许错过t个连续更新的用户在t个错过的更新之前和之后接收一个更新时恢复它们。不幸的是，即使对于最有效的自愈方案[14]，更新的大小也是O（t·v），其中v是该方案可以处理的（被撤销用户的）最大联盟的大小由于t和v在系统初始化期间必须固定，因此通常必须选择较大的值，以便覆盖可能错过连续更新的最大周期，以及可能形成的最大可能的撤销节点联盟。GKMPAN [32，33]基于概率密钥预部署[7，34]，为ad hoc无线网络中的组密钥更新提供了可扩展且高效的机制。在系统设置期间，节点被预加载有从l个密钥的池中选择的m个对称密钥。这些密钥随后被相邻节点用于建立安全信道。当发生添加或撤销事件时，组管理器生成中间密钥并通过网络传播它。节点使用该中间密钥来更新组密钥和它们与任何被撤销的节点共享的密钥。由于任何两个节点都有很高的可能性存储至少一个共同的密钥，因此分区节点将可能能够从其邻居恢复丢失的更新。这项工作最接近我们的工作，因为错过更新消息的节点（例如，由于有损链路或网络分区）能够主要通过本地交互来恢复新的组密钥（节点可能需要联系密钥管理器的概率很低）。这种部分无状态特性使得GKMPAN对于在MANNETWORK中使用具有吸引力，特别是因为密钥更新具有较小的每个节点传输成本。虽然GKMPAN有几个理想的功能，我们在这项工作中采取的方法实现了新的和有用的属性。例如，由于我们的可靠性机制独立于我们的安全内容分发机制（即，的基础广播加密方案），我们可以利用不是授权组成员的节点的资源。我们的系统还允许分区节点确定地恢复任何任意（但固定）数量的丢失消息，而GKMPAN仅提供概率保证。此外，由于GKMPAN要求所有连接的节点在它们更新组密钥和它们的折衷密钥之后擦除中间密钥，因此在丢失的密钥更新消息之后重新加入网络的分区节点将永远不能更新其折衷密钥。作为60R. Curtmola，S.卡马拉/电子笔记在理论计算机科学171（2007）57λ因此，它与其邻居共享密钥（以及它可以建立安全信道来恢复丢失的更新）的概率将随着丢失消息的数量增加而降低最后，我们不假设节点的妥协是在有限的时间内检测到的。3预赛网络和安全模型。这项工作依赖于几个网络和安全假设。广播加密方案中的接收器是移动自组织网络中的节点。除了授权接收器的子集中的节点之外，网络还可以包含非授权节点，这些非授权节点可以使用它们的服务来提高内容分发服务的质量如果授权的接收器受到危害，攻击者将获得其凭证，并且将能够解密广播内容，直到检测到危害。我们假设存在网络层机制（例如，多播路由协议[22，9]），确保从中心到adhoc网络中特定节点组的高效消息传递我们还假设节点的通信和计算能力是有限的，但是它具有相对大的存储能力（例如，PDA可以存储多达几个MB）。删除码。擦除码[21，15，3]是一对（可能）概率算法C=（Encode，Decode）。发送方使用Encode算法将由l个符号组成的消息m编码为由λ个符号组成的码字c。 我们说C有最小距离d，如果它可以容忍多达d − 1个擦除，或者换句话说，如果接收器可以从c的任何λ−d + 1个符号中恢复m。一个码的速率是值ρ = l，我们说C是（λ，l，d）-擦除码，如果它将l个符号的消息编码成λ个符号的码字，并且具有最小距离d。注意符号可以是任何数据“单元”（例如，分组或比特），但是当将我们的构造应用于广播加密时，我们将假设符号是指定比特长度的块（详见第5节）。对于纠删码的若干示例，可以高效地进行编码和解码。特别地，Reed-Solomon[21]码可以在O（λ2）时间内编码和解码，Tornado码[15]在O（λ）时间内编码和解码（尽管Tornado码仅保证消息以高概率被恢复）。最后，我们注意到，纠删码容易受到污染攻击，这是拒绝服务攻击，对手引入无效的符号到解码过程中。然而，这种攻击可以通过使用蒸馏码来减轻[13]，代价是增加计算和通信开销。广播加密。我们互换使用术语源和中心来指传播内容的源。类似地，我们可以互换地表示接收R. Curtmola，S.卡马拉/电子笔记在理论计算机科学171（2007）5761内容作为用户或接收者。用户或者被授权（即，未被撤销并且被允许访问内容）或被撤销。我们使用撤销用户作为通用术语来表示不允许访问内容的用户。我们用N表示系统中的用户集合，G<$N表示授权用户集合，R=N\G对于被撤销的用户的集合。 假设n = |N|且r = n-|G|.设BE=（GBE，EBE，DBE）是有状态广播加密方案，并且（G，E，D）G G是对称加密方案。 用户与中心共享长期密钥。一广播加密方案利用会话密钥对每个消息进行加密，然后对会话密钥进行加密，使得只有未被撤销的用户能够基于他们的长期密钥对其进行解密。 具体来说，对于中心广播的消息m[EBE（K），EK（m）]，其中K是会话密钥，EBE（K）是封装的报头G G隔离会话密钥。 当比较广播加密方案，我们通常指的是这个头的大小。4可靠的消息传递在移动自组织网络中，由于网络分区或链路损耗，节点经常会丢失广播消息。一个可靠的消息传递机制使源以可靠的方式将消息传递到移动自组网中的所有节点。我们将主要关注这种机制的三个方面：可伸缩性、每个节点的存储和恢复时间。我们将可扩展性松散地定义为该机制我们首先回顾可靠消息传递的两种可扩展性和存储要求。然后，我们提出了我们的首选机制，它是高度可扩展的，并允许存储和恢复时间之间的权衡（即，所需的次数）。互动的方法。简单的可靠传递机制可以构造如下。内容分发源存储它发送的每条消息当错过消息的节点（因为它被分区或因为它是非线性的 它只是向源询问它错过的消息。 这种交互式解决方案显然是不可伸缩的，因为当网络规模很大时，源可能会被消息请求淹没。这也是有问题的，因为节点可能不能直接与源通信（例如，它可能在源的传输范围之外一种（朴素的）非交互式方法。一个简单的非交互式解决方案是要求每个从源接收消息的节点存储它。当一个错过消息的节点重新加入网络时，它可以向在广播期间连接的任何节点询问错过的消息。这种方法实现了最佳的恢复时间，62R. Curtmola，S.卡马拉/电子笔记在理论计算机科学171（2007）57节点只需要遇到单个节点就可以恢复消息。另一方面，它需要每个节点大量的存储，因为每个节点将必须存储r·q比特，其中r是由源广播的消息的数量，并且q是每个消息的大小。4.1我们的方法我们提出了一个非交互式的解决方案，但提供了一种方法，需要节点存储不到天真的非交互式方案。代价是断开连接的节点需要遇到多个节点才能恢复它们错过的消息。由于节点是移动的，重新加入的节点将遇到其他节点，因此以存储大小换取恢复时间似乎是合理的。非正式地，我们的方法是使用纠删码来编码由源广播的每个消息m。 在接收到码字时，每个节点将仅存储编码消息的“片段”，以便当节点重新加入网络时，它将能够在遇到指定数量的节点后恢复丢失的消息。我们注意到，在这种情况下，节点移动性是至关重要和有益的，因为遇到的节点越多，可以恢复的码字符号就越多，重新加入的节点将能够更快地重建消息。显然，节点不能存储源广播的每一条消息，我们只要求它们存储你的助手。在描述我们的可靠消息传递机制之前，我们首先介绍一些基本定义。 回想一下，N是网络中所有节点的集合。 在 每次步骤t≥1，源S广播消息mt。 设ON（t）=N，OFF（t）N是在线的节点的子集（即，连接）和邻苯二甲酸(i.e.、断开连接）。我们考虑以下情况。一个节点v∈OFF（t）在时间t是零，因此错过了mt。如果在时间t，J> t，v重新加入网络并且希望恢复m，t，我们假设它将开始遇到网络中的其它节点，特别是存储符号Ct的节点。此外，让μ是一个有限值，它决定了ON（t）中的每个节点将存储多少个时间步直觉上，我们可以认为μ决定了机制的内存，或者换句话说，系统将保证消息可恢复的时间步长的数量。所以如果v∈OFF（t）在某个时间tJ> t重新加入网络，则它将仅能够在以下情况下恢复mt：tJ μ，则擦除st−μ(ii) storest，y，wher ey←R [1，λ]。•如果在时间t，J> t，节点v∈OFF（t）希望恢复m，t，则它请求c，t的符号直到它具有足够的唯一符号来解码和恢复Mt。• 在执行后，vre-encodeisitanddstoressymb olst，y，其中y←R[1，λ]。由于对于每个消息m_t，节点需要存储码字c_t的至多一个符号，因此每个节点的总存储量至多为μ个符号。恢复单个消息。我们现在确定恢复单个丢失消息所需的预期遭遇次数为了充分理解我们的机制提供的（存储和重新加工时间之间的）权衡然而，在第5节中，我们固定了一个特定的代码，并在广播加密的背景下更精确地研究了交易。我们注意到，在我们的分析中使用的基本模型只近似一个MANET。令Store（mt，tJ）=N是在时间tJ> t存储符号ct=Encode（mt）的节点子集，并且令Rec（mt，tJ）=OFF（t）=Store（mt，tJ）是错过mt的广播的节点子集（即，它们在时间t时是O形的），但是，通过时间tJ> t恢复mt。因此Rec（mt，tJ）包括例如错过mt<给定一个节点v∈OFF（t）在时间tJ> t重新加入网络并希望恢复mt，我们想计算v为了恢复mt必须遇到的Store（mt，tJ）中的预期节点数的上限。根据定义，|为|ON（t）|+的|Rec（m t，t j）|≥| ON（t）|.|.由于ON（t）中的每个节点选择符号c t=（s t，1，. ，s t，λ）在范围内均匀分布，dom，则平均而言，在时间t，每个符号将被存储为|ON（t）|结毛皮-因此，由于ON（t）中的每个节点仅存储在最后μ时间步长中广播的消息的符号，因此在任何时间t tJ

下载后可阅读完整内容，剩余1页未读，立即下载