en>Kwamikagami: /* Forms and variants */Latin script vs Latin alphabet using AWB

2014-01-08T19:15:40Z

Forms and variants: Latin script vs Latin alphabet using AWB

New page

'''Linking-based time-stamping''' is a type of [[trusted timestamping]] 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 structure]]. 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) [[Public-key cryptography|private keys]] in use, avoiding [[Public key infrastructure|PKI]]-related risks.

Suitable candidates for authenticated data structure are:
* Linear [[hash chain]],
* [[Merkle tree]] (binary hash tree),
* [[Skip list]].

Simplest linear hash chain based time-stamping is illustrated on following drawing: [[File:Hashlink timestamping.svg|thumb|none|600px|Linear hash-chain based linking scheme]]

The linking-based [[Timestamping authority|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 [[Cryptography|cryptographic]] 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.

[[File:Root of Merkle tree as published in Widely Witnessed Media.png|thumb|321px|right|Example newspaper publication of hash-linked time-stamping service]]

;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 function]]. 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<ref>{{Cite doi|10.1007/978-3-540-88702-7_3}}</ref> than modular arithmetic based algorithms, e.g. [[RSA (algorithm)|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<ref>See ISO/IEC 18014-1:2002 Chapter 4.2</ref> for guaranteeing long-term attestation value of the issued time-stamps (and digitally signed data<ref>For example see [[XAdES|XAdES-A]].</ref>) 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.

==Research==

===Foundations===

Haber and Stornetta proposed<ref>{{Cite doi|10.1007/BF00196791 }}</ref> in 1990 to link issued time-stamps together into linear hash-chain, using a collision-resistant hash function. The main rationale was to diminish [[Timestamping authority|TSA]] trust requirements.

Tree-like schemes and operating in rounds were proposed by Benaloh and de Mare in 1991<ref>{{Cite journal
| last=Benaloh
| first=Josh
| last2=de Mare
| first2=Michael
| title=Efficient Broadcast Time-Stamping
| volume=Technical Report 1
| publisher=Clarkson University Department of Mathematics and Computer Science
| year=1991
| url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.9199
}}</ref> and by Bayer, Haber and Stornetta in 1992.<ref>{{Cite journal
| last=Bayer
| first=Dave
| last2=Stuart A.
| first2=Haber
| last3=Wakefield Scott
| first3=Stornetta
| title=Improving the Efficiency And Reliability of Digital Time-Stamping
| pages=329–334
| journal=Sequences II: Methods in Communication, Security and Computer Science
| publisher=Springer-Verlag
| year=1992
| url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.5923
}}</ref>

Benaloh and de Mare constructed a one-way accumulator<ref>{{Cite doi|10.1007/3-540-48285-7_24}}</ref> 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<ref>http://www.surety.com/</ref> 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<ref>{{Cite doi|10.1145/266420.266430}}</ref> by Haber and Sornetta.

[[Ahto Buldas|Buldas]] et al. continued with further optimization<ref>{{Cite doi|10.1007/BFb0055749}}</ref> and formal analysis of binary tree and threaded tree<ref>{{Cite journal
| last=Buldas
| first=Ahto
| last2=Lipmaa
| first2=Helger
| last3=Schoenmakers
| first3=Berry
| title=Optimally Efficient Accountable Time-Stamping
| pages=293–305
| journal=LNCS
| volume=1751
| year=2000
| url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9332
| doi=10.1007/b75033}}</ref> based schemes.

Skip-list based time-stamping system was implemented in 2005;<ref>http://chronos.univ-pau.fr/</ref> related algorithms are quite efficient.<ref>{{Cite doi|10.1007/11751595_43}}</ref>

===Provable security===

Security proof for hash-function based time-stamping schemes was presented by Buldas, Saarepera<ref>{{Cite journal
| last = Buldas
| first = Ahto
| last2 = Saarepera
| first2 = Märt
| title = On Provably Secure Time-Stamping Schemes
| pages = 500–514
| journal = LNCS
| volume = 3329
| year = 2004
| url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.65.8638
| doi = 10.1007/b104116}}</ref> in 2004. There is an explicit upper bound <math>N</math> 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<ref>{{Cite doi|10.1007/11556992_26}}</ref> 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<ref>{{Cite doi|10.1007/978-3-540-71677-8_11}}</ref> 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 <math>N</math> to <math>\sqrt{N}</math>.

The hash functions used in the secure time-stamping schemes do not necessarily have to be collision-resistant<ref>{{Cite doi|10.1007/978-3-540-75670-5_9}}</ref> or even one-way;<ref>{{Cite doi|10.1007/11767480_4}}</ref> 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.

[[File:Hashtree timestamping.svg|thumb|none|600px|Hash tree based linking scheme]]
At the illustration above hash tree based time-stamping system works in rounds (<math>t</math>, <math>t+1</math>, <math>t+2</math>, ...), with one aggregation tree per round. Capacity of the system (<math>N</math>) is determined by the tree size (<math>N=2^l</math>, where <math>l</math> 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 18014]] part 3 covers 'Mechanisms producing linked tokens'.

[[American National Standards Institute|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 [[Internet Engineering Task Force|IETF]] [[Request for Comments|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.

[http://www.openksi.org/ OpenKSI working group ] is working on a set of specifications for Keyless Signature Infrastructure, an infrastructure used for generating keyless signatures, which are a combination of linking-based timestamps and [[Server-based_signatures| server-based signatures]] .<ref>http://www.openksi.org/refer/</ref>

==See also==
* [http://www.guardtime.com/educational-series-on-hashes/ "Series of mini-lectures about cryptographic hash functions"]; includes application in time-stamping and provable security; by A. Buldas, 2011.

Some commercial implementations:
* http://www.guardtime.com/
* http://www.alstru.com/

==References==
<references />

[[Category:Computer security]]
[[Category:Time]]

I - Revision history

en>Kwamikagami: /* Forms and variants */Latin script vs Latin alphabet using AWB