POTSHARDS: Secure Long-Term Storage Without EncryptionMark W. Storer Kevin M. GreenanUniversity of California, Santa CruzEthan L. MillerKaladhar VorugantiNetwork Appl iance†AbstractUsers are storing ever-increasing amounts of infor-mation digitally, driven by many factors including gov-ernment regulations and the public’s desire to digitallyrecord their personal histories. Unfortu nately, many ofthe security mechanisms that modern systems rely upon,such as e ncryption, are poorly suited for storing datafor indefinitely long periods of tim e—it is very diffi-cult to manage keys and update cryptosystems to pro-vide secrecy through encryption over periods of decades.Worse, an adversary who can compromise an ar c hiveneed only wait for cr yptanalysis techniques to catch upto the encryption algorithm used at the time of the com-promise in order to obtain “secure” data.To addr e ss these conce rns, we have developed POT-SHARDS, an archival storage system that provides long-term security for data with very long lifetime s withoutusing enc ryption. Secrecy is ach ieved by using prov-ably secure secr e t splitting and spreading the resultingshares across separately-managed archives. Providingavailability and data recovery in such a system can be dif-ficult; thus, we use a new technique, approximate point-ers, in conjunction with secure distributed RAID tech-niques to provide availability and reliab ility acr oss in-dependent archives. To validate our design, we devel-oped a prototype POTSHARDS implementation , whichhas demonstrated “normal” storage and retrieval of userdata using indexes, the recovery of user data using onlythe pieces a user has stored across the archives and thereconstruction of an entir e failed archive.1 IntroductionMany factors motivate the need f or secure long-termarchives, ranging from the relatively short-term (forarchival pu rposes) requirements on p reservation, re-trieval and security properties demanded by recent leg-†Work performed while a member of IBM Almaden Researchislation [1, 20] to the indefinite lif etimes of cultural andfamily heritage data. As users increasingly create andstore images, vid e o, family d ocuments, medical recordsand legal re cords digitally, the need to securely preservethis data for future generations grows correspon dingly.This information often needs to be stored securely; datasuch as medical records and legal documents that couldbe important to future generations must be kept indefi-nitely but mu st no t be publicly accessible.The goal of a secure, long-term archive is to providesecurity for relatively static data with an indefinite life-time. There are three pr imary security properties thatsuch archives aim to provide. First, the data stored mustonly be viewable by au thorized readers. Second, thedata must be available and accessible to a uthorized userswithin a reasonable amount of tim e , even to those whomight lack a specific key. Third , there must be a way toconfirm the integrity of the data so that a reader can bereasonably assured that the data that is rea d is the sameas the data that was written.The usage mode l of secure, long -term archival stor-age is write-once , read-maybe, and thu s stresses through-put over low-latency per forman ce. This is quite differentfrom the top storage tier of a hierarchical storage solu-tion th at stresses low-latency access or even bottom-tierbackup storage. The usage model of long- te rm archivesalso has the unique property that the reader may havelittle knowledge of the system’s contents and no contactwith the original writer; while file lifetimes may be in-definite, user lifetimes certain ly are not. For digital “timecapsules” that must la st for decades or even centuries, thewriter is assumed to be gone soo n after the data has beenwritten.There are many novel storage problems [3, 32] that re-sult from the potentially indefinite data lifetimes foundin long-term stora ge. This is partially due to mecha-nisms such as cryptography that work well in the short-term but are less effective in the long-term. In long- termapplications, encryption intr oduces the problems of lost2007 USENIX Annual Technical ConferenceUSENIX Association143keys, compromised keys and even compromised cryp-tosystems. Additionally, the management of keys be-comes difficult because data will experience many keyrotations and cryptosystem migrations over the course ofseveral decades; this m ust all be done without user in-tervention beca use the user who stored the data may beunavailable. Thus, security for archival storage must bedesigned explicitly for the uniq ue demand s of long-ter mstorage.To addr ess the many security requirements for long-term archival storage, we de sig ned and implementedPOTSHARDS (Protection Over Time, Securely Harb or-ing And Reliably Distributing Stu ff), which uses threeprimary techniques to provide security for long-ter mstorage. Th e first techn ique is secret splitting [28], whichis used to provide secrecy for the sy stem’s contents. Se-cret splitting breaks a block into n pieces, m of whichmust be o btained to reconstitute the b lock; it can beproven that any set of fewer than m pieces contains noinforma tion about the origin al block. As a result, se-cret splitting does not requir e the same updating as en-cryption, which is only computationally secure. By pro-viding data secrecy witho ut the use of encryption, POT-SHARDS is able to move security from encryption to themore flexible and secure authe ntication realm; unlike en-cryption, auth entication need not be done by computer,and authenticatio n schemes can be easily changed in re-sponse to new vulnerabilities. Our second technique, ap-proximate pointers, makes it possible to reconstitute thedata in a reasonable time even if all indices over a user’sdata have been lost. This is achieved without sacrificingthe secrecy property provided by the secre t splitting. Thethird technique is the use of secur e , distributed RAIDtechniques across multiple independent archives. In theevent that an archive fails, the data it stored can be recov-ered without the need for other archives to reveal the irown data.We implemen ted a prototype of POTSHARDS andconducted several experiments to test its performanceand resistance to failure. The current, CPU-bound im-plementation of POTSHARDS can read and write dataat 2.5–5 MB/s on commodity hardware but is highly p ar-allelizable. It also survives the failure of an