(C) 1997 Ing. Miguel Angel Gallardo Ortiz , CEO of C.I.T.A.  

COOPERACIÓN INTERNACIONAL EN TECNOLOGÍAS AVANZADAS
C.I.T.A. SL, Apartado Postal (P.O. Box) 17.083 - 28080 Madrid, España
Tel.: (+34) 91 474 38 09 - Modem/Fax: (+34) 902 99 83 79, Internet E-mail: miguel@cita.es
This page has not been updated since 17 October 1997.

Technical Summary

When a traditional document is considered, a time forgery is a difficult task and it is easy for an expert witness to detect. On electronic documents, the opposite happens: time forgeries are too easy, and detections almost impossible.

If we consider economical and juridical transactions, exact date and time can be important and sensitive matters; they can even be used as evidence in court, therefore an exact, secure and verifiable Time Stamping Service (TSS) delivery system is needed for the EU Trusted Third Parties (TTP).

The aim of the project is to assess the role of TSS in ETS-II: its functional analysis, quality requirements, security profile, and implementation issues.

If we want to give a complete order of events in a distributed system it is necessary to associate a time-stamp with each event. However, this is not a physical time-stamp but rather a logical one. A digital timestamping protocol must have, at least, the following properties:

  • The data should be timestamped as well, with complete independence of the physical medium

  • It should be impossible to change a single bit of the document without that change being apparent

  • It should be impossible to timestamp a document with a forged date and time

    •

There are several well known protocols that can be preliminary classified as: arbitrated (with one-way hash functions), linking and distributed protocols. Our preliminary research recommends a TSS already developed which seems to be in State of The Art, however other solutions will be also considered with crucial role in non-repudiation (a secure time-stamp maintains the validity of a digitally-signed document even after the key has expired or compromised).

Once the best TSS is found, we will analyse the technical and juridical context in depth so as to find an easy way to have a common, secure and verifiable TSS for the EU.

 

PART 2: Technical description

1. Project Objectives

The European Trusted Services programme is a research initiative sponsored by the European Commission as part of its ongoing work in Security of Information Systems. It is a central part of the INFOSEC programme. In particular it addresses the issues in the provision of Trusted Third Party (TTP) services in the context of the European and Global Information Infrastructure. One of the main issues is the development of a Time Stamping Service (TSS) for ETS.

The main aims of this proposal are:

 

1.1 Introduction

This project is oriented to its functional analysis, quality requirements, security profile and implementation issues of TSS. We describe the procedures, the technical means, and the requirements of time stamping related to certification and key management as well as digital signed documents in the context that will be provided in the Trusted Third Parties environment of ETS-II.

A time-stamp is defined as a certain date & time information which all participants (e.g. partners, parties) trust and agree in regarding an electronic document, a connection or an interaction. At the time specified, a document was created then and from this moment $its format remains unchanged. This can be achieved only, if the date & time information is connected to the related document in a way that is unchangeable and unreverseable.

The aspect of time-stamping is related to signature and certificate aspects as well as to aspects of non-repudiation of origin and receipt, or non-repudiation of delivery.

Time stamps assume there is a common time reference which logically links a claimant and verifier, as a Co-ordinated Universal Time (e.g. GMT). A verifier will adopt an acceptance window of fixed size. On receipt of an authentication message, the verifier calculates the difference between the time-stamp in the message and the time of receipt. If this difference is within the window, the message is accepted. Uniqueness can be guaranteed by buffering copies of all messages received within the current window and rejecting any repeated message.

From the system point of view, the use of time-stamps within the ETS-II project depends upon the systems involved maintaining secure local clocks (real time clocks) which are periodically synchronised within a reliable source of time. There are several potential problems with this kind of approach:

  1. If a verifier system can be misled about the correct time, then old messages can be replayed very easily.

  2. If a legitimate principal system can be misled about the correct time, it can be induced to generate authentication requests which can be later replayed to a verifier with a sound time reference.

  3. If two parties’ clocks drift sufficiently, they become unable to communicate, leading to an availability problem.

  4. In the many networks which employ time servers and time-synchronisation protocols, the security of the authentication system becomes dependent upon the security of these servers or protocols respectively.

