PaperlayerView exact revision on arXiv

Source-linked AI summary

Securing Dynamic Distributed Storage Systems against Eavesdropping and Adversarial Attacks

Sameer Pawar, Salim El Rouayheb, Kannan Ramchandran

arXiv:1009.2556v2cs.ITcs.CR

TL;DR

The paper asks how to secure dynamic distributed storage systems whose nodes fail and are repaired while an intruder observes or alters data over time. It derives capacity bounds for passive and active attacks, proves tightness in the bandwidth-limited regime, and supplies explicit codes that can identify a short list containing malicious nodes.

  • Problem

    The problem is securing dynamic distributed storage systems against eavesdropping and adversarial attacks during node failures and repairs.

  • Method

    The paper derives secrecy and resiliency capacity bounds and constructs capacity-achieving codes in the bandwidth-limited regime.

  • Results

    The bounds are tight in the bandwidth-limited regime, with explicit constructions for passive eavesdroppers and active adversaries.

  • Takeaways & Limitations

    The active-adversary schemes identify a list of at most 2b nodes guaranteed to contain the malicious nodes, enabling expurgation.

  • Takeaways & Limitations

    General capacity expressions and efficient decoding algorithms remain open problems.

Abstract

from arXiv · show

We address the problem of securing distributed storage systems against eavesdropping and adversarial attacks. An important aspect of these systems is node failures over time, necessitating, thus, a repair mechanism in order to maintain a desired high system reliability. In such dynamic settings, an important security problem is to safeguard the system from an intruder who may come at different time instances during the lifetime of the storage system to observe and possibly alter the data stored on some nodes. In this scenario, we give upper bounds on the maximum amount of information that can be stored safely on the system. For an important operating regime of the distributed storage system, which we call the 'bandwidth-limited regime', we show that our upper bounds are tight and provide explicit code constructions. Moreover, we provide a way to short list the malicious nodes and expurgate the system.

I. INTRODUCTION

Distributed storage systems maintain reliability through repair as nodes fail, but repair dynamics create opportunities for eavesdropping and malicious modification. This paper characterizes secure storage limits and gives tight constructions in the bandwidth-limited regime.

  • Distributed storage systems use multiple unreliable nodes to store files reliably over time, including in data-center and peer-to-peer settings.
  • Repair can reduce bandwidth by downloading partial data from d nodes instead of reconstructing the entire file from k nodes.In the example, repair bandwidth decreases from 4 to 3 symbols when d=3 rather than k=2.
  • Repair dynamics expose systems to intruders that may observe or modify nodes at different times as nodes leave and join.
  • The paper derives upper bounds on secrecy and resiliency capacities and proves them achievable with explicit codes in the bandwidth-limited regime.
  • The proposed active-adversary codes identify a list of suspected nodes containing the malicious nodes, enabling system expurgation.

C. Intruder Model

The intruder model distinguishes passive observation from active corruption, while allowing attacks to target original or replacement nodes as the system evolves.

  • The adversary is characterized by ℓ observed nodes and b nodes whose stored data can be maliciously corrupted.
  • Passive Eavesdropper: A passive eavesdropper observes up to ℓ<k nodes, possibly at different times, but cannot modify their data.
  • Passive Eavesdropper: Because eavesdroppers access input nodes, they can observe incoming repair messages in addition to stored contents.
  • Active Omniscient Adversary: An omniscient adversary knows the file and all node contents, controls b nodes with 2b<k, and can alter stored data and outgoing information.
  • Active Limited-knowledge Adversary: A limited-knowledge adversary observes ℓ nodes, controls b of them, and knows the coding and decoding strategies without knowing all stored data.

IV. RESULTS

The paper studies secrecy and resiliency capacities under passive and active attacks, deriving cut-based upper bounds and explicit bandwidth-limited constructions. Its results also connect adversarial protection to node redundancy and limited-knowledge decoding.

  • The paper’s goals are to characterize secrecy capacity for eavesdroppers and resiliency capacity for active adversaries.
  • For symmetric repair, the upper bounds are maximized at d=n−1 and are achievable by explicit codes in the bandwidth-limited regime.
  • The capacity bounds are obtained from cut arguments on the distributed storage information-flow graph.
  • Passive Eavesdropper: A passive eavesdropper reduces the secrecy bound by ℓ terms because compromised nodes can be discarded from storage.
  • Active Adversaries: An omniscient adversary requires redundancy of 2b nodes to correct errors introduced on b controlled nodes.

B. Special Cases

