People's Newsroom


Time-stamping services produce time-stamp tokens as evidence to prove that digital data existed at given points in time. Time-stamp tokens contain verifiable cryptographic bindings between data and time, which are produced using cryptographic algorithms. In the ANSI, ISO/IEC, and IETF standards for time-stamping services, cryptographic algorithms are addressed in two aspects.

  • Client-side hash functions used to hash data into digests for nondisclosure
  • Server-side algorithms used to bind the time and digests of data

These algorithms are associated with limited lifespans due to their operational life cycles and increasing computational powers of attackers. After the algorithms are compromised, time-stamp tokens using the algorithms are no longer trusted. The ANSI and ISO/IEC standards provide renewal mechanisms for time-stamp tokens. However, the renewal mechanisms for client-side hash functions are specified ambiguously, which may lead to the failure of implementations. Besides, in existing papers, the security analyses of long-term time-stamping schemes only cover the server-side renewal, and the client-side renewal is missing.

Digital data is ubiquitous in our modern world. To prove the existence time of digital data, a time-stamping service produces verifiable cryptographic bindings between digital data and time to form time-stamp tokens. Such cryptographic bindings could be digital signatures, hash values, message authentication codes, etc. Most of the bindings are generated through cryptographic algorithms. Therefore, time-stamp tokens are valid only when the underlying cryptographic algorithms remain secure. For time-stamping services specified in the ANSI, IETF, and ISO/IEC standards, the cryptographic algorithms used to generate time-stamp tokens could be categorized into two sides.

  • Client-side hash functions used to hash data into digests for nondisclosure
  • Server-side algorithms used to bind digests of a data item and a given point in time

These algorithms are time-restricted due to their limited operational life cycles and the increasing computational power of attackers. For instance, the upcoming quantum computers are considered to break some broadly-used signature algorithms and increase the speed of attacking hash functions. Once the algorithms are compromised, the corresponding time-stamp tokens are no longer valid. However, for many types of digital data, the validity of time-stamp tokens needs to be maintained for a long time. For example, the identity information of citizens should be kept permanently; the health records of people follow their lifetimes; mp3 files produced by musicians may last for decades, etc. In these cases, the validity periods of time-stamp tokens need to be longer than any individual cryptographic algorithm’s lifetime.

The ANSI and ISO/IEC standards provide time-stamp renewal mechanisms for both client-side and server-side algorithms. For server-side renewal, the standards clearly say that a requester sends a time-stamp request by inputting a new server-side algorithm identifier, hash value(s) of a data item, and a previous time-stamp token on this data item to a Time-Stamping Authority (TSA), the TSA then produces a new time-stamp token on the input content using the indicated algorithm. However, the client-side renewal mechanisms in both standards are specified ambiguously. In the ISO/IEC standard, the renewal of client-side hash functions is not mentioned as a motivation for time-stamp renewal, and how to implement the client-side renewal is not explicitly specified. In the ANSI standard, a list of reasons for time-stamp renewal includes that a requester needs to replace the hash value using a stronger hash function, but when a requester “needs” to replace the hash value is not specified in detail. These ambiguities may cause the failure of client-side renewal implementations and therefore the failure of long-term time-stamping services. 

Nevertheless, the analyses are only related to renewal mechanisms of server-side algorithms, the client-side renewal is not covered. Specifically, in the security model, the client-side renewal is not discussed, and client-side hash functions are treated as random oracles. This security notion does not truly model the case of practical implementations. The motivation of this work is based on the following observation. The security of the client-side is as significant as the server-side since the time-stamp tokens are generated on the hash values of data items. If the client-side hash functions are broken and the client-side renewal mechanism is not performed effectively, the time-stamp tokens are no longer valid regardless of whether the server-side is secure or not. Even if a client-side renewal mechanism is clearly specified, a formal security analysis of the mechanism is necessary and it does not exist in the literature. After that, we formally analyze the client-side security of our proposed long-term time-stamping scheme and provide a quantified evaluation of the client-side security level.


A secure hash function maps a string of bits of variable (but usually upper bounded) length to a fixed-length string of bits, satisfying the following three properties:

