Dec 31 2009

Time-Stamping Eternity

A step-by-step approach offers agencies a way to gain long-lived digital integrity using short-lived hash functions.

One-way hash functions are fundamental tools in cryptography and computer security.

These algorithms, commonly used in software and hardware, take a digital file or message of arbitrary length and compress it to produce a short, fixed-length output. For example, Secure Hash Algorithm 1 (SHA-1), standardized by the National Institute of Standards and Technology in 1995 and the most widely used hash function, produces 20-byte outputs.

The hash value for a particular file can serve as a proxy — a digital fingerprint, as it were — for the file itself, especially as part of a procedure for guaranteeing the bit-by-bit integrity of the file. Checking that the hash value computed for a file or message exactly matches a hash value that has been stored or computed separately is at the heart of verification procedures for digital time-stamp certificates and for digital signatures, as well as forming part of the cryptographic handshake of forming a secure browser connection to a Web server.In the past three years, cryptographic researchers have developed powerful new attacks on hash functions. The predecessor to SHA-1 as the de facto standard one-way hash function was MD5, still in widespread use even though its use has been officially discouraged — or deprecated — for more than 10 years.

With normal advances in computational power and resources, and with further improvements in algorithmic techniques, agencies can expect that a collision-finding attack on SHA-1 could be practical fairly soon. Last spring, NIST recommended that agencies stop using SHA-1 for digital signatures, digital time stamping and other applications that require collision resistance as soon as practical and begin using SHA-2 instead.

This situation poses the problem of what to do with the abundance of time-stamp certificates and digital signatures that federal systems have computed using SHA-1 or MD5.

Renewing the Stamp

A digital time-stamping system provides a way to compute, for any digital file or message, a certificate that anyone can later use, along with the file itself, to verify the file existed at the time listed in the certificate. There are a number of different time-stamping systems of varying quality in use. But all of them use one-way hash functions, so they all pose a risk.

To be specific, suppose that you have a particularly important digital document, which you time-stamped in January 2002 using a time-stamping system offered by Acme Time-Stamping. You have saved the file along with its Acme time-stamp certificate (and properly backed up your data). Back in 2002, Acme’s system used SHA-1 as its one-way hash function. Now it’s spring 2007, and your Acme certificate is perfectly trustworthy, but you are worried about expected improvements in attacks on SHA-1.

Then you read about the deployment by Bravo Time-Stamping of an improved time-stamping system that uses SHA-256 (a function from the SHA-2 family having 32-byte outputs). Bravo may be running the same system as Acme with SHA-256 replacing SHA-1 in the computation of new time-stamp certificates, or perhaps Bravo is commercializing a new time-stamping algorithm. In either case, you would like to be able to use Bravo’s system to buttress the guarantee of integrity supplied by the five-year-old Acme certificate for your document.

You could simply use Bravo to time-stamp your document to obtain a new time-stamp certificate for it. Al­­though the new certificate would be completely invulnerable to attacks on SHA-1, it would also be completely useless as proof your document existed in 2002.Instead, you might use Bravo to time-stamp your Acme certificate, saving both the new Bravo certificate and the old Acme certificate along with your document, and have verifiers of your document’s integrity check both of the certificates.

But this approach would still be vulnerable to the later existence of a devastating attack on SHA-1. Suppose it becomes possible later to find a document different from yours — maybe even one that looks the same as your document with a small incriminating change to one of the words — that has the same SHA-1 hash value as your document does. (This is not likely to happen any time soon, but it’s crucial to avoid as many conceivable failures as possible.) Because the only link between your document and its Acme time-stamp certificate is by way of its SHA-1 hash value, the combination of the two certificates would be no better at proving the 2002 date for your document than it would be for the newly computed colliding document.

The solution is to make a compound time-stamping request to Bravo, asking for a new time-stamp certificate for the combination of both your original document and its Acme certificate. This new certificate should be saved, of course, along with the document and the old certificate, and full verification of the integrity of your document requires, in turn, both systems’ verification procedures.

Why It Works

Suppose that a catastrophic attack on SHA-1 is indeed discovered and announced in 2010, and that in the meantime SHA-256 is still regarded as a secure one-way hash function.

The Bravo certificate provides evidence that both your document and its Acme certificate existed at a time, in spring 2007, when the Acme certificate was trustworthy. And by virtue of its trustworthiness in 2007, it would make sense in 2010 to trust the Acme certificate’s assertion that your document existed in December 2002. Thus, you have successfully “renewed” your document’s time-stamp certificate.Notice that the security offered by this renewal process depends on the arguably questionable assumption that SHA-1 was not compromised until a definite time after you applied Bravo’s time-stamping system, which uses SHA-256. In practice, this is not an unreasonable assumption.

Advances in cryptanalytic attacks on hash functions typically proceed incrementally, and well before a hash function is completely broken, fielded systems can swap in a new hash function. The computer security community is doing exactly this right now, following the recommendations of NIST.