Static-storage secrecy methods can fail in dynamic systems because repair exposes additional information, especially when replacement nodes are observed. The paper derives secrecy-capacity bounds and gives a capacity-achieving construction for the bandwidth-limited regime.

  • Static versus dynamic systems: Repair can expose the entire stored file when a replacement node downloads and regenerates the whole file.Observing two successive replacement nodes during random linear repair yields six linearly independent equations with high probability, sufficient to reconstruct the data.
  • Static versus dynamic systems: Random network coding may achieve the storage-repair tradeoff while failing to provide secrecy against node eavesdroppers.This differs from multicast networks, where random network coding can perform as well as deterministic secure codes against fixed edge observations.
  • Bandwidth-limited regime: In the bandwidth-limited regime, the repair bandwidth is constrained while node storage is unconstrained, and the upper bound is achieved when d = n −1 with α = Γ.The paper states this as the secrecy-capacity result for d = n −1 and fewer than k compromised nodes.
  • Upper bound: The secrecy-capacity upper bound is obtained by deleting compromised nodes in the flow graph and finding the resulting worst-case source-to-collector min-cut.In the D(4, 3, 3) example with two compromised nodes, only one unit can traverse a path not observed by Eve.
  • Achievable construction: The capacity-achieving code concatenates an outer nested MDS coset code with an RSKR-repetition code.The information symbol is mixed with five independent random keys; any data collector accessing three nodes can decode, while any two observed nodes reveal no information about the symbol.

D. Secrecy Capacity in the Bandwidth-Limited Regime

In the bandwidth-limited regime, carefully chosen exact regenerating codes transform secrecy in a dynamic DSS into secrecy over a static erasure-erasure wiretap channel. Nested MDS codes with an RSKR-repetition inner code achieve the resulting secrecy capacity.

  • Reduction to a static channel: Dynamic DSS secrecy can be reduced to a static point-to-point secrecy problem using RSKR-repetition codes when Γ = α = n−1.Repair downloads are stored without compression, and replacement nodes receive exact copies of lost data.
  • Code construction: The construction concatenates an outer nested MDS code with an inner RSKR-repetition code that stores the resulting codeword on the DSS.The outer code takes the information file and random keys as input, while the inner code follows the repetition structure.
  • Code construction: The RSKR-repetition code stores coded symbols by vertically repeating data across nodes according to an auxiliary complete graph.For β = 1, the construction is described directly; larger β values are handled by splitting the file into chunks.
  • Capacity achievement: Nested MDS coding achieves the equivalent wiretap channel's secrecy capacity, completing the construction for the DSS.For β = 1, the equivalent channel has secrecy rate M − µ; the construction extends to general β = Γ/(n−1).

VI. ACTIVE OMNISCIENT ADVERSARY

The omniscient adversary Calvin may control and modify up to b storage nodes as the dynamic system evolves, reducing reliable recovery to a resiliency-capacity problem. A tailored code and decoder exploit the restricted error patterns created by node control, whereas ordinary majority decoding can fail after repairs.

  • Adversary model: Calvin can control up to b nodes over time, knows the stored data and repair scheme, and may modify node data or outgoing messages.The resiliency capacity is the maximum data reliably delivered to a collector contacting any k nodes.
  • Adversary-resilient decoding: The example's repair-induced error pattern shows why network-coding approaches designed for adversarial edges do not directly solve node-based dynamic storage attacks.The paper contrasts this setting with multicast networks where the intruder observes a fixed number of edges.
  • Reliable storage scheme: The proposed scheme reliably stores 1 bit on D(4,3,3) using a (6,1) repetition code concatenated with an RSKR-repetition code.Repair downloads bits with matching indices from the remaining active nodes.
  • Failure of ordinary decoding: Dynamic repairs can increase the observed errors to 5 among 9 bits, so majority or minimum-Hamming-distance decoding cannot recover the correct message.The adversary's corrupted symbols can propagate through repairs to multiple replacement nodes.
  • Adversary-resilient decoding: A special decoder selects a trusted set whose symbols agree, and outputs the corresponding message because one such set remains unaltered for every compromised node.The four trusted sets pairwise intersect in one symbol, ensuring a trusted set exists and agreement identifies the correct message.

A. Results on Omniscient Adversary

