Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23CIS607: Systems SecurityPOTSHARDSMark W. Storer, Kevin M. Greenan, Ethan L. Miller, and Kaladhar VorugantiPresented by: Jason GustafsonCIS607: Systems Security2Overview●Secure long-term storage●Background technology review●POTSHARDS overview●Implementation details●System evaluationCIS607: Systems Security3The Challenge●In the long term:●People pass away.●Companies merge or go bankrupt.●Governments are overthrown.●Natural disasters occur.●More technically:●Hardware fails.●Crypto-systems are broken!●The challenge is to design a secure long-term storage system which maintains security even in the occurrence of these events.CIS607: Systems Security4POTSHARDS from 10,000 Feet●The basic idea is to split the data across multiple institutions in such a way that significant collusion is required to recreate the data.●No cryptography is used!●Builds on many prior technologies●Secret splitting●Distributed RAID●Algebraic signaturesCIS607: Systems Security5Background: Secret Splitting●A (K, N) secret splitting scheme divides a single piece of data into N separate pieces such that no fewer than K are needed for reconstruction.●The Shamir method is to use polynomial interpolation●Let D be the data. Chose, at random, a K – 1 polynomial q(x) such that q(0) = D.●Evaluate q(x) at N separate points to get the separate pieces.CIS607: Systems Security6Background: Secret Splitting●An XOR-based method: ●Let D be the block of data. Choose N - 1 random blocks of equal size.●Choose one more block of data such that the XOR of the N - 1 blocks and it is equal to D.CIS607: Systems Security7Background: RAID 5Source: https://secure.wikimedia.org/wikipedia/en/wiki/Standard_RAID_levels●Data is XOR'd together to create a parity bit.●Can recover from the loss of one disk.●Parity is spread across disks to avoid write bottleneck.CIS607: Systems Security8Background: Algebraic Signatures●Parity of the signature is equal to the signature of the parity.●Allows verification of the possession of data without actually possessing that data (or any signatures).Source: Schwarz T., Miller E.; “Store, Forget, and Check: Using Algebraic...”CIS607: Systems Security9POTSHARDS Security Overview●Confidentiality●Original data is divided using secret-splitting techniques into “shards,” which are distributed to separate organizations (ideally with competing agendas).●The user holds an index which shows how to recombine the shards to get the original data.●Integrity●Distributed RAID technologies. ●Algebraic signature verification.●Availability●Redundancy and distribution.●Approximate pointers in case the user's index is unavailable.CIS607: Systems Security10POTSHARDS Implementation●Data is processed in four steps before being placed at storage locations.●Each step provides a different protection.CIS607: Systems Security11Preprocessing●Converts a chunk of data into a set of fixed-sized objects.●Each object gets:●An identifier.●A hash to help with data reconstitutionCIS607: Systems Security12Secret Splitting●Uses an XOR-based secret splitting algorithm (tuned for secrecy) to produce N fragments.●Add another identifier and hash and some additional metadata.CIS607: Systems Security13Availability Splitting●Uses Shamir (M, N) secret splitting on the fragments from previous step to produce “shards.”●Throw on another identifier and an approximate pointer to the next shard (discussed later).●Individuals shards no longer contain the fragment metadata.CIS607: Systems Security14Placement●Select archives for each shard so that no single archive has enough shards to recover the data.●Ideally, each archive is in a separate “security domain.”●Can take into account geographic location of archives.CIS607: Systems Security15Reliability Enhancements●Archives are required to participate in a distributed RAID over the data they store.●Each archive is divided into fixed-sized blocks.●When a shard is inserted, a random block is chosen, the shard is placed in the last slot, and a parity update is sent along.●The update includes the data in the block.●The parity is computed across redundancy groups.CIS607: Systems Security16Secure Reconstruction●If an archive is lost, recovery proceeds as follows:●Choose an archive which has space and is not a member of the redundancy group being recovered.●Elect one archive to manage the rebuilding through a sequence of chained requests which proceed according to the diagram below.CIS607: Systems Security17Secure Integrity Checking●Each archive must check the internal consistency of each block.●Algebraic signatures are used for archives to verify that the other members of each redundancy group are actually storing the data.CIS607: Systems Security18How to Retrieve Data●After the transformation process completes, the user gets an index mapping the original data to its shards.●If the index is lost...●Each shard has an approximate pointer.●“Following” the pointer involves retrieving many shards (some of which might not exist).●Since you cannot confirm the data until you have enough shards, this potentially involves retrieving many shards.CIS607: Systems Security19Evaluation●Implementation:●15,000 lines of Java●Standard TCP/IP communication●BerkeleyDB for storage●Experiments:●750 KB objects●(2, 2) first-stage secret splitting●(2, 3) second-stage secret splitting●Local experiments on 1 Gbps network●Global experiments on PlanetLabCIS607: Systems Security20Read PerformanceCIS607: Systems Security21Write PerformanceCIS607: Systems Security22Performance with Multiple ClientsCIS607: Systems Security23Data