Transient-key digital time-stamps

Michael D. Doyle, Ph.D.
September 22, 1997
Patent Pending

1.0 Introduction

A system is described for the creation and use of irrefutable public key digital signature time-stamps. The system is based upon the concept of transient time-interval-related secret cryptographic keys, which are used to digitally sign submitted data during specific time intervals, and then are permanently destroyed. The public-key correlate for each time interval is saved for future authentication of the content of and time of creation of time-stamped data. The validity of the public keys is ensured through the certification of each time interval's public key using the previous time interval's secret key, immediately before that secret key is destroyed.

2.0 Background

2.1 Chain of evidence

The concept of chain of evidence has long been a fundamental tenet of the U.S. judicial system. Many legal situations depend upon the ability to prove that a certain piece of evidence existed at a certain point in time and that it hasn't been altered since then. In the past, when most of the possible types of evidence consisted of material objects, there was a need for a protocol of a "chain of witnesses" to testify to the veracity of an evidentiary object in question. Historically, if the evidence was under the control of only a finite set of individuals, and if all of those individuals could testify as to the location and state of the object, then the court would accept the claim of authenticity of the evidence.

2.2 Witnesses

Of course, such a system is dependent upon the availability of trustworthy witnesses that will be available and willing to testify in any given circumstance. Often times, witnesses are available, but not trustworthy, or vice versa. This is particularly the case with respect to document authentication, where the details of when a specific document was created or signed is in question. Clearly, a system was needed to allow one to easily obtain a "witness on demand" in many situations.

2.3 Notary public

This concept of evidentiary authentication is so important to so many areas of endeavor, that a formalized system of professional document witnesses was developed, called the Notary Public service. Notary Publics would, for a fee, attest to such things as the existence of a document and the identity of the document holder or signer. Of course a notary could not swear to any knowledge of the actual contents of a document, since that would have required that the notary keep copies, in perpetuity, of every document s/he witnessed during his or her career -- an impractical requirement. Much of the trust held in the notary public system related to a generally-held belief that it was impossible or impractical to forge a notary public's stamp and signature, or to buy a notary public's testimony. As computer graphics and desktop publishing technology advanced, however, the level of difficulty of creating forged documents and signatures has decreased significantly. A significant result of this technological advance is the fact that many states no longer accept notarization as proof of document validity.

2.4 Time stamping in databases

As more and more of the information of import in personal and business transactions becomes digital in form, the usefulness of notary-public-style authentication mechanisms become less useful. Much of this information is stored accessed and managed through computer database management systems. All major database systems permit time stamping of data in records. Many commercial and governmental systems depend upon the assumption of veracity of such database time stamps. The presumption is that, if the organization is trustworthy, then the time stamps in their databases can be believed. In practice, this assertion requires a large degree of, to borrow a literary term, "willing suspension of disbelief." No one, of course, can safely assume that all individuals within a large organization are trustworthy, even if the organization, itself, is believed to be so. Furthermore, it is now well known that no conventional computer database system is immune from the possibility of data tampering or "hacking" by dishonest individuals.

2.5 Public-key encryption

One approach that has been developed to deal with some of this problem is based upon a technology called "public key" cryptography. One of the most well known of this type of system is the program called Pretty Good Privacy, distributed by the Massachusetts Institute of Technology, which makes use of the Rivest-Shamir-Adleman (RSA) public key cryptosystem. Such systems are built around the concept of encrypting data in such a way that allows both secure transmission and authentication of sensitive data. Public key systems employ a pair of cryptographic keys for each encryption/decryption event. One key is kept secret by the owner, and the other key is publicly distributed. A message encrypted with one of the keys in a key pair can only be decrypted with the other key, and vice versa.

This system allows, for example, the encryption of data by one individual, using a second individual's public key. The message could then be sent to a second individual over unsecure channels, and only the second individual could access the unencrypted data, since it could only be decrypted with the second individual's private key.

2.5.1 Digital signatures

Prior to using the second individual's public key to encrypt the data, the first individual could have used his or her private key to encrypt the data, thereby digitally "signing" the data, so that the recipient could then use the sender's public key to decrypt it, thus proving that it actually came from the sender, since only he or she could have used the correct secret key to sign the data. Such a system provides both confidentiality of data and a mechanism for authentication of the identity of the sender. It also proves that the data could not have been altered in any way since the time it was encrypted by the sender. Public keys, themselves, can be "certified" by signing them with a trusted individual's secret key. Others can then assess the authenticity of published public keys by authenticating them using that trusted individual's public key.

2.5.2 Message digests

Public key algorithms are notoriously slow. For this reason, virtually all public key digital signature systems use what is called a "cryptographically-strong one-way hash function" to create what is called a "message digest" from the data to be signed. This message digest is a unique representation of that data, sort of a data fingerprint, that is typically much smaller than the original data. The message digests that PGP uses are only 128 bits in length. The message digest is then encrypted using the sender's secret key before sending the data to the recipient. The recipient can then use the sender's public key to automatically decrypt the message digest and then verify that it does indeed match the original data. This is a very secure system, since it is computationally infeasible for an attacker to devise a substitute message that would provide an identical message digest. Most estimates state that it would take 10^12 or more years (taking into account Gordon Moore’s "law" relating to increases in chip capacity over time) to successfully fake a 128-bit message digest using the algorithm employs by the PGP software package. Also, changing even a single byte of a digested message would cause the hash function to be unable to match the message digest to the unencrypted data.

