Linked Timestamping
Encyclopedia
Linking-based time-stamping is a type of trusted timestamping
where issued time-stamps are related to each other.
. Later modification of issued time-stamps would invalidate this structure. Temporal order of issued time-stamps is also protected by this data structure, making backdating of the issued time-stamps impossible, even by the issuing server itself.
Top of the authenticated data structure is generally published in some hard-to-modify and widely witnessed media like printed newspaper
. There are no (long-term) private keys
in use, avoiding PKI
-related risks.
Suitable candidates for authenticated data structure are:
Simplest linear hash chain based time-stamping is illustrated on following drawing:
The linking-based time-stamping authority (TSA) usually performs the following distinct functions:
Aggregation
Linking
Publishing
. Continuity of operation is observable by users; periodic publications in widely-witnessed media provide extra transparency.
Tampering with absolute time values could be detected by users, whose time-stamps are relatively comparable by system design.
Absence of secret keys increases system trustworthiness. There are no keys to leak and hash algorithms are considered more future-proof than modular arithmetic based algorithms, e.g. RSA.
Linking-based time-stamping scales well - hashing is much faster than public key cryptography. There is no need for specific cryptographic hardware with its limitations.
The common technology for guaranteeing long-term attestation value of the issued time-stamps (and digitally signed data) is periodic over-time-stamping of the time-stamp token. Because of missing key-related risks and of the plausible safety margin of the reasonably chosen hash function this over-time-stamping period of hash-linked token could be an order of magnitude longer than of public-key signed token.
Tree-like schemes and operating in rounds were proposed by Benaloh and de Mare in 1991 and by Bayer, Haber and Stornetta in 1992.
Benaloh and de Mare constructed a one-way accumulator in 1994 and proposed its use in time-stamping. When used for aggregation, one-way accumulator requires only one constant-time computation for round membership verification.
Surety started the first commercial linking-based time-stamping service in January 1995. Linking scheme is described and its security is analyzed in the following article by Haber and Sornetta.
Buldas et al. continued with further optimization and formal analysis of binary tree and threaded tree based schemes.
Skip-list based time-stamping system was implemented in 2005; related algorithms are quite efficient.
for the number of time stamps issued during the aggregation period; it is suggested that it is probably impossible to prove the security without this explicit bound - the so-called black-box reductions will fail in this task. Considering that all known practically relevant and efficient security proofs are black-box, this negative result is quite strong.
Next, in 2005 it was shown that bounded time-stamping schemes with a trusted audit party (who periodically reviews the list of all time-stamps issued during an aggregation period) can be made universally composable - they remain secure in arbitrary environments (compositions with other protocols and other instances of the time-stamping protocol itself).
Buldas, Laur showed in 2007 that bounded time-stamping schemes are secure in a very strong sense - they satisfy the so-called "knowledge-binding" condition. The security guarantee offered by Buldas, Saarepera in 2004 is improved by diminishing the security loss coefficient from
to 
.
The hash functions used in the secure time-stamping schemes do not necessarily have to be collision-resistant or even one-way; secure time-stamping schemes are probably possible even in the presence of a universal collision-finding algorithm (i.e. universal and attacking program that is able to find collisions for any hash function). This suggests that it is possible to find even stronger proofs based on some other properties of the hash functions.
At the illustration above hash tree based time-stamping system works in rounds (
, 
, 
, ...), with one aggregation tree per round. Capacity of the system (
) is determined by the tree size (
, where 
denotes binary tree depth). Current security proofs work on the assumption that there is a hard limit of the aggregation tree size, possibly enforced by the subtree length restriction.
part 3 covers 'Mechanisms producing linked tokens'.
American National Standard
for Financial Services, "Trusted Timestamp Management and Security" (ANSI ASC X9.95 Standard
) from June 2005 covers linking-based and hybrid time-stamping schemes.
There is no IETF
RFC
or standard draft about linking based time-stamping. RFC 4998 (Evidence Record Syntax) encompasses hash tree and time-stamp as an integrity guarantee for long-term archiving.
Trusted timestamping
Trusted timestamping is the process of securelykeeping track of the creation and modification time of a document. Securityhere means that no one — not even the owner of the document — should be able to change it once it has been recorded provided that the timestamper's integrity is never...
where issued time-stamps are related to each other.
Description
Linking-based time-stamping creates time-stamp tokens which are dependent on each other, entangled into some authenticated data structureData structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
. Later modification of issued time-stamps would invalidate this structure. Temporal order of issued time-stamps is also protected by this data structure, making backdating of the issued time-stamps impossible, even by the issuing server itself.
Top of the authenticated data structure is generally published in some hard-to-modify and widely witnessed media like printed newspaper
Newspaper
A newspaper is a scheduled publication containing news of current events, informative articles, diverse features and advertising. It usually is printed on relatively inexpensive, low-grade paper such as newsprint. By 2007, there were 6580 daily newspapers in the world selling 395 million copies a...
. There are no (long-term) private keys
Public-key cryptography
Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
in use, avoiding PKI
Public key infrastructure
Public Key Infrastructure is a set of hardware, software, people, policies, and procedures needed to create, manage, distribute, use, store, and revoke digital certificates. In cryptography, a PKI is an arrangement that binds public keys with respective user identities by means of a certificate...
-related risks.
Suitable candidates for authenticated data structure are:
- Linear hash chainHash chainA hash chain is the successive application of a cryptographic hash function to a piece of data. In computer security, a hash chain is a method to produce many one-time keys from a single key or password...
, - Hash treeHash treeIn cryptography and computer science Hash trees or Merkle trees are a type of data structure which contains a tree of summary information about a larger piece of data – for instance a file – used to verify its contents. Hash trees are a combination of hash lists and hash chaining, which in turn are...
(Merkle tree), - Skip listSkip listA skip list is a data structure for storing a sorted list of items using a hierarchy of linked lists that connect increasingly sparse subsequences of the items...
.
Simplest linear hash chain based time-stamping is illustrated on following drawing:
The linking-based time-stamping authority (TSA) usually performs the following distinct functions:
Aggregation
- For increased scalability TSA might group time-stamping requests arriving within a short timeframe. These requests will be aggregated together without retaining their temporal order and then assigned the same time value. Aggregation creates cryptographicCryptographyCryptography is the practice and study of techniques for secure communication in the presence of third parties...
connection between all involved requests; authenticating aggregate value will be used as input for the linking operation.
Linking
- Linking creates verifiable and ordered cryptographic link between current and already issued time-stamp tokens.
Publishing
- TSA publishes periodically some links, so that all previously issued time-stamp tokens depend on the published link and that it is practically impossible to forge the published values. By publishing widely witnessed links the TSA creates unforgeable verification points for validating all previously issued time-stamps.
Security
Linking-based time-stamping is inherently more secure than the usual, public-key signature based time-stamping. All consequential time-stamps "seal" previously issued ones - hash chain (or other authenticated dictionary in use) could be built only in one way; modifying issued time-stamps is nearly as hard as finding a preimage for the used cryptographic hash functionCryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
. Continuity of operation is observable by users; periodic publications in widely-witnessed media provide extra transparency.
Tampering with absolute time values could be detected by users, whose time-stamps are relatively comparable by system design.
Absence of secret keys increases system trustworthiness. There are no keys to leak and hash algorithms are considered more future-proof than modular arithmetic based algorithms, e.g. RSA.
Linking-based time-stamping scales well - hashing is much faster than public key cryptography. There is no need for specific cryptographic hardware with its limitations.
The common technology for guaranteeing long-term attestation value of the issued time-stamps (and digitally signed data) is periodic over-time-stamping of the time-stamp token. Because of missing key-related risks and of the plausible safety margin of the reasonably chosen hash function this over-time-stamping period of hash-linked token could be an order of magnitude longer than of public-key signed token.
Foundations
Haber and Stornetta proposed in 1990 to link issued time-stamps together into linear hash-chain, using a collision-resistant hash function. The main rationale was to diminish TSA trust requirements.Tree-like schemes and operating in rounds were proposed by Benaloh and de Mare in 1991 and by Bayer, Haber and Stornetta in 1992.
Benaloh and de Mare constructed a one-way accumulator in 1994 and proposed its use in time-stamping. When used for aggregation, one-way accumulator requires only one constant-time computation for round membership verification.
Surety started the first commercial linking-based time-stamping service in January 1995. Linking scheme is described and its security is analyzed in the following article by Haber and Sornetta.
Buldas et al. continued with further optimization and formal analysis of binary tree and threaded tree based schemes.
Skip-list based time-stamping system was implemented in 2005; related algorithms are quite efficient.
Provable security
Security proof for hash-function based time-stamping schemes was presented by Buldas, Saarepera in 2004. There is an explicit upper bound for the number of time stamps issued during the aggregation period; it is suggested that it is probably impossible to prove the security without this explicit bound - the so-called black-box reductions will fail in this task. Considering that all known practically relevant and efficient security proofs are black-box, this negative result is quite strong.Next, in 2005 it was shown that bounded time-stamping schemes with a trusted audit party (who periodically reviews the list of all time-stamps issued during an aggregation period) can be made universally composable - they remain secure in arbitrary environments (compositions with other protocols and other instances of the time-stamping protocol itself).
Buldas, Laur showed in 2007 that bounded time-stamping schemes are secure in a very strong sense - they satisfy the so-called "knowledge-binding" condition. The security guarantee offered by Buldas, Saarepera in 2004 is improved by diminishing the security loss coefficient from
to .The hash functions used in the secure time-stamping schemes do not necessarily have to be collision-resistant or even one-way; secure time-stamping schemes are probably possible even in the presence of a universal collision-finding algorithm (i.e. universal and attacking program that is able to find collisions for any hash function). This suggests that it is possible to find even stronger proofs based on some other properties of the hash functions.
At the illustration above hash tree based time-stamping system works in rounds (
, , , ...), with one aggregation tree per round. Capacity of the system () is determined by the tree size (, where denotes binary tree depth). Current security proofs work on the assumption that there is a hard limit of the aggregation tree size, possibly enforced by the subtree length restriction.Standards
ISO 18014ISO 18014
ISO/IEC 18014 Information technology — Security techniques — Time-stamping services is an international standard that specifies time-stamping techniques...
part 3 covers 'Mechanisms producing linked tokens'.
American National Standard
American National Standards Institute
The American National Standards Institute is a private non-profit organization that oversees the development of voluntary consensus standards for products, services, processes, systems, and personnel in the United States. The organization also coordinates U.S. standards with international...
for Financial Services, "Trusted Timestamp Management and Security" (ANSI ASC X9.95 Standard
ANSI ASC X9.95 Standard
The ANSI X9.95 standard for trusted timestamps expands on the widely used by adding data-level security requirements that can ensure data integrity against a reliable time source that is provable to any third party...
) from June 2005 covers linking-based and hybrid time-stamping schemes.
There is no IETF
Internet Engineering Task Force
The Internet Engineering Task Force develops and promotes Internet standards, cooperating closely with the W3C and ISO/IEC standards bodies and dealing in particular with standards of the TCP/IP and Internet protocol suite...
RFC
Request for Comments
In computer network engineering, a Request for Comments is a memorandum published by the Internet Engineering Task Force describing methods, behaviors, research, or innovations applicable to the working of the Internet and Internet-connected systems.Through the Internet Society, engineers and...
or standard draft about linking based time-stamping. RFC 4998 (Evidence Record Syntax) encompasses hash tree and time-stamp as an integrity guarantee for long-term archiving.