Do Digital Signatures Assure Long-Term Integrity?

Duane Dunston has posted a long description of the use of digital signatures to assure the integrity of preserved digital documents. I agree that the maintaining the integrity of preserved documents is important. I agree that digital signatures are very useful. For example, the fact the GPO is signing government documents is important and valuable. It provides evidence that the document contains information the federal government currently wants you to believe. Similarly, the suggestion by Eric Hellman to use signatures to verify that Creative Commons licenses have been properly applied.

However, caution is needed when applying digital signatures to the problem of maintaining the integrity of digital documents in the long term. Details below the fold.


First, it is important to distinguish between detecting corruption or tampering, i.e. tamper-evident storage, and recovering from tampering, i.e. tamper-proof storage. Digital signatures are intended to provide tamper-evident storage. They do so by allowing a later reader to verify the signature. To do so, the readers needs the public half of the key used to sign the document. Without it, or with a corrupted public key, the signature is useless. Thus, strictly speaking, digital signatures do not solve the problem of tamper-evidence, they reduce it to the harder problem of tamper-proof storage, applied to a smaller set of bits (the public key). And even if they did solve it, maintaining integrity requires not tamper-evident but tamper-proof storage for documents.

Even tamper-proof storage of the public key alone is not enough. The signature's testimony as to the integrity of the document depends not just on the availability of the public key but also on the secrecy of the private key. As we see from recent compromises at RSA, Comodo, DigiNotar and others, maintaining the secrecy of private keys is hard. In fact, over the long term it is effectively impossible. So keys have a limited life. They are created and eventually revoked. In order to verify a signature over the long term, a reader needs access to a tamper-proof database of keys and the date ranges over which they were valid. Implementing such a database is an extraordinarily hard problem; for details see Petros Maniatis' Ph.D. thesis (PS).

Even if the practical problems of implementing a tamper-proof database could be overcome, the reader would know only the span of time over which the creator of the key believed that the secret had not leaked. Secrets don't ring a bell when they leak, so the creator might be unduly optimistic. And, of course, truly tamper-proof databases are a utopian concept, the best we can do in the real world is to make them tamper-resistant.

Basing the long-term integrity of digital documents on digital signatures, and thus on the ability to keep secrets for the long term is unwise. Fortunately, it is not necessary. There are at least two different approaches to doing so that do not depend on long-term secrets:

• The technique of entangling hashes, patented by Stuart Haber and others, and implemented in the ACE system, provides tamper-evident storage without secrets. It can detect but not recover from tampering using a minimum of tamper-proof storage. There are practical difficulties in implementing it securely enough, but these are much less significant than those involved in long-term use of digital signatures.
• The protocol underlying the LOCKSS system provides tamper-resistant storage against a powerful adversary without long-term secrets. It does use short-term secrets, whose life is a day or less, but it limits the damage caused if even these leak.

Duane's proposal depends heavily on the idea of a:

"Deep Archive (DA)." A DA is unique in that the servers and databases where all the original data is stored is disconnected from the Internet, which dramatically limits the exposure of the system and the data from attacks from the Internet. Access is only allowed out on a scheduled basis to receive system updates (e.g. Operating System enhancements, security patches, etc.).

The recent compromises of the US Air Force drone control systems and the Iranian centrifuges, which were never connected to the Internet, are examples of the fragility of this approach. "Air gaps" like this are never watertight, and even if they were they do not defend against other, equally likely attacks such as insider abuse (PDF).