Public key digital signatures, therefore, can irrefutably prove that signed data was originally signed by a given secret key and that the data has not changed in any way since the signature was made. Systems such as PGP routinely attach time-stamps to both key pairs at their creation, and to digital signatures, each time they are created. Such time-stamps, however, are dependent only upon the internal clocks within the computers being used, and thus are subject to inaccuracies or falsification by, for example, an individual intentionally changing the time on a computer's clock in order to make it falsely appear that a given digital signature was created at a specific point in time.

2.6 Digital notary public

For this reason, a new type of notary public has arisen, which uses public-key digital signatures to notarize, for a fee, digital information typically submitted over the Internet. These so-called "digital notaries" are, essentially, businesses that provide such a service and agree to attest to the veracity of both the content of the original data, as well as the time at which the signature was made. This is a major improvement over the notary public concept of old, since the new digital notary services can testify to the fact that data which has been digitally signed by their service existed at a certain point in time, and that it hasn't been altered in any way since that point in time.

2.7 Need for a rigorous self-proving method

The largest problem with such digital notary services, and also the primary motivating reason behind the existing system, is the fact that the authenticity of such digital-notary-generated digital signatures is wholly dependent upon the trustworthiness of the institution and individuals running the digital notary service.

To solve this problem, a system is needed that will automatically and rigorously prove the veracity of digital signature time-stamps, without depending upon the trustworthiness of the institution or individuals administering a digital notary service. Transient-key digital time-stamps provide these capabilities.

3.0 Objects and Advantages of Transient-key digital time-stamps (TKDTS)

3.1 A primary object and advantage of the system is that it provides a mechanism to irrefutably prove that a collection of data existed at a given interval of time, and hasn't changed since that interval of time.

3.2 A significant advantage of this system is that it provides non-repudiation to the user. It is difficult-to-impossible to deny the veracity of the time-stamp certificates generated by this system.

3.3 The system does not depend upon the trustworthiness (or later existence) of any external "certification authority" or external time tracking system.

3.4 All that is needed to authenticate the time stamp is the time-stamped data, the signature from the time-stamp certificate, the time interval's public key from the time-stamp certificate, and a standard public-key authentication program, such as either the free or commercial version of PGP.

3.5 The system will work with any kind of computer data.

3.6 Systems based upon Transient-Key Digital Time-Stamps can be set up as Internet servers, stamping all requests on a fee-for-service basis.

3.7 The time of creation and the internal state of information can be proven without endangering the confidentiality of sensitive data. This makes the technology ideal for use in invention documentation systems. This also means that the system can be used to authenticate critical confidential records, such as medical records and financial transactions.

3.8 The system can be easily adapted to any computing platform, and is not dependent upon any specific public-key algorithm

4.0 Summary of TKDTS system architecture

The TKDTS system uses public key cryptography in a new way to, first, create key pairs that correspond not to fixed entities, such as previous systems employ, but which correspond to transient time intervals; and second, to provide a mechanism to use the keys, and signatures created by those keys, to provide rigorous proof of the time of existence and the authenticity of the content within data signed by the system. A key feature of the system is that the secret key for a given time interval only exists for a finite, typically very short, period of time, and is replaced by subsequent secret keys as subsequent time intervals proceed.

A public key cryptography system, such as PGP, is employed to automatically generate a series of public-key encryption key pairs at regular time intervals. Each key contains a designation, typically within the key's user ID, which identifies the specific time interval during which it is to be (or was) used. For dynamically-created keys, the minimum possible duration of a time interval is limited by the time necessary for creation of a key pair and the use of that key pair to validate a public key. Shorter time intervals can be enabled by pre-generating the key pairs

The veracity of the time designation is proven by "chaining" of signatures, so that each new time interval's public key is certified (digitally signed) using the prior interval's secret key, immediately prior to deleting that prior time interval's secret key

This is done by using the prior time interval's secret key to digitally sign the new time interval's public key. Immediately after the public key is signed, the prior interval's secret key is deleted

The public key of each key pair is stored for future use. Any given private key is used for time-stamping data only during the time interval (the interval of use) immediately following the interval within which the private key was generated. During its interval of use, the secret key is used to digitally sign and time-stamp all data submitted to the system for such processing.

As data is submitted to the system for time-stamping, these data are processed by signing them using the respective time interval's private key. This signing process generates a time-stamp certificate. Each time-stamp certificate consists of the digital signature of the data generated by the secret key and the certified public key for the current time interval of use. Each interval-of-use's public key can be also archived for future reference, and for use in easy authentication of time-stamp certificates in the future, all time-stamp certificates can be archived as well, although it should be pointed out that such time-stamp certificate archiving is not necessary for later proof of the veracity of time-stamps generated by the system.

At the end of each time interval, a new key pair is generated, the public key of the new pair is certified (signed) by the current time interval's secret key, and that secret key is then deleted, and the cycle continues.

Validation of a time-stamp at any later point requires using the respective time interval's public key to authenticate the digital signature in the time-stamp certificate. Validation of that public key is accomplished by using the previous time interval's public key to authenticate the certification signature on the public key to be authenticated. The ability to trace back through the "chain" of public key certification signatures provides irrefutable proof of the location, in time, of any individual time interval's stamp within the chain of signatures. Further evidence of the exact time that a given time interval key was in use can be provided by tracking other certificates that were generated by the same key and collecting evidence of the time of generation of those signatures and the signed data relating to them.

Since the secret key for each time interval is destroyed immediately after that time interval passes, it is virtually impossible to create a bogus time-stamp after the fact.

Many other implementations of the TKDTS system are possible as well. For example, one could calculate the message digests at the users' sites, and send only those message digests to the server for signing. This would both insure confidentiality of data and efficient network bandwidth usage.