Improving secure long-term archival of digitally signed documents

Carmela Troncoso, Danny De Cock, Bart PreneelStorageSS 2008 · DOI

TL;DR

This paper introduces a novel Secure Long-Term Archival System (SLTAS) that ensures the verifiable integrity and validity of digitally signed documents far into the future, even as cryptographic algorithms and technologies evolve. It addresses the critical challenge of proving not only that a document's signature was valid at the time of archival, but also that the signature was created within a specific, verifiable time window, preventing backdating.

What Problem Does This Paper Address?

In today's digital world, an ever-increasing volume of documents are created and stored electronically. While short-term archival focuses on integrity and availability, long-term archival faces unique challenges. The primary concern is the enduring validity of digital signatures. Over time, private keys can be compromised, and the cryptographic algorithms used for signing and verification can become vulnerable due to advances in computing power and cryptanalysis. Furthermore, the validity status of public key certificates (which attest to the authenticity of a signing key) can change (e.g., revocation). Existing archival systems often fail to address these issues comprehensively, leaving the integrity of archived digital documents at risk in the distant future. This paper tackles the problem of preserving the integrity and validity of digitally signed documents over extended periods, ensuring that their authenticity can be proven even decades or centuries later.

Methods

The proposed Secure Long-Term Archival System (SLTAS) employs a client-server architecture with two additional trusted parties: a Certification Authority (CA) and a Time Stamping Authority (TSA). The core innovation lies in how it establishes verifiable proofs for three critical requirements:

  1. Signed between two indisputable moments: The client obtains two timestamps from the TSA – one before signing and one after signing. This creates a verifiable time window, proving that the signature was generated within this specific period, thus preventing backdating.
  2. Content unchanged during storage: The SLTAS uses a "retimestamping" mechanism. Periodically, the system re-validates the integrity of archived documents and their associated proofs, then generates a new timestamp over the entire package. This creates an "onion" of timestamps, where each layer adds a new proof of integrity at a later point in time, using current cryptographic standards.
  3. Signature generated with a valid key: The client collects evidence of the signing key's validity at the time of signing (e.g., OCSP responses or CRLs) and includes it in the archival package. The SLTAS also retimestamps this validity proof, ensuring its integrity over time.

The system creates a "packet" containing the signed document, the client-generated timestamps, the signing key's validity proof, and relevant certificates. This packet is then submitted to the SLTAS, which verifies it and adds its own timestamp to prove the archival time.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Preventing Backdating is Crucial: The paper highlights that simply proving a signature existed before archival isn't enough. Establishing a verifiable time window for signature creation is essential for applications like financial transactions or legal contracts where precise timing is critical.
  • The "Onion" of Timestamps: The retimestamping process, creating nested layers of proofs, is a clever way to continuously update the integrity guarantees using the latest cryptographic algorithms. This effectively combats the "aging" of cryptographic primitives over time.
  • Client-Side Proof Generation: Shifting the initial proof of signature existence and validity to the client side, rather than relying solely on the SLTAS, reduces trust requirements and provides stronger evidence for the signing event itself.
  • Separation of Concerns: The SLTAS focuses specifically on the integrity and validity of digitally signed documents, explicitly stating it does not address long-term availability (e.g., disaster recovery) or format migration, allowing for modular integration with other systems.

Key Results

The paper presents a Java implementation and evaluation of the SLTAS. Key findings include:

  • Negligible Time Overhead for Initial Archival: Creating the initial archival package (including two timestamps, signature, and certificates) takes less than one second on current hardware.
  • Efficient Retimestamping: The SLTAS's internal operations, including archiving and retimestamping, are efficient, with archival taking less than 350 milliseconds. The retimestamping process is also shown to become more efficient over time due to Moore's Law.
  • Affordable Storage Overhead: While the storage space grows with each retimestamping layer, the overhead is considered affordable, especially for larger documents like multimedia files. Figures show that even with 25 layers (representing 75 years), the overhead is manageable.
  • Verifiable Integrity: The system provides a verifiable path to assert that an archived document has not been tampered with since it was signed, even after decades. Complete validation of the "onion" of timestamps is demonstrated to be computationally feasible.

Limitations and Future Work

  • Focus on Integrity, Not Availability/Migration: The system does not inherently solve long-term availability (e.g., against large-scale disasters) or format migration issues. However, the authors suggest their output can serve as input for systems that do address these.
  • Trust in TPs: The system relies on the trustworthiness of the CA and TSA.
  • Privacy Concerns with Certificates: Public key certificates, which may contain sensitive information, are stored with the document. Future work suggests using anonymous credentials to address privacy concerns.
  • Obsolescence of Cryptography: While the system is designed to mitigate this, a complete and sudden breakdown of all cryptographic primitives used would render the integrity proofs useless.
  • Authentication: The paper does not specify authentication mechanisms for SLTAS operations, leaving it to concrete implementations.
  • Key Management for Encrypted Data: If documents are encrypted for confidentiality, the client is responsible for long-term key management, which is outside the scope of this paper.

Future work includes exploring anonymous credentials for enhanced privacy and investigating how to integrate their system with solutions for format migration and data possession proofs, while also accounting for the potential obsolescence of cryptographic primitives in those contexts.

Summary updated

BibTeX
@inproceedings{troncoso2008improving,
  author = {Carmela Troncoso and Danny De Cock and Bart Preneel},
  title = {{Improving secure long-term archival of digitally signed documents}},
  booktitle = {StorageSS},
  year = {2008},
  doi = {10.1145/1456469.1456476},
}
Figure