In many applications, and we think that also in every PKI architecture too, it is necessary to determine the order of events that have occurred in the system (A. Burns & A. Wellings "Real-Time Systems and Their Programming Languages", Addison Wesley, 1989). This presents no difficulty for uniprocessor or tightly-coupled systems, which have a common memory and a common clock. However, for distributed systems and networks, like the Internet, however, there is no common clock, and the delay which occurs in sending messages between processors means that these systems must have two important properties (Le Lann G. "Distributed systems - towards a formal approach" in Proceedings of the IFIP Congress, 1977, pp. 155-60, North Holland Publishing Company):

1. For any given sequence of events, it is impossible to prove that two different processes will observe, identically, the same sequence.

2. As state changes can be viewed as events, it is impossible to prove that any two processes will have the same global view of a given subset of the system state.

If processes in a distributed application are to coordinate and syncronize their activities in response to events as they occur, it is necessary to place an order on these events.

Therefore, it is necessary -once the document, messsage or certificate point of view is considered- to order all events totally in a distributed system it is necessary to associate a time-stamp with each event. However, this is not a physical time-stamp but, rather, a logical one.

A digital timestamping protocol must have (S. Haber and W. S. Stornetta, "How to Time-Stamp a Digital Document", Journal of Cryptology, v. 3, n. 2, 1991, pp. 99-112), at least, the following properties:

There are several well known solutions and patented systems that can be preliminary classified as:

Of course, digital time-stamp certificates also depend for their security on the difficulty of certain computational tasks concerned with so-called one-way hash functions. (All practical digital-signature systems depend on these functions as well.) Those who maintain a secure digital time-stamping service will have to remain abreast of the state of the art in building and in attacking one-way hash functions. Over time, they will need to upgrade their implementation of these functions, as part of the process of renewal. This will allow time-stamp certificates to remain valid indefinitely (D. Bayer, S. Haber, and W.S. Stornetta."Improving the efficiency and reliability of digital time-stamping" Sequences ´91: Methods in Communication, Security and Computer Science, Springer-Verlag, 1992, pp. 329-334).

1.2 Background

 

A TSS presumes a number of documents whose authors are distributed throughout a communication network. System time and electronic document time must be considered in ETS-II. So, the background must have at least two branches, one for the system and another one for the electronic documents.

 

1.2.1 System Time Background

Closely related to the issue of time is that of synchronization. In most of the timestamping systems syncronization among different machines is simply not an issue, because TTP programs must contain exactly one "thread of control", a single process, meaning that all objects, events and timestamps are sequential.

The UNIX functions ctime() and time() can be used together, with the latter providing the argument for the former. The ctime() function takes as an argument a pointer to the memory location holding the number of seconds since 1970. Timezone subroutine contains the difference in seconds between Greenwich Mean Time and local time. In OSF/MOTIF inter-client communication the target TIMESTAMP returns the time when the selection ownership was obtained. MS-Windows NT time domain as well as some other operating systems will be considered as well.

One of our ideas for TTPs can be developed when it is necessary for every message sent between processes to carry the time-stamp of the event that sent the message. Furthermore, everytime a process receives a message it must set its logical clock to a value which is:

 

This ensures that no message can seem to be received before it is sent, because using the above algorithm, all events in the system have an associated time-stamp and can be partially ordered accordingly. If two events have the same time-stamp then it is suffcient to use an arbitrary condition, such as the numeric value of process identifiers, to order the events totally.

For certain kinds of problems, an automated system may have to handle many different events simoultaneously. Other problems may involve so much computation that they exceed the capacity of any single processor. In each of these cases, it is natural to consider using a distributed set of computers for the target implementation or to use processors capable of multitasking. A single process -also known as a "thread of control"- is the root from which independent dynamic action occurs within a system. Every program has at least one thread of control, but a system involving concurrency may have many such threads: some that are transitory, and others that last the entire life-time of the system´s execution. Systems executing across multiple CPUs allow for truly concurrent threads of control, whereas systems running on a single CPU can only archive the illusion of concurrent threads of control, usuarlly by means of some time-slicing algorithm.

We have found it useful to express concurrency semantics for each individual operation as well as for the object as a whole, since different operations may require different kinds of syncronization. Message passing may thus take one of the following forms:

 

 

The form can be selected on an operation-by-operation basis, but only after the functional semantics of the operation have been decided upon.

From our point of vie, PKI architectures selected in Lot 1 Task 1 must consider this concurrency semantics.

 

1.2.2 Electronic Document Time Background

 

