 | This article provides insufficient context for those unfamiliar with the subject.(September 2017) (Learn how and when to remove this template message) |
Linked timestamping is a type of trusted timestamping where issued time-stamps are related to each other.
Linked timestamping creates time-stamp tokens which are dependent on each other, entangled in some authenticated data structure. Later modification of the issued time-stamps would invalidate this structure. The 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.
The top of the authenticated data structure is generally published in some hard-to-modify and widely witnessed media, like printed newspaper or public blockchain. There are no (long-term) private keys in use, avoiding PKI-related risks.
Suitable candidates for the authenticated data structure include:
The simplest linear hash chain-based time-stamping scheme is illustrated in the following diagram:
The linking-based time-stamping authority (TSA) usually performs the following distinct functions:
Linked timestamping 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 [1] than modular arithmetic based algorithms, e.g. RSA.
Linked timestamping scales well - hashing is much faster than public key cryptography. There is no need for specific cryptographic hardware with its limitations.
The common technology [2] for guaranteeing long-term attestation value of the issued time-stamps (and digitally signed data [3] ) 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.
Haber and Stornetta proposed [4] 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 [5] and by Bayer, Haber and Stornetta in 1992. [6]
Benaloh and de Mare constructed a one-way accumulator [7] 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 [8] started the first commercial linked timestamping service in January 1995. Linking scheme is described and its security is analyzed in the following article [9] by Haber and Sornetta.
Buldas et al. continued with further optimization [10] and formal analysis of binary tree and threaded tree [11] based schemes.
Skip-list based time-stamping system was implemented in 2005; related algorithms are quite efficient. [12]
Security proof for hash-function based time-stamping schemes was presented by Buldas, Saarepera [13] 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 [14] 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 [15] 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 [16] or even one-way; [17] 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.
ISO 18014 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.
A cryptographic hash function (CHF) is a mathematical algorithm that maps data of arbitrary size to a bit array of a fixed size. It is a one-way function, that is, a function which is practically infeasible to invert. Ideally, the only way to find a message that produces a given hash is to attempt a brute-force search of possible inputs to see if they produce a match, or use a rainbow table of matched hashes. Cryptographic hash functions are a basic tool of modern cryptography.
In cryptography, the eXtended Sparse Linearization (XSL) attack is a method of cryptanalysis for block ciphers. The attack was first published in 2002 by researchers Nicolas Courtois and Josef Pieprzyk. It has caused some controversy as it was claimed to have the potential to break the Advanced Encryption Standard (AES) cipher, also known as Rijndael, faster than an exhaustive search. Since AES is already widely used in commerce and government for the transmission of secret information, finding a technique that can shorten the amount of time it takes to retrieve the secret message without having the key could have wide implications.
Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.
In cryptography, a private information retrieval (PIR) protocol is a protocol that allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved. PIR is a weaker version of 1-out-of-n oblivious transfer, where it is also required that the user should not get information about other database items.
Proof of work (PoW) is a form of cryptographic zero-knowledge proof in which one party proves to others that a certain amount of computational effort has been expended for some purpose. Verifiers can subsequently confirm this expenditure with minimal effort on their part. The concept was invented by Cynthia Dwork and Moni Naor in 1993 as a way to deter denial-of-service attacks and other service abuses such as spam on a network by requiring some work from a service requester, usually meaning processing time by a computer. The term "proof of work" was first coined and formalized in a 1999 paper by Markus Jakobsson and Ari Juels. Proof of work was later popularized by Bitcoin as a foundation for consensus in permissionless blockchains and cryptocurrencies, in which miners compete to append blocks and mint new currency, each miner experiencing a success probability proportional to their computational effort provably expended. PoW and PoS are the two best known consensus mechanisms. In the context of cryptocurrencies they are the most common mechanisms.
A rainbow table is a precomputed table for caching the output of cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering a key derivation function up to a certain length consisting of a limited set of characters. It is a practical example of a space–time tradeoff, using less computer processing time and more storage than a brute-force attack which calculates a hash on every attempt, but more processing time and less storage than a simple key derivation function with one entry per hash. Use of a key derivation that employs a salt makes this attack infeasible.
In cryptography and computer science, a hash tree or Merkle tree is a tree in which every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes. Hash trees allow efficient and secure verification of the contents of large data structures. Hash trees are a generalization of hash lists and hash chains.
FORK-256 is a hash algorithm designed in response to security issues discovered in the earlier SHA-1 and MD5 algorithms. After substantial cryptanalysis, the algorithm is considered broken.
Distributed key generation (DKG) is a cryptographic process in which multiple parties contribute to the calculation of a shared public and private key set. Unlike most public key encryption models, distributed key generation does not rely on Trusted Third Parties. Instead, the participation of a threshold of honest parties determines whether a key pair can be computed successfully. Distributed key generation prevents single parties from having access to a private key. The involvement of many parties requires Distributed key generation to ensure secrecy in the presence of malicious contributions to the key calculation.
In cryptography, a nonce is an arbitrary number that can be used just once in a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused in replay attacks. They can also be useful as initialisation vectors and in cryptographic hash functions.
A 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. For non-repudiation a hash function can be applied successively to additional pieces of data in order to record the chronology of data's existence.
The ANSI X9.95 standard for trusted timestamps expands on the widely used RFC 3161 - Internet X.509 Public Key Infrastructure Time-Stamp Protocol by adding data-level security requirements that can ensure data integrity against a reliable time source that is provable to any third party. Applicable to both unsigned and digitally signed data, this newer standard has been used by financial institutions and regulatory bodies to create trustworthy timestamps that cannot be altered without detection and to sustain an evidentiary trail of authenticity. Timestamps based on the X9.95 standard can be used to provide:
Trusted timestamping is the process of securely keeping track of the creation and modification time of a document. Security here 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 compromised.
Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems, which could, theoretically, be easily attacked by a quantum computer, some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.
In cryptography, the Fiat–Shamir heuristic is a technique for taking an interactive proof of knowledge and creating a digital signature based on it. This way, some fact can be publicly proven without revealing underlying information. The technique is due to Amos Fiat and Adi Shamir (1986). For the method to work, the original interactive proof must have the property of being public-coin, i.e. verifier's random coins are made public throughout the proof protocol.
Post-quantum cryptography refers to cryptographic algorithms that are thought to be secure against an attack by a quantum computer. As of 2020, this is not true for the most popular public-key algorithms, which can be efficiently broken by a sufficiently strong quantum computer. The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems can be easily solved on a sufficiently powerful quantum computer running Shor's algorithm. Even though current, publicly known, experimental quantum computers lack processing power to break any real cryptographic algorithm, many cryptographers are designing new algorithms to prepare for a time when quantum computing becomes a threat. This work has gained greater attention from academics and industry through the PQCrypto conference series since 2006 and more recently by several workshops on Quantum Safe Cryptography hosted by the European Telecommunications Standards Institute (ETSI) and the Institute for Quantum Computing.
A hash calendar is a data structure that is used to measure the passage of time by adding hash values to an append-only database with one hash value per elapsed second. It can be thought of special kind of Merkle or hash tree, with the property that at any given moment, the tree contains a leaf node for each second since 1970‑01‑01 00:00:00 UTC.
In cryptography, server-based signatures are digital signatures in which a publicly available server participates in the signature creation process. This is in contrast to conventional digital signatures that are based on public-key cryptography and public-key infrastructure. With that, they assume that signers use their personal trusted computing bases for generating signatures without any communication with servers.
In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed in "bits", where n-bit security means that the attacker would have to perform 2n operations to break it, but other methods have been proposed that more closely model the costs for an attacker. This allows for convenient comparison between algorithms and is useful when combining multiple primitives in a hybrid cryptosystem, so there is no clear weakest link. For example, AES-128 is designed to offer a 128-bit security level, which is considered roughly equivalent to 3072-bit RSA.
Hash-based cryptography is the generic term for constructions of cryptographic primitives based on the security of hash functions. It is of interest as a type of post-quantum cryptography.
|journal= (help)