Preimage Resistance: it is computationally infeasible to find, for a given output, an input that maps to this output.

Second Preimage Resistance: it is computationally infeasible to find a second input that maps to the same output.

Collision Resistance: it is computationally infeasible to find any two distinct inputs which map to the same output.

Note that the hash functions discussed in this paper are compression functions. That means, the collision resistance of a hash function implies preimage resistance. In other words, if a hash function is collision-resistant, then it is also preimage resistant; if a hash function is not preimage resistant, then it is not collision-resistant.


There are two types of time-stamp tokens that can be generated by a time-stamping service.

Independent tokens: An independent time-stamp token can be verified without involving other time-stamp tokens. The protection mechanism used to generate this type of token can be digital signatures, message authentication codes (MAC), archives, or transient keys. For instance, for signature-based time-stamping, a Time-Stamping Authority (TSA) digitally signs a data item and a time value that results in a cryptographic binding between the data and time. The data, time, and the corresponding signature together form a time-stamp token.

Linked tokens: A linked time-stamp token is associated with other time-stamp tokens produced by the same methods. The protection mechanism used to generate this type of token can be hash functions and a public repository, therefore a time-stamping service generating this type of token is referred to as “hash-based time-stamping” or “repository-based time-stamping”. In specific, a TSA hashes a data item and a time value together and aggregates the hash output with other data items produced at the same time, (e.g., uses a Merkle Tree). The aggregation result can be linked to other data produced at previous times, (e.g., uses linear chain linking). Eventually, the aggregation or linking result is published in widely visible media (e.g., newspapers). The data, time record, published information, and group values that are contributed to determining the published result, together form a time-stamp token.


There are two time-stamp transactions that are performed between a requester and one or more TSAs, or between a requester and a verifier, respectively.

Time-stamp request transaction: A requester sends a time-stamp request to a TSA and the TSA returns a time-stamp response to the requester.

Time-stamp verification transaction: A requester sends a verification request to a verifier and the verifier returns a verification response to the requester.

A timestamp request contains a “messageImprint” field, which is comprised of a hash value of a data item and its hash function identifier, an “extensions” field, and other information. More specifically, the “extensions” field contains three types of additional information: ExtHash, ExtMethod, and ExtRenewal, which work as follows.

ExtHash: In this field, a requester could submit multiple “messageImprint” fields, in which each hash value could be computed from a different hash function so that it prevents the failure of any single hash function.

ExtMethod: In this field, a requester could indicate a specific protection mechanism (e.g., a digital signature scheme) to bind the data item and time.

ExtRenewal: In this field, a requester could submit an existing time-stamp token on the data item for the purpose of extending the validity period of the time-stamp token.

After the TSA receives the request, it adds the current time to the requested content to form a “TSTInfo” structure and produces a cryptographic binding on the TSTInfo by using the indicated protection mechanism or a default one if it is not indicated. The TSTInfo and the cryptographic binding together form a time-stamp token, then the TSA returns a time-stamp response with the time-stamp token to the requester. In order to validate the time-stamp token, the requester could send a verification request that contains the time-stamp token to a verifier at time tv. For a single time-stamp token that has not been renewed, the verifier checks the following.

  • The token is syntactically well-formed
  • Every hash value of the data item is correctly computed through the corresponding hash function
  • At least one of the hash functions that is used to generate digests of the data item is collision-resistant at tv
  • The protection mechanism of the time-stamp token is not broken on tv
  • The cryptographic binding is correctly computed on the data and time

If all the above conditions are held, the time-stamp token is valid at time tv, so the verifier returns a verification response with a “true” result to the requester. Otherwise, the verifier returns a “false” result to the requester. For a renewed time-stamp token, the verifier checks the validity of each nested time-stamp token at the time it was generated or renewed, and the validity of the latest time-stamp token at tv following the above checking steps. The verifier returns a verification response with a “true” result to the requester if all verifications are successful, or a “false” otherwise. We argue that the short-term nondisclosure of our scheme could be accepted since integrity could naturally be required for a much longer time than nondisclosure. For instance, intellectual-property data is usually protected in secret for a certain period before it is released but its integrity should be maintained in perpetuity.

Back to top button