For omniscient adversaries, the paper derives resiliency-capacity upper bounds from flow-graph cuts and achieves them in the bandwidth-limited regime with explicit coding and decoding schemes.

  • Capacity bounds: The resiliency-capacity upper bound generalizes a network Singleton bound by deleting 2b nodes when an omniscient adversary controls b nodes and 2b < k.The bound is obtained from cuts in the distributed-storage flow graph.
  • Capacity bounds: In the bandwidth-limited regime, the upper bound is maximized at repair degree d = n −1 and is achieved by a capacity-achieving code.The achieving construction uses node storage capacity α = Γ.
  • Code construction: The construction uses an outer MDS code followed by an RSKR-repetition structure that supports exact repair while accounting for adversarial corruption.The MDS rate is reduced relative to the passive-adversary case to permit error correction.
  • Decoding: A data collector removes repeated symbols and decodes the resulting punctured MDS code after testing candidate malicious-node sets.For each candidate set, the decoder punctures the received word and code according to the symbols associated with that set, then uses a syndrome test.
  • Decoding: The proposed decoder always produces the correct message by identifying a trusted candidate set corresponding to the actual adversarial nodes.Its correctness proof shows that the actual set yields zero syndrome and that an incorrect set cannot produce a different consistent codeword.
  • Limitations and expurgation: The decoder has exponential complexity in the number b of malicious nodes, so it is not practical for large b but establishes achievability.Decoded error locations can be reported to a tracker, which combines them into a list of suspected malicious nodes for expurgation.

VII. ACTIVE LIMITED-KNOWLEDGE ADVERSARY

For a limited-knowledge adversary, the paper uses secure correlation hashes with an MDS-based repair code to identify corrupted symbols and decode despite dynamic attacks. A worked example shows that restricting the adversary’s knowledge can substantially increase resiliency capacity.

  • Adversary model: A limited-knowledge adversary eavesdrops on ℓ nodes and controls b ≤ ℓ of those nodes, without observing enough data to determine the stored file.The adversary knows the coding and decoding strategies but not the complete stored data.
  • Example: For D(5, 3, 4) with α = γ = 4 and b = ℓ = 1, limited knowledge raises the resiliency capacity from 2 in the omniscient case to 5.The example exploits the adversary’s restricted observation.
  • Code construction: The code combines an outer (10, 5) MDS code, an RSKR-repetition repair structure, and hash vectors appended to each data packet.The example assumes hash values are secure from the adversary.
  • Decoding: The decoder removes repeated symbols, compares observed and computed hash matrices, and selects a consistent trusted set before decoding the MDS code.A trusted set of five symbols leaves four symbols as erasures, which the (9, 5) MDS code can correct.
  • Security condition: The adversary can sometimes choose errors whose hash values remain consistent because it observes the corresponding data symbols.The construction therefore relies on keeping hash values secure from the adversary.
  • Performance: The decoding error probability is at most 1/q and vanishes as the field size q increases.The code rate approaches 5 as the block length v increases, despite hash-table overhead.

A. Results on Active Limited-Knowledge Adversary

For limited-knowledge adversaries, the paper derives a general resiliency-capacity upper bound and shows that it is achievable in the bandwidth-limited regime when the adversary’s observations do not determine the stored message.

  • Upper bound: Theorem 14 gives an upper bound on resiliency capacity when the adversary eavesdrops on ℓ < k nodes and controls b ≤ ℓ of them.The proof considers successive failures and repairs followed by a data collector contacting replacement nodes.
  • Achievability: When E < R, the adversary’s observations are insufficient to determine the stored message, and the upper bound is achievable for d = n −1 in the bandwidth-limited regime.This condition distinguishes the limited-knowledge case from an omniscient adversary.
  • Achievability: Theorem 15 gives the resiliency capacity for d = n −1 under the condition E < R, with β = Γ/(n −1).The construction uses a secure hash table to identify erroneous symbols with high probability.
  • Expurgation: Identifying erroneous symbols converts adversarial errors into erasures for decoding and supports expurgation of malicious nodes.The decoder’s outputs can be used to discard suspect nodes from the system.

VIII. CONCLUSION

The paper studies security under repair dynamics, derives secrecy and resiliency-capacity upper bounds, and shows achievability in the bandwidth-limited regime. General capacity expressions and efficient decoding algorithms remain open problems.

  • Scope and conclusions: The model captures adversaries that intrude at different times to exploit node failures and repairs while eavesdropping on or changing stored data.The paper analyzes both secrecy capacity and resiliency capacity.
  • Scope and conclusions: The derived upper bounds are achievable in the bandwidth-limited regime, where explicit coding constructions are provided.The paper also provides a method to identify malicious nodes and expurgate the system.
  • Open problems: General expressions for these capacities and efficient decoding algorithms remain open problems.This is the paper’s stated limitation and direction for future work.

APPENDIX