The "certificate" returned by the certification procedure of a digital time-stamping system is a certificate for a particular record (specifying what) at a particular time (specifying when). The procedure works by mathematically linking the bits of the record to a "summary number" that is widely witnessed by and widely available to members of the public--including, of course, users of the system. The computational methods employed ensure that only the record in question can be linked, according to the "instructions" contained in its time-stamp certificate, to this widely witnessed summary number; this is how the particular record is tied to a particular moment in time. The verification procedure takes a particular record and a putative time-stamp certificate for that record and a particular time, and uses this information to validate whether that record was indeed certified at the time claimed by checking it against the widely available summary number for that moment.

A number of different methods have been proposed and implemented for managing the keys of a digital signature system -- both the private signing keys and the corresponding public validation keys -- and for keeping track of which keys are "valid" (according to an appropriate notion of validity). However the keys are managed, part of the process of verifying a particular signature for a particular document and a particular public key should be a validation that the signature was computed at a point in time when the key was presumed to be valid. This is especially important for signed digital documents that are meant to be long-lasting.

A good way to do this is to include -as part of the protocol for signing a long-lived digital document- the computation of a cryptographically secure time-stamp for the document-signature pair. Preferably, this should be a time-stamp whose trustworthiness does not itself depend on the long-term assurance that a cryptographic key remain physically and mathematically uncompromised.

Two features of a digital time-stamping system are particularly helpful in enhancing the integrity of a digital signature system. First, a time-stamping system cannot be compromised by the disclosure of a key. This is because digital time-stamping systems do not rely on keys, or any other secret information, for that matter. Second, following a technique already introduced, digital time-stamp certificates can be renewed so as to remain valid indefinitely.

With these features in mind, any TTP must to consider the following situations.

It sometimes happens that the connection between a person and his or her public signature key must be revoked--for example, if the user's secure access to the private key is accidently compromised; or when the key belongs to a job or role in an organization that the person no longer holds. Therefore the person- key connection must have time limits, and the signature verification procedure should check that the record was signed at a time when the signer's public key was indeed in effect. And thus when a user signs a record that may be checked some time later--perhaps after the user's key is no longer in effect--the combination of the record and its signature should be certified with a secure digital time-stamping service.

There is another situation in which a user's public key may be revoked. Consider the case of the signer of a particularly important document who later wishes to repudiate his signature. By dishonestly reporting the compromise of his private key, so that all his signatures are called into question, the user is able to disavow the signature he regrets. However, if the document in question was digitally time-stamped together with its signature (and key-revocation reports are time-stamped as well), then the signature cannot easily be disavowed in this way. This is the recommended procedure, therefore, in order to preserve the non-repudiability desired of digital signatures for important documents.

The statement that private keys cannot be derived from public keys is an over-simplification of a more complicated situation. In fact, this claim depends on the computational difficulty of certain mathematical problems. As the state of the art advances--both the current state of algorithmic knowledge, as well as the computational speed and memory available in currently available computers--the maintainers of a digital signature system will have to make sure that signers use longer and longer keys. But what is to become of documents that were signed using key lengths that are no longer considered secure? If the signed document is digitally time-stamped, then its integrity can be maintained even after a particular key-length is no longer considered secure.

Of course, digital time-stamp certificates also depend for their security on the difficulty of certain computational tasks concerned with so-called one-way hash functions. (All practical digital-signature systems depend on these functions as well.) Those who maintain a secure digital time-stamping service will have to remain abreast of the state of the art in building and in attacking one-way hash functions. Over time, they will need to upgrade their implementation of these functions, as part of the process of renewal. This will allow time-stamp certificates to remain valid indefinitely.

Further improvements to timestamping protocols are presented in the enclosed abstracs of three United States patents (the creators offered their support to this tender by E-mail). Surety technologies at <http://www.surety.com> already developed a Digital Notary System to support this protocols, and this company recommended to publish a hash of the day´s timestamps in a public place, such a newspaper. This serves a function similar to sending the hash to random people in distributed protocol. In fact, a timestamp has appeared in every Sunday´s New York Times since 1992.

It is quite reasoneble that the European Community could do something like that in an official media, after the conclusions of this ETS-II and the full understanding of the best patents for Time Stamp Services.


(C) 1997 Ing. Miguel Angel Gallardo Ortiz , CEO of C.I.T.A.  

COOPERACIÓN INTERNACIONAL EN TECNOLOGÍAS AVANZADAS
C.I.T.A. SL, Apartado Postal (P.O. Box) 17.083 - 28080 Madrid, España
Tel.: (+34) 91 474 38 09 - Modem/Fax: (+34) 902 99 83 79, Internet E-mail: miguel@cita.es
This page has not been updated since 17 October 1997.