Efficient Reconstruction Techniques for Disaster Recovery in Secret-Split Datastores


Increasingly, archival systems rely on authentication-based techniques that leverage secret-splitting rather than encryption to secure data for long-term storage. Secret-splitting data across multiple independent repositories reduces complexities in key management, eliminates the need for updates due to encryption algorithm deprecation over time, and reduces the risk of insider compromise. While reconstruction of stored data objects is straightforward if a user-maintained index is available, the system must also support disaster recovery for index-free datastores. Designing a mechanism for efficient index-free reconstruction that does not increase the risk of attacker compromise is a challenge. Reconstruction requires the association of chunks that make up an object, which is the kind of information attackers can use to identify chunks they must steal to illicitly obtain data. We propose two new techniques, the Set-Subset reconstruction and Secret-Split Secure Hash reconstruction, which allow chunks of data to be correlated and quickly reconstructed. Both techniques operate on the entire collection of chunks in the archive. While they can efficiently rebuild an entire archive, they are inefficient and impractical for rebuilding single objects, making them useless for attackers that do not have access to all of the data. These techniques can each be tuned to trade-off between reconstruction performance and security, reducing overall runtime from O(N^T ) (for N objects requiring T recombined chunks each to return the original object) to between O(N) and O(N^2). These runtimes are practical for archives containing as many as 10 million objects. Larger archives can run these techniques with manageable runtimes by dividing themselves into smaller collections and running the algorithms separately on each collection. Index Terms—Archival Storage, Secret-Splitting, Security, Disaster Recovery

Full Paper



  author       = {Sinjoni Mukhopadhyay and Joel Frank and Daniel Bittman and Darrell D. E. Long and Ethan L. Miller},
  title        = {Efficient Reconstruction Techniques for Disaster Recovery in Secret-Split Datastores},
  booktitle    = {Proceedings of the 26th IEEE International Symposium on the Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS 2018)},
  month        = sep,
  year         = {2018},