Archives seek to preserve information for the long-term. In this work we assume "long-term" to be on the order of a human lifetime or more. At a minimum, archives should be highly reliable and storage-ecient. Reliability means that user data is never lost, corrupted, or unavailable. Storage efciency is critical because the cost of storage is proportional to the time and amount of data stored, and since archives accumulate data that is rarely deleted, the size of an archive could be on the order of multiple exabytes or more [29].
Archives often store highly valuable and/or sensitive data, such as public historical records, private medical data, or classied government secrets; these may be targets for adversaries willing to spend vast resources to attack the archive over the course of many years. Thus, archives should protect data security (i.e., condentiality, integrity, availability) with strong guarantees.
At a minimum, secure storage systems typically use encryption for data condentiality, message authentication codes or signatures for integrity, and replication or erasure coding for availability. On the archival time scales, however, it becomes much more likely that cryptographic techniques used today will be broken in the future by cryptanalytic advances, and this event is impossible to rule out unless we resolve long-standing open questions like P vs. NP. Naively re-encrypting data to use newer ciphers is also an inadequate approach because re-encrypting a large archive is prohibitively expensive (see Section 3). Furthermore, it fails to address the threat of adversaries who steal encrypted data now with the hopes of extracting useful information years down the line; this is called a "Harvest Now, Decrypt Later" attack-a threat being taken seriously by industry and government alike with the prospects of cryptographically viable quantum computers on the horizon [39,48,65].
1 Some secure archival works address this problem by leveraging unorthodox information-theoretic (also referred to as unconditional, or non-cryptographic) techniques that yield provably long-term security guarantees, but suer higher storage costs than replication. Other works devise more storage-ecient cryptographic schemes; alas, due to their cryptographic nature, they still fail to provide long-term guarantees. Ultimately, the trade-o between eciency and security is a central theme of secure archival, and we still have yet to see any system that strikes a desirable point in this trade-o design space.
In this work, we investigate the nature of this trade-o and related challenges in secure archival arising from the threat of cryptographic obsolescence. We study how these challenges are (or fail to be) addressed by existing solutions, and conclude with promising research directions.
To discuss secure archival issues, we rst establish our security goals for archival systems. We then discuss how to formalize adversaries that attack the system, and introduce two notions of security that are central in what follows. Throughout the paper we operate under the standard assumption (for reasons of fault tolerance) that an archival system will, at a minimum, span geographically dispersed storage nodes [25,27,38,43,64]. We conclude the section with some related survey articles in the domain.
Security Goals. When discussing the goals of information security, we adopt the classic CIA triad of condentiality, integrity, and availability. Condentiality and integrity refer to the protection of data from unauthorized access and modication, respectively; availability refers to the ability of the system to provide correct functionality to its users upon request. These are not the only possible goals of information security (e.g., non-repudiation), but the CIA triad is widely agreed upon, and most additional concerns can be lumped under the CIA umbrella. In this work we mostly focus on (long-term) condentiality and integrity, since we consider availability to be much better understood in the storage community [25][26][27]. Availability can also be violated by purely physical means; there's no protection against a suciently determined adversary.
Threat Modeling. To violate any of the security goals, an adversary needs at least to corrupt some storage nodes. Obviously we cannot allow an adversary to corrupt all nodes, so typically an adversary is only allowed to corrupt at most a threshold number of nodes at any point in time. This idea is formalized in Ostrovsky and Yung's popular mobile adversary model [49], which is highly relevant for the provable security of many modern secure-archival works.
Adversarial models come in varying levels of formalism. Rigorous cryptographic adversarial models-like the mobile adversary model-allow one to obtain more useful security proofs, and are therefore considered the "gold standard" for adversarial modeling [21]. A key consideration in formulating an adversarial model is specifying its computational power. Typically, adversaries are viewed as Turing machines with either probabilistic polynomial runtime (PPT) or completely unbounded runtime, but some works make more nuanced computational assumptions. For instance, one can introduce real-time notions into the model and bound the rate of computation per unit of real time [17]. Additionally, one can dene an adversary as a sequence of adversaries indexed by time, with each successive adversary belonging to a more powerful class of computing machines [15]. In this work we consider a mobile adversary with computational power bounded in this more nuanced manner; yet, for the purpose of understanding the challenges of secure archival it is often instructive to consider a computationally unbounded adversary, even though unbounded computing machines do not exist in the real world due to physical limits of computation [40].
Computational vs. Information-Theoretic Security. We draw an important distinction between computational and information-theoretic notions of security. If an adversarial model assumes any kind of restrictions on computing power, then we say that the security (if any) of our system with respect to some security goal is computational. Otherwise, it is information-theoretic.
Next, we present two security denitions for encryption as an example. Consider a key space K, message space M, and ciphertext space C, and let (Enc, Dec) be a (private key) encryption scheme such that Enc : K ⇥ M ! C, Dec : K ⇥ C ! M, and Dec : (Enc : (<)) = < for all : 2 K, < 2 M. Denition 2.1 (n-Statistically Indistinguishable Encryptions). An encryption scheme (Enc, Dec) is n-statistically indistinguishable (n > 0) if, 8< 0 , < 1 2 M, and for any A : C ! {0, 1}:
and for any PPT algorithm A : C ! {0, 1}:
Both denitions try to formalize the sentiment that an adversary A cannot distinguish between any two ciphertexts (i.e., learn any information) with greater than a certain probability. The only dierence is that in Denition 2.2, the adversary's computational power is restricted. Thus, this definition provides computational security, while Denition 2.1 provides the (much stronger) information-theoretic security. The computational setting is almost always preferred over the information-theoretic one for eciency reasonsespecially storage cost (see Figure 1). However, informationtheoretic denitions appear in many secure archival works due to the unique challenges posed by long-term security.
Related work. Several have studied the security of storage systems [13,61,66,68], but only one [61] takes into account both condentiality and integrity of long-lived data. For example, Braun et al. [13] study the condentiality of storage systems and examine various information-theoretic key agreement solutions for data in transit and proactive secret sharing schemes for data at rest. Their work is complemented by the survey on integrity by Vigil et al. [66], which analyzes and compares solutions to integrity concerns including proof of existence, non-repudiation, and authenticity of documents. However, Braun et al. [13] and Vigil et al. [66] do not explore solutions that provide both condentiality and integrity of long-term archival systems.
A survey by Yang et al. [68] investigates data security and privacy issues and potential countermeasures in cloud storage systems. The threats mentioned in their paper can be applicable to secure archives, but the focus is not long-term security. The survey by Storer et al. [61] highlights security threats specic to long-term archival systems. Our work can be thought of as an extension of Storer's in that we also consider some of the attacks mentioned in their paper and evaluate recent approaches to address them.
As outlined in Section 1, the primary security challenge for archival systems is the threat of cryptographic obsolescence. After briey examining why this threat is (currently) unavoidable, we explore why developing a practical solution to overcome it is so dicult by stepping through several existing approaches, discussing condentiality and integrity separately.
The security of all computationally secure cryptographic primitives (encryption schemes, hash functions, etc.) relies on assumptions of hardness. For example, Die-Hellman key exchange assumes the hardness of computing discrete logarithms [20], RSA encryption assumes the hardness of factoring RSA moduli [54], several post-quantum cryptographic schemes assume the hardness of the Module Learning with Errors (MLWE) problem [11], and AES is simply assumed to be secure because two decades of cryptanalysis have failed to produce practical attacks [9]. All these assumptions rely on the existence of one-way functions [35]. Informally, a function is one-way if it is easy to compute, but any PPT algorithm fails to invert it with overwhelming probability. Unfortunately, the existence of one-way functions directly implies P < NP [5]. Consequently, any computationally secure cryptographic primitive can potentially be broken in the future. Of course, this has not prevented security practitioners from developing schemes that are widely believed to be secure. Yet, history has repeatedly shown that schemes believed to be secure at one point in time are often broken in the future, like the MD5 hash [60], DES encryption [8], and discrete-log based schemes against quantum computers [58]. Thus, trying to extrapolate the computational security of current cryptographic schemes decades or more into the future is a fairly risky endeavor.
To simplify exposition of existing approaches, we begin by addressing data condentiality, grouping approaches by computational vs. information-theoretic notions of security.
Computational security. It is natural to ask whether we can still use our arsenal of computationally secure cryptography to achieve long-term condentiality in the face of cryptographic obsolescence. For instance, can we not just periodically re-encrypt data? A naïve approach is for the user to retrieve data, decrypt, and re-encrypt it with a new scheme, but this requires user intervention. This is especially problematic in an emergency situation where the current encryption method is broken, and all users' data needs to be re-encrypted immediately. This re-encryption could be delegated to the storage system (without giving the system access to user keys) using more sophisticated techniques like Universal Proxy Re-Encryption (UPRE) [23].
Unfortunately, regardless of technique, it may be infeasible to re-encrypt all data in a timely manner due to I/O bottlenecks. An archival system will require massive amounts of storage media that is cost eective and easy to secure. Therefore, we exclude HDDs and SSDs as they are (i) too expensive and (ii) less secure, because online media are more prone to remote attacks. Conversely, removable media stored oine enjoy a reduced attack surface (e.g., DVDs, tapes). We illustrate with a few examples of tape-based archives-a common archival storage medium [16]-in the literature. A similar exercise can be conducted with glass-based media [4].
In this example, we attempt to use conservative numbers from the cited works below-whether explicit or implicitand make several simplifying assumptions: a real archive would have even longer re-encryption times and costs. A conservative approximation for the time to just read all the data in an archive can be obtained by dividing the size of the archive by its aggregate read throughput. With 80PB of total data and an aggregate throughput of 400TB/day, the Oak Ridge HPSS [59] could be read in 6.75 months. At 37.9PB and 120TB/day, the ECMWF MARS archive [30] yields 10.35 months, and the CERN EOS archive [51] yields 8.3 months for 230PB and 909TB/day. Pergamum [62] (a HDD archive) describes a hypothetical 10PB tape archive with aggregate throughput of 5GB/s, yielding 0.76 months. In addition to reading, the system has to encrypt (i.e., consume memory and CPU) and then write out the data. Writing in many systems tends to be slower than reading due to media limitations and the need to verify written data; this factor will at least double the re-encryption duration. Moreover, in practice the system would have to reserve some capacity for new activity (e.g., ingest new data and serve read requests); this additional factor can easily double the re-encryption duration. Lastly, the aforementioned systems are considerably smaller than the archives we envision in the many exabyte and even zettabyte sizes over their lifetimes. All things considered, the practical time for re-encrypting an entire archive could turn into many years-during which time all not-yet-encrypted data remains vulnerable.
One could avoid the I/O cost of re-encryption-at the cost of storing a growing history of encryption keys-by using multiple layers of dierent encryption schemes to hedge against the threat of any one or more ciphers being broken. This approach, known as a robust combiner, more precisely a cascade cipher, is used in the secure-archival system ArchiveSafeLT [56]. Cascade ciphers enjoy the property of being at least as secure as the most secure cipher in the cascade [33], but care must be taken in their design as failure to account for subtle considerations can render the whole cascade insecure [45]. ArchiveSafeLT also proposes wrapping data in new layers of encryption if enough of the old layers are broken, though this runs into the same I/O issues as re-encryption.
Another approach is that taken in AONT-RS [53], which was deployed as part of the Cleversafe dispersed storage system (later acquired by IBM's Cloud Object Storage). Let Enc : (•) denote a computationally secure encryption using key :, and ⌘(•) a computationally secure hash function. The AONT-RS scheme begins by splitting the data to be encrypted into equal-sized blocks < 1 , ...,< B . Then, for each 8 2 {1, ..., B} the scheme computes ciphertext blocks 2 8 = < 8 Enc : (8 + 1), and a nal ciphertext block 2 B+1 = : ⌘(2 1 , ..., 2 B ). The B + 1 ciphertext blocks are encoded into = > B + 1 codewords via systematic erasure coding, and each codeword is then dispersed to a dierent storage node. Assuming Enc and ⌘ are computationally secure, then a PPT attacker provably cannot learn any information about the plaintext unless they possess all B+1 ciphertext blocks or know the key. This scheme is easy to parallelize, achieves a good trade-o between storage cost and availability, and eliminates the need for key management. On the other hand, if the underlying encryption scheme or hash function are broken, an attacker trivially "knows the key" and can recover plaintext from even a single share. Note that, apart from AONT-RS, every other commercially available archival system we are aware of simply uses AES (e.g., AWS, Google Cloud, Azure [1][2][3]).
We have seen how to devise computationally secure methods that improve upon naïve re-encryption. However, these methods are all still vulnerable to a showstopping attack: they are susceptible to Harvest Now, Decrypt Later attacks. Re-encryption does nothing to protect portions of any stolen ciphertext.
Information-theoretic security. The simplest example of information-theoretically secure encryption is the One-Time Pad [36]. To encrypt a message <, a key : 2 {0, 1} |< | is sampled uniformly at random, and the ciphertext is computed as 2 = < :. Without knowledge of :, an adversary provably cannot learn any information about < from 2 regardless of computing power, thus achieving "perfect secrecy" (i.e., let n = 0 in Denition 2.1).
A generalization of the One-Time Pad is Shamir's secret sharing [57]. It takes a message < as input, and outputs = shares B 1 , ..., B = , with |B 8 | = |<|, such that any subset of C = or more shares suces to recover <, but fewer than C shares leaves < perfectly secret. The mechanism is equivalent [46] to a non-systematic [=, C] Reed-Solomon code applied to (<, A 1 , ..., A C 1 ), where < is the message and A 1 , ..., A C 1 are all sampled uniformly at random from {0, 1} |< | .
Many secure archival systems propose using secret sharing as a data encoding scheme, thus providing long-term condentiality [12,14,27,28,47,63,64,67]. POTSHARDS [63] was the rst work to design and evaluate a full archival system based on Shamir's secret sharing. In POTSHARDS, each share is uploaded to an administratively independent storage provider, thereby avoiding a single point of trust or failure, and achieving good availability due to the erasure-coding properties of Shamir's secret sharing and some additional disaster recovery techniques. There are two main drawbacks with this scheme. The rst is high storage overhead: each share is the same size as the original message, so we incur the same overhead as replication with less availability as we can tolerate the loss of at most = C shares. This cost is a provably unavoidable consequence of perfect secrecy [6].
The second is that given enough time, we must entertain the possibility that a mobile adversary eventually steals a threshold number of shares.
To combat this mobile adversary, it is desirable for the system to have a means of "refreshing" the shares, rendering stolen shares obsolete. This can be accomplished via proactive secret sharing [34]: an information-theoretic distributed protocol that re-randomizes shares. Wong et al. [67] suggest using a version of proactive secret sharing for secure archival with the desirable feature of adding or removing shareholders in each share renewal phase. Unfortunately, share renewal requires every shareholder to send a share to each shareholder. This incurs high communication costs. Moreover, if the system must execute share renewal for many data objects in a short time frame, this may become impractical for the same reasons as re-encryption. Nonetheless, proactive secret-shared datastores remain the leading (and only) approach for secure-archival systems that provide long-term information-theoretic condentiality of data at rest.
Given the strong information-theoretic security of secretshared datastores, an adversary may nd it more fruitful to steal data in transit rather than data at rest, since TLS encryption is only computationally secure. This motivates a desire for information-theoretically secure communication channels. LINCOS [12] and follow-up works [14,28,47] construct information-theoretic channels via Quantum Key Distribution (QKD). By setting up entangled quantum states, two parties can generate a shared One-Time Pad key that is impervious to eavesdropping. While promising, QKD requires specialized infrastructure, and a number of engineering challenges must be resolved before QKD can be considered a mature, practical, and cost-eective method [18]. Another approach to information-theoretic channels is introduced in Section 4.
Whereas long-term condentiality guarantees require expensive information-theoretic methods, long-term integrity is more amenable to cryptographic tools. Today, computationally secure digital signatures are widely used for integrity protection. A single signature alone may eventually be broken, but long-term integrity can be achieved with a chain of digitally signed timestamps [32]. We omit details, but intuitively this works because signing an old signature with a new signature preserves the integrity of both as long as the old signature has not been broken at the time the new signature was computed. Note that a computationally unbounded attacker could instantly break this signature with brute force, but unbounded attackers are unnecessarily strict in this scenario. A signature's integrity needs to hold for only a relatively short interval of real time until a newer, more secure signature is added to the chain. This motivates the more nuanced computationally bounded adversary described in Section 2. LINCOS makes the key observation that while timestamp chains provide long-term integrity, the use of computationally secure hashes within the chain compromises the information-theoretic condentiality of data. They remedy this by swapping out hashes with information-theoretically hiding commitments, such as the Pedersen commitment [50].
Timestamp chains provide long-term integrity of a single data object in isolation, but this by itself is insucient for secret-shared datastores, where one must also ensure that shares are consistent with each other. This is especially important for the share renewal phase of proactive secret sharing, as a corrupt shareholder that distributes invalid new shares can compromise the integrity of the secret. Veriable secret sharing [50] protects against this threat, and is often included by default as a sub-protocol of proactive secret sharing. The use of Pedersen commitments within veriable secret sharing protocols is again useful in order to safeguard long-term condentiality.
In Section 3 we examined how dierent approaches to secure archival systems fare against the core challenge of cryptographic obsolescence. We found that computationally secure methods can yield decent long-term integrity, and are sometimes (e.g., AONT-RS) practical enough to make their way into commercial use, but fail to provide long-term condentiality guarantees. Conversely, the information-theoretic approach of a secret-shared datastore equipped with proactive secret sharing and information-theoretic channels (via QKD) delivers strong long-term condentiality, but suers from high storage and communication overheads, as well as higher infrastructure costs.
We are left with a seemingly intractable trade-o between eciency and security. A reasonable response to this state of aairs is to declare that there is no "one size ts all" approach to secure archival. This statement was made nearly two decades ago by the PASIS [27] project, which investigated several approaches but left users to decide which one was best for their data. This may very well be the case, but the unsavory trade-o remains. See Table 1 for a summary of systems discussed in this work.
We conclude with some future directions for alleviating the trade-o by reducing costs with alternative storage media, and improving the security of information-theoretic systems with new and existing techniques.
The high storage costs of secret-shared datastores may be reduced with cheaper and denser archival storage media. One leading candidate is DNA storage, with a theoretical density of 1EB per cubic millimeter (8 orders of magnitude greater than tape), and centuries of durability [10]. Citing the high costs and low throughputs of DNA synthesis and sequencing, Microsoft's Project Silica [4] advocates for glass as an archival storage medium. While not as dense as DNA (only 429TB per cubic inch [69]), glass requires very little maintenance, can survive for millenia, and is much closer to widespread adoption than DNA storage. Photosensitive lm is also low maintenance, potentially lasts centuries, and is currently used in the the Arctic World Archive [55].
Instead of stealing an entire secret share from the archive, an adversary might leak only a few bits of information about a share via some hidden side-channel. Shamir's secret sharing is known to be vulnerable to such leakage attacks [7]; several recent works [7,19,37,41,42] have proposed new leakage-resilient secret sharing (LRSS) schemes. Evaluating LRSS's viability for archival systems is an open problem. In particular, LRSS schemes can be broadly classied according to leakage model and linearity. The leakage model determines the class of side-channel attacks that the scheme can resist; it is unclear which leakage model is most appropriate for a secret-shared archive. Linear LRSS constructions tend to be simple and compatible with existing proactive secretsharing schemes, but their security often imposes restrictions on what the threshold value can be. Nonlinear schemes have no such restrictions, but their constructions are more complex, and it is unclear how to make these schemes proactive.
An alternative to QKD for information-theoretic channels is the Bounded Storage Model (BSM) [44]. In the BSM, honest parties can agree on a One-Time Pad key by streaming large amounts of random data to each other such that an adversary with a much larger storage capacity cannot capture the entire stream. We believe the BSM is overdue for a practical evaluation-last evaluated in 2005 [24]. Since then, new theoretical results have expanded the possibilities of the BSM. Namely, the necessary gap between honest and adversarial storage has been improved from quadratic to exponential for important cryptographic primitives like key agreement, oblivious transfer, and general multi-party computation, at the cost of increased round and communication complexity [22,31,52]. It remains to be seen whether these costs are low enough in practice to consider the BSM as a viable option for information-theoretic channels.
The concrete design and implementation of secret-shared archives may benet from the literature on key-management systems, as their architectures can be quite similar. For example, HasDPSS [70] leverages modern blockchain and proactive secret-sharing techniques to realize a robust and decentralized key-management system.
To conclude, the currently unavoidable threats of cryptographic obsolescence and Harvest Now, Decrypt Later attacks induce a steep trade-o between security and storage cost that depends on whether designers of secure archives choose between computational or information-theoretically secure techniques. Fundamentally, this trade-o will remain unless large open problems in complexity theory are resolved (see Section 3.1), but exploring certain research directions such as next-generation archival media, LRSS schemes, BSM improvements, and recent developments in key-management systems may make the trade-o more palatable by improving information-theoretic systems.