Time-Stamping Eternity

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

Stuart Haber, a holder of patents for time-stamping technology and co-founder of Surety, is a researcher at HP Labs in Princeton, N.J., and serves as a director of the International Association for Cryptologic Research.

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. Although 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.

What Makes a Hash a Hash?

When designing hash algorithms,cryptographers try to achieve two things:

First: They are one-way. Given a hash value (an output of the hash function), it is effectively impossible to find an input that produces exactly this output.

Second: It is effectively impossible to find a pair of distinct inputs for the hash function that produce the same hash value. Such a pair of inputs is called a collision for the hash function, and this property is called “collision resistance.” What does it mean to say that these computational tasks are “effectively impossible?” They simply cannot be performed in a reasonable amount of time by any computation.

Next-Gen Hashes

The four functions in the SHA-2 family have output lengths of 28, 32, 48 and 64 bytes (compared to SHA-1’s 20 bytes). These functions are not known to be vulnerable to the current suite of attacks, but they build on the design technique that led to MD5, as does SHA-1.

Therefore, it would be prudent to have in hand another method for one-way hashing. Given this reality, the National Institute of Standards and Technology launched an international design competition for new hash functions. It used a similar development approach for the Advanced Encryption Standard.

Online Exclusive:

Safeguarding the Integrity of Digital Signatures

Just as with time-stamps, there are ways to bolster digital signatures that use one-way hash algorithms.

Use the scenario of the important document created in January 2002. Suppose that instead of using the Acme time-stamping service, you digitally signed it and saved the resulting signature with your file. If you were using an up-to-date digital signature system in 2002, then the signature was computed using the SHA-1 hash value of your file.

Leap ahead to today, spring 2007. You’re still worried about future attacks on SHA-1, because anyone who might use one of these attack methods to produce an incriminating document that collides with your document under SHA-1 could then use your signature on your own document as a “valid” signature, verifiable as yours, on the incriminating document instead. You learn about the fictional Bravo Time-Stamping company’s offering of a time-stamping system that uses SHA-256, and you wonder whether Bravo can help you.

Indeed it could. You could submit a compound time-stamping request to Bravo, asking for a new time-stamp certificate for the combination of both your original document and your signature. Just as with the time-stamp renewal procedure, the Bravo certificate would be evidence for the existence of both your document and its signature in spring 2007, when evidence using SHA-1 was still trustworthy.

There is an extra complication with digital signatures, having to do with the validity of the public key used to verify the signature. Your public key from 2002 may have been registered with a public-key infrastructure (PKI). In the winter of 2001, someone who wanted to verify your signature on that document would have needed a secure link between your public key and your name — or, for example, your e-mail address or your job title. That’s the purpose of the PKI. Though not many users do this, an especially skeptical verifier might have configured his or her software to find and check extra PKI information for this purpose — by consulting a certificate revocation list or using the Online Certificate Status Protocol, for example.

Unfortunately, many current PKIs don’t accommodate truly long-term verifiability, and PKI information might no longer be easily available for a five-year-old public key. If it is available, then it should be included in the compound request to Bravo, and this would simplify the task of the especially skeptical signature verifier in the year 2010 or later. If it is not available in 2007, it is even more likely to be unavailable in 2010, and you will have to make do without it, but nevertheless you will have insulated yourself against new attacks on SHA-1.