HAIL: A High-Availability and Integrity Layerfor Cloud StorageKevin D. BowersRSA [email protected] JuelsRSA [email protected] OpreaRSA [email protected] introduce HAIL (High-Availability and IntegrityLayer), a distributed cryptographic system that permits aset of servers to prove to a client that a stored file is in-tact and retrievable. HAIL strengthens, formally unifies,and streamlines distinct approaches from the cryptographicand distributed-systems communities. Proofs in HAIL areefficiently computable by servers and highly compact—typically tens or hundreds of bytes, irrespective of file size.HAIL cryptographically verifies and reactively reallocatesfile shares. It is robust against an active, mobile adver-sary, i.e., one that may progressively corrupt the full set ofservers. We propose a strong, formal adversarial model forHAIL, and rigorous analysis and parameter choices. Weshow how HAIL improves on the security and efficiency ofexisting tools, like Proofs of Retrievability (PORs) deployedon individual servers. We also report on a prototype imple-mentation.1 IntroductionCloud storage denotes a family of increasingly popularon-line services for archiving, backup, and even primarystorage of files. Amazon S3 [1] is a well known exam-ple. Cloud-storage providers offer users clean and simplefile-system interfaces, abstracting away the complexities ofdirect hardware management. At the same time, though,such services eliminate the direct oversight of componentreliability and security that enterprises and other users withhigh service-level requirements have traditionally expected.To restore security assurances eroded by cloud environ-ments, researchers have proposed two basic approaches toclient verification of file availability and integrity. The cryp-tographic community has proposed tools called proofs ofretrievability (PORs) [24] and proofs of data possession(PDPs) [2]. A POR is a challenge-response protocol thatenables a prover (cloud-storage provider) to demonstrate toa verifier (client) that a file F is retrievable, i.e., recover-able without any loss or corruption. The benefit of a PORover simple transmission of F is efficiency. The responsecan be highly compact (tens of bytes), and the verifier cancomplete the proof using a small fraction of F . Roughlyspeaking, a PDP provides weaker assurances than a POR,but potentially greater efficiency.As a standalone tool for testing file retrievability againsta single server, though, a POR is of limited value.1De-tecting that a file is corrupted is not helpful if the file is irre-trievable and thus the client has no recourse. Thus PORs aremainly useful in environments where F is distributed acrossmultiple systems, such as independent storage services. Insuch environments, F is stored in redundant form acrossmultiple servers. A verifier (user) can test the availability ofF on individual servers via a POR. If it detects corruptionwithin a given server, it can appeal to the other servers forfile recovery. To the best of our knowledge, the applicationof PORs to distributed systems has remained unexplored inthe literature.A POR uses file redundancy within a server for verifi-cation. In a second, complementary approach, researchershave proposed distributed protocols that rely on queriesacross servers to check file availability [26, 35]. In adistributed file system, a file F is typically spread acrossservers with redundancy—often via an erasure code. Suchredundancy supports file recovery in the face of server er-rors or failures. It can also enable a verifier (e.g., a client) tocheck the integrity of F by retrieving fragments of F fromindividual servers and cross-checking their consistency.In this paper, we explore a unification of the two ap-proaches to remote file-integrity assurance in a system thatwe call HAIL (High-Availability and Integrity Layer).HAIL manages file integrity and availability across a col-lection of servers or independent storage services. It makesuse of PORs as building blocks by which storage resourcescan be tested and reallocated when failures are detected.1A standalone POR is useful for quality-of-service testing. The speedof the verifier’s response gives an upper bound on expected deliverythroughput for F . We don’t treat QoS issues in this paper.1HAIL does so in a way that transcends the basic single-server design of PORs and instead exploits both within-server redundancy and cross-server redundancy.HAIL relies on a single trusted verifier—e.g., a client ora service acting on behalf of a client—that interacts withservers to verify the integrity of stored files. (We do notconsider a clientless model in which servers perform mu-tual verification, as for distributed information dispersal al-gorithms such as [16, 18, 8, 21].)HAIL offers the following benefits:• Strong file-intactness assurance: HAIL enables a setof servers to prove to a client via a challenge-responseprotocol that a stored file F is fully intact—more pre-cisely, that the client can recover F with overwhelm-ing probability. HAIL protects against even small, e.g.,single-bit, changes to F .• Low overhead: The per-server computation and band-width required for HAIL is comparable to that ofpreviously proposed PORs. Apart from its use ofa natural file sharing across servers, HAIL improveson PORs by eliminating check values and reducingwithin-server file expansion.• Strong adversarial model: HAIL protects against anadversary that is active, i.e., can corrupt servers and al-ter file blocks and mobile, i.e., can corrupt every serverover time.• Direct client-server communication: HAIL involvesone-to-one communication between a client andservers. Servers need not intercommunicate—or evenbe aware of other servers’ existence. (In comparison,some information dispersal algorithms involve server-to-server protocols, e.g., [16, 18, 8, 21].) The clientstores just a secret key.• Static / dynamic file protection: In this paper, weshow how HAIL protects static stored objects, such asbackup files and archives. But our tools and frameworkcan be modified with little added overhead to accom-modate file updates, i.e., to provide integrity assurancefor dynamically changing objects. We briefly explainthis direction in the paper conclusion.Our two broad conceptual contributions in HAIL are:Security modeling We propose a strong, formal modelthat involves a mobile adversary, much like the model