The appendix derives secrecy and adversarial-resilience bounds for dynamic distributed storage systems using information-flow cuts and adversarial indistinguishability. It also shows that when 2b ≥ k, the resilient capacity is zero.

  • Eavesdropping bounds: The secrecy proof combines reconstruction, perfect secrecy, a Markov chain, and repair-edge capacity bounds to upper-bound the safely stored information.The argument uses H(S|C_B)=0, H(S|D_E)=H(S), node storage limits, and repair links of capacity β.
  • Adversarial bounds: For an adversary controlling b nodes, the cut is partitioned into E1, E2, and E3, with E3 carrying the information needed to distinguish messages.The construction groups cut edges by adversarially controlled nodes and replacement-node inputs before imposing a decoding condition.
  • Information-flow model: A dynamic repair sequence can be represented by an information-flow graph in which failed nodes are replaced and a data collector connects to surviving and replacement nodes.The graph models successive failures of nodes vj+1 through vk and replacement nodes vn+1 through vn+k−j.
  • Adversarial bounds: The capacity upper bound is the total capacity of the E3 edges, and the final theorem takes the minimum over all relevant failure indices j.The analysis covers j = 2b through k and applies the corresponding cut bounds.
  • Adversarial bounds: 2b ≥ k implies Cr(α, γ) = 0 because the set E3 is empty.The zero-capacity conclusion follows directly from the cut argument when the adversary can cover the relevant collector-side nodes.

C. Proof of Theorem 15

The proof constructs a bandwidth-limited secure storage scheme using an outer MDS code, an inner exact-repair repetition code, and a hash table protected from the adversary. A trusted subset of received symbols enables decoding despite controlled-node errors.

  • Construction: The construction operates in the bandwidth-limited regime with d = n−1, β = 1, Γ = n−1, and α = n−1.Larger β or Γ values are obtained by repeatedly applying the proposed scheme.
  • Construction: An outer (θ, R) MDS code forms the data symbols, while an inner RSKR-repetition code stores them and enables exact repair after any node failure.Each data packet is augmented with a hash vector computed from the encoded symbols.
  • Decoding: The data collector compares computed and observed hashes, then selects R symbols indexing an all-✓ subtable as a trusted error-free set.The remaining M−R symbols are treated as erasures and decoded as an (M, R) MDS codeword.
  • Decoding: Since the adversary controls only b nodes, at least one R-symbol trusted set always exists, so the decoder is guaranteed to stop.The guarantee follows from the bound M − Σ_{i=1}^b(n−i) = R.

Error Analysis:

The error analysis bounds the chance that a corrupted symbol passes the hash-consistency test. This probability vanishes with increasing field size, while the hash-table overhead becomes negligible with increasing block length.

  • Error probability: A decoding error can occur only when the selected trusted set contains at least one erroneous symbol.The analysis focuses on whether a corrupted y_j = x_j + e_j can be included in a trusted set.
  • Error probability: Because Charlie observes fewer than R MDS-coded symbols, an unobserved symbol is uniformly distributed conditioned on his observations.This independence limits Charlie’s ability to choose an error orthogonal to every possible unobserved symbol.
  • Error probability: The hash-consistency condition succeeds for a malicious error with probability that goes to zero as the field size q increases.Among q^v possible unobserved symbols, only q^v−1 satisfy the relevant orthogonality condition for a chosen error.
  • Security condition: Secure hash storage is essential because access to the complete hash table would let Charlie choose errors that deceive the decoder.The paper notes that the hash values must remain hidden from the adversary.
  • Rate: The proposed codes achieve the theorem’s capacity asymptotically because hash-table overhead per information symbol vanishes with block length v.The construction stores the hash table with constant-size overhead independent of v.

Security Analysis:

The security analysis defines a decoder that tests candidate adversarial node sets by puncturing received symbols and checking MDS syndromes. It always decodes hash bit 0 correctly, while the error probability for hash bit 1 vanishes as q grows.

  • Decoding logic: The decoder selects M observed symbols with distinct indices, tests each candidate controlled-node set, punctures the corresponding symbols, and checks a syndrome.A zero syndrome causes the decoder to declare that hash bit 0 was stored.
  • Hash bit 0: For hash bit 0, the actual controlled-node set yields an error-free punctured codeword, so the decoder always outputs 0.The true adversarial set removes the error vector from the tested symbols.
  • Hash bit 1: For hash bit 1, the decoder analyzes errors through the decomposition Y = (K + eK) ḠK + (S + eS) ḠS.The secrecy of S makes S + eS uniformly random for the subsequent rank and syndrome analysis.
  • Error probability: The MDS rank argument bounds the probability that any tested candidate set produces a zero syndrome, and the union bound preserves a vanishing error probability as q increases.The resulting probability bound is shown to go to zero with increasing field size.
  • Rate and overhead: Securely storing the hash table requires θ^3 log q symbols, independent of the information-packet block length, yielding negligible overhead for sufficiently large q and v.The paper concludes that the hash table can be stored with high-probability secrecy and resilience.
Loading 1009.2556v2…