CS448/548 Sequence 18Survivable Storage!This part of the discussion of survivable storage is based on the CMU paper below [Wylie-2001].!“Selecting the Right Data Distribution Scheme for a Survivable Storage System”,–Jay J. Wylie, Mehmet Bakkaloglu, Vijay Pandurangan,Michael W. Bigrigg, Semih Oguz, Ken Tew, Cory Williams, Gregory R. Ganger, Pradeep K. Khosla–May 2001–CMU-CS-01-1201CS448/548 Sequence 18Survivable Storage!Design based on mature technologies from decentralized storage systems!Key issues is the selection of the data distribution scheme–specific algorithms for data encoding and partitioning–set of values for its parameters!Algorithms are based on–encryption–replication–striping–erasure-resilient coding–secret sharing–combinations of the above2CS448/548 Sequence 18Survivable Storage!Each algorithm has tunable parameters!Results are schemes using different levels of–performance »e.g. throughput–availability»probability that data is accessible–security»effort required to compromise confidentiality and integrity of stored data3CS448/548 Sequence 18Survivable Storage!Example–replication results in high availability but at high cost with respect to network bandwidth and storage–secret sharing provides security at lower storage and bandwidth cost»disadvantage includes higher CPU utilization»what happens if the number of shares increases?4CS448/548 Sequence 18Survivable Storage!There is no snake oil!–life is a compromise!Paper enumerates on –possible data distribution schemes»<algorithm, parameters>–modeling the consequences of the schemes–identification of best approach for given requirements5CS448/548 Sequence 18Survivable Storage[Wylie-2001] figure 16CS448/548 Sequence 18Survivable Storage!Assumptions–no individual service, node, or user can be fully trusted–view compromised entities as common rather than the exception–encode and distribute data across independent storage nodes–if confidentiality is required»unencoded data should not be stored on single node7CS448/548 Sequence 18Survivable Storage[Wylie-2001] figure 2!Generic decentralized storage architecture–solid lines trace data path–dashed lines trace metadata path8CS448/548 Sequence 18Survivable Storage!Threshold algorithms–encryption, replication, striping, erasure resilient coding, information dispersal, secret sharing–3 parameters (p,m,n)»n: data is encoded into n shares»m: any m shares can reconstruct the data»p: less than p shares reveal no information about the encoded data9CS448/548 Sequence 18Survivable Storage!Replication (1,1,n)–n replicas are stored–any single replica provides the entire data (m=1)–each replica reveals information about the data, in this case, about all the data (p=1)10CS448/548 Sequence 18Survivable Storage!Decimation or Striping (1,n,n)–large block of data is partitioned into n equally sized blocks–need all n sub-blocks to retrieve the data–each sub-block reveals some information!Splitting (n,n,n)–n-1 sub-blocks contain random values, 1 value is EXOR of the n-1 values and the original value–all n sub-blocks are needed to extract the data, hence p=m=n11CS448/548 Sequence 18Survivable Storage!Secret sharing (m,m,n)–need m components to reassemble the data–possible implementation»interpolation points on a polynomial in a finite field»secret value together with m-1 random values determines the encoding polynomial of order m-112CS448/548 Sequence 18Survivable Storage–[Ganger-2001]13CS448/548 Sequence 18Survivable Storage!Ramp scheme (p,m,n)–can be implemented using polynomial-based math–p-1 random values and m-(p-1) secret values–for p=1 this is equivalent to information dispersal–for p=m this is equivalent to secret sharing14CS448/548 Sequence 18Survivable Storage!In general–given N storage nodes there are N3 different options to consider–considerations»availability»confidentiality»CPU cost»storage requirements"implies network bandwidth 15CS448/548 Sequence 18Survivable Storage!Encryption–common approach to protection of confidential data–Symmetric key encryption»single parameter, i.e. key length–Hybrid data distribution algorithms»combining replication with encryption»two security issues:"how well is key protected"how difficult is crypto-analysis16CS448/548 Sequence 18Survivable Storage!Encryption cont.–Short Secret Sharing»encrypt original with random key»store key using secret sharing»store encrypted data using information dispersal»parameters are m, n, and k (key length)–Compression»can be applied to data before applying other algorithms»reduce size of data17CS448/548 Sequence 18Survivable Storage!Encryption cont.–Cryptographic algorithms»e.g. MD5, SHA-1»can be applied before encoding and used to verify data integrity»store signature with data or separate18CS448/548 Sequence 18Availability!Evaluating Availability–Typical assumptions»independence of failure, i.e. uncorrelated failures–example (p,m,n) threshold scheme»this is basically an m-of-n system in fault-tolerance"but, be aware of the implications of the fault model, –e.g. benign vs. malicious»let fnode be the probability that a node has failed or is unavailable»the “read” availability of the stored information is19CS448/548 Sequence 18Availability–example (p,m,n) threshold scheme»write operations are more complicated»system could require m to n nodes to operate correctly to write»if n nodes are required => poor availability»assume N > n storage nodes»now write operation is finished if n shares have been written"this is essentially an n-of-N system»if an m-of-N system is assumed, recovery would be more complicated"paper assumes this approach20CS448/548 Sequence 18Availability–availability discussion»requirements for availability are high, 0.9999…x»how realistic is the assumption that failures are uncorrelated?"e.g. DoS attack, what are the consequences w.r.t. availability?"availability measures are meaningless (!)"availability measure are useful (!)21CS448/548 Sequence 18Security!Evaluating Security–How does one measure security?»no proven metric available to date–One approach: reuse mathematics of fault tolerance»how many nodes must be compromised to bypass confidentiality or integrity?»e.g. use fault-model approach, use PRA»potential problems:"need probabilities of being compromised"difficult or impossible to estimate such probabilities"attacks are often very