HAIL: A High-Availability and Integrity Layer for Cloud StorageSaturday, December 18, 2010HAIL: A High-Availability and Integrity Layer for Cloud StorageSaturday, December 18, 2010Cloud StorageFlexible, economical, easyBut no direct control over reliability, securityNeed a way to get those guarantees from untrusted systems(Ars Technica)Saturday, December 18, 2010The Game(or “adversarial model”)Saturday, December 18, 2010The GameThe object of the game is to keep a file F available on the service and intactThe player is a trusted client T that owns the fileAn adversary A wants to corrupt it Saturday, December 18, 2010The Game35124The file is stored across n servers (here n=5)Saturday, December 18, 2010The Game35124Each turn (or “epoch”), the adversary gets to take over any b servers (here b=2) and control them for the turnThis is called the corruption phaseSaturday, December 18, 2010The Game35124Then, the client issues a request to each server to check on the file?????Saturday, December 18, 2010The Game35124This is called the challenge phase!!!!!Saturday, December 18, 2010The Game35124If the client detects anomalies in the responses …!!!!!Saturday, December 18, 2010The Game35124… it can try and fix the data in those serversThis is the remediation phase!!!!!Saturday, December 18, 2010The Game35124At the end of the turn, each server is rebooted and the adversary loses controlBut any corruption in storage remainsSaturday, December 18, 2010So how do we rig the game?Saturday, December 18, 2010Idea 1: ReplicationSaturday, December 18, 2010Idea 1: ReplicationJust give each server a copy of the file FFFFFF35124Saturday, December 18, 2010Idea 1: ReplicationFor the challenge, read a random block from each server and compareFFFFF35124Saturday, December 18, 2010Idea 1: ReplicationSo far, so goodNot much bandwidth usedIf the adversary changes the whole file, we'll find out right awaySaturday, December 18, 2010Idea 1: ReplicationBut what if he just changes a bit at a time? We probably won't check that one.FFFFF35124Saturday, December 18, 2010Idea 1: ReplicationWorse, after enough turns a majority of servers have the corrupted blockFFFFF35124Saturday, December 18, 2010Idea 1: ReplicationThis is called a creeping-corruption attackFFFFF35124Saturday, December 18, 2010We need to be able to detect small changes.But we don't want to download the whole fileIdea 1: ReplicationSaturday, December 18, 2010Proofs of RetrievabilitySaturday, December 18, 2010Proofs of RetrievabilityChallenge/response protocol to ensure a file could be fetchedOnly needs to scan a small part of the file, send small responseSaturday, December 18, 2010FPOR EncodingSaturday, December 18, 2010FPOR EncodingEncode using an error-correcting codeSaturday, December 18, 2010FPOR EncodingEncode using an error-correcting codeEncrypt using κ Saturday, December 18, 2010FPOR EncodingEncode using an error-correcting codeEncrypt using κ Add sentinels computed by κSaturday, December 18, 2010ðPOR EncodingEncode using an error-correcting codeEncrypt using κ Add sentinels computed by κShuffle using κκ →Saturday, December 18, 2010ðPOR EncodingOnly the owner knows where the sentinels areTo challenge, ask for a block known to be a sentinelUse κ to verify it’s the correct sentinelSaturday, December 18, 2010ðPOR EncodingAdvantage of POR: Very little data transmission for very high probability of robustnessAny change big enough to fool the ECC will likely overlap a sentinelSaturday, December 18, 2010Idea 2: Replication with PORSaturday, December 18, 2010Idea 2: Replication with PORAs before, only first encode the file with an error-correcting codeFFFFF35124✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔Saturday, December 18, 2010Idea 2: Replication with PORHarder to corrupt, but uses even more spaceFFFFF35124✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔✔Saturday, December 18, 2010Idea 3: Dispersal with PORSaturday, December 18, 2010Idea 3: Dispersal with PORFigure 1. Encoding of file F : on the left, original file represented as a matrix; on the right, encodedfile with parity blocks added for both the server and dispersal codes.of the blocks in any position i. At that point, majority de-coding will fail. The adversary can do this in T = �n/(2b)�epochs.Because the client can feasibly check only a small frac-tion of the file, the probability that it will detect temporaryinconsistencies introduced by the adversary’s corruptions islow. Thus, the adversary can escape detection and render Funretrievable with high probability in T epochs.Replication system with POR. To achieve better resi-lence against a creeping-corruption attack, we might em-ploy a POR system (e.g., [24, 36, 6]) on each of the nservers. In a single-server POR system, F is encoded un-der an error-correcting code (or erasure code) that we referto in HAIL as the server code. The server code renderseach copy of F robust against a fraction �cof corruptedfile blocks, protecting against the single-block corruptionsof our previous approach. (Here �cis the error rate of theserver code.)There are then two options to check the integrity of F .One is to use the single-server POR approach of embeddingintegrity checks within each server’s copy of F . This ap-proach, however, imposes high storage overhead: It doesnot take advantage of cross-server redundancy.An alternative approach is to perform integrity checks bycomparing block values in a given position j using cross-server redundancy as in our previous construction. Withthis approach, the system is still vulnerable to a creeping-corruption attack, but much less than in the previous con-struction. Suppose that the POR can detect inconsistenciesacross the servers in any �dfraction of blocks of F withhigh probability, i.e., the adversary can escape detection bymodifying at most �dblocks in corrupted servers.Assuming that the client performs majority decoding toreplace faulty servers whenever it detects corruption, thisapproach will ensure the integrity of F with high probabilityfor T = �n/(2b)�×(�c/�d) epochs—improving over theprevious approach by a factor of �c/�d.Dispersal code with POR. We can improve the storageoverhead of the previous approach with a more intelligentapproach to creating file redundancy across servers. Ratherthan replicating F across servers, we can instead