Hubbry Logo
Hash chainHash chainMain
Open search
Hash chain
Community hub
Hash chain
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Hash chain
Hash chain
Hash chain
View on Wikipedia
from Wikipedia

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 used 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.

Definition

[edit]

A hash chain is a successive application of a cryptographic hash function to a string .

For example,

gives a hash chain of length 4, often denoted

Applications

[edit]
Main article: S/KEY

Leslie Lamport[1] suggested the use of hash chains as a password protection scheme in an insecure environment. A server which needs to provide authentication may store a hash chain rather than a plain text password and prevent theft of the password in transmission or theft from the server. For example, a server begins by storing which is provided by the user. When the user wishes to authenticate, they supply to the server. The server computes and verifies this matches the hash chain it has stored. It then stores for the next time the user wishes to authenticate.

An eavesdropper seeing communicated to the server will be unable to re-transmit the same hash chain to the server for authentication since the server now expects . Due to the one-way property of cryptographically secure hash functions, it is infeasible for the eavesdropper to reverse the hash function and obtain an earlier piece of the hash chain. In this example, the user could authenticate 1000 times before the hash chain were exhausted. Each time the hash value is different, and thus cannot be duplicated by an attacker.

Binary hash chains

[edit]
Main article: Merkle tree

Binary hash chains are commonly used in association with a hash tree. A binary hash chain takes two hash values as inputs, concatenates them and applies a hash function to the result, thereby producing a third hash value.

Hash tree and hash chain

The above diagram shows a hash tree consisting of eight leaf nodes and the hash chain for the third leaf node. In addition to the hash values themselves the order of concatenation (right or left 1,0) or "order bits" are necessary to complete the hash chain.

Winternitz chains

[edit]

Winternitz chains (also known as function chains[2]) are used in hash-based cryptography. The chain is parameterized by the Winternitz parameter w (number of bits in a "digit" d) and security parameter n (number of bits in the hash value, typically double the security strength,[3] 256 or 512). The chain consists of values that are results of repeated application of a one-way "chain" function F to a secret key sk: . The chain function is typically based on a standard cryptographic hash, but needs to be parameterized ("randomized"[4]), so it involves few invocations of the underlying hash.[5] In the Winternitz signature scheme a chain is used to encode one digit of the m-bit message, so the Winternitz signature uses approximately bits, its calculation takes about applications of the function F.[3] Note that some signature standards (like Extended Merkle signature scheme, XMSS) define w as the number of possible values in a digit, so in XMSS corresponds to in standards (like Leighton-Micali Signature, LMS) that define w in the same way as above - as a number of bits in the digit.[6]

Hash chain vs. blockchain

[edit]

A hash chain is similar to a blockchain, as they both utilize a cryptographic hash function for creating a link between two nodes. However, a blockchain (as used by Bitcoin and related systems) is generally intended to support distributed agreement around a public ledger (data), and incorporates a set of rules for encapsulation of data and associated data permissions.

See also

[edit]

References

[edit]

Sources

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Hash chain

View on Grokipedia
from Grokipedia
A hash chain is a cryptographic primitive consisting of a sequence of values where each element is generated by applying a one-way to the previous element, starting from an initial secret seed value, such that reversing the chain to recover prior values is computationally infeasible under standard cryptographic assumptions. This structure provides forward security and , as any alteration to an early element would invalidate all subsequent hashes, enabling efficient verification from the final value backward without revealing the seed. Introduced by in 1981 as a method for over insecure communication channels—where a user precomputes a chain of hashed passwords and reveals them sequentially to prove knowledge of the seed without transmitting it directly—hash chains have since become integral to various security protocols. In authentication systems, such as (OTP) schemes like , hash chains allow users to authenticate without reusing static passwords, mitigating replay attacks by ensuring each authentication value is unique and verifiable against the publicly known chain endpoint. They also underpin early digital signature schemes, such as the Winternitz one-time signature scheme, where multiple hash chains generate ephemeral keys for signing messages once, providing post-quantum resistance due to reliance on collision-resistant hash functions rather than factoring or discrete logarithms. These schemes have been standardized by NIST in 2024 as part of efforts, including LMS and XMSS. Beyond authentication, hash chains facilitate systems, such as those proposed by Rivest for electronic commerce, where payers release chain values incrementally to pay small amounts without per-transaction signatures, and time-release cryptography, enabling delayed disclosure of information. A prominent modern application is in technology, where hash chains link blocks of transactions: each block includes the hash of the prior block's header, forming an immutable ledger that timestamps data and prevents tampering, as demonstrated in Satoshi Nakamoto's . This chaining mechanism ensures consensus on transaction history across distributed nodes, with the longest valid chain representing the accepted state. In resource-constrained environments like RFID tags, hash chains enable privacy-preserving by updating pseudonyms with each interaction, limiting traceability while minimizing computational overhead. Despite their efficiency—requiring only hash computations, which are lightweight compared to public-key operations—hash chains are vulnerable to preimage attacks if the underlying is weak, underscoring the need for secure primitives like SHA-256. Overall, hash chains exemplify a simple yet versatile tool for achieving and chain-of-custody in cryptographic systems.

Fundamentals

Definition

A hash chain is a sequence of values generated by iteratively applying a to an initial value, where each subsequent value is the hash of the immediately preceding one. This structure forms a unidirectional , as computing forward from any point is straightforward, but reversing the process to find prior values is computationally infeasible due to the properties of the underlying . Cryptographic hash functions, which serve as the building blocks for hash chains, are mathematical algorithms that map input data of arbitrary length to a fixed-size output, typically a string of digits. These functions exhibit the , whereby even a minor change in the input—such as flipping a single bit—results in a dramatically different output, with approximately half the bits altered on average. Key security properties include preimage resistance (difficulty in finding an input that produces a given output), (infeasibility of finding two distinct inputs yielding the same output), and second-preimage resistance (hardness of producing a different input with the same output as a given input). These attributes ensure the chain's and resistance to tampering or . For example, given a seed value SS and a HH, the chain is constructed as h1=H(S)h_1 = H(S), h2=H(h1)h_2 = H(h_1), ..., hn=H(hn−1)h_n = H(h_{n-1}). This iterative process leverages the one-way nature of HH, making it easy to verify forward links (e.g., checking if H(hi)=hi+1H(h_i) = h_{i+1}) while preventing backward computation. The concept originated in cryptographic literature in the early 1980s, introduced by for secure authentication over insecure channels.

Construction

A hash chain is constructed by selecting a secure cryptographic one-way , such as SHA-256, which produces a 256-bit output and is designed to resist preimage and collision attacks. The process starts with choosing an initial value, typically a random or secret string of sufficient to prevent predictability by adversaries. This , denoted as h0h_0, serves as the starting point, and the chain is generated by iteratively applying the to produce subsequent values up to a predetermined length nn. For example, each hi=H(hi−1)h_i = H(h_{i-1}) for i=1i = 1 to nn, where HH is the chosen . The chain length nn is selected based on the anticipated number of uses or the desired lifetime of the chain; for example, values on the order of 2202^{20} (approximately 1 million) are used in some systems to support extended periods without reseeding. Typically, only the endpoint hash hnh_n is stored publicly or shared for verification purposes, while the full may be generated and stored privately if needed for sequential revelation. Weak hash functions must be avoided during construction; for instance, MD5 was deprecated after 2008 due to practical collision attacks that undermine its one-way property. To illustrate the algorithmic process, the following outlines the basic iterative construction:

function generate_hash_chain(seed, n, H): h = seed // h_0 = seed chain = [h] // Optional: store full chain if needed for i = 1 to n: h = H(h) // Apply [hash function](/page/Hash_function) chain.append(h) // Optional storage return chain // Or just return h_n for endpoint-only

function generate_hash_chain(seed, n, H): h = seed // h_0 = seed chain = [h] // Optional: store full chain if needed for i = 1 to n: h = H(h) // Apply [hash function](/page/Hash_function) chain.append(h) // Optional storage return chain // Or just return h_n for endpoint-only

This approach ensures the chain's one-way nature, as each link depends solely on the previous one. The computational cost of constructing a full of length nn is O(n)O(n) in both time and , requiring nn evaluations of the and storage for n+1n+1 values if the entire sequence is retained. Optimizations often involve computing and storing only the and endpoint, regenerating intermediate values on demand, though this trades storage for repeated computation in usage scenarios. To test for hash chaining in sequence generation, one verifies that each subsequent key derives from the previous one by applying the hash function. For instance, compute the hash of key_{n-1} and check if it matches key_n. In salted implementations, this may involve key_n = int(sha256(hex(key_{n-1}) + salt), 16) clipped to a specific range, ensuring the computed value aligns with the provided sequence. Alternatively, in counter-based variants, keys are generated by hashing a master seed concatenated with a counter n, such as H(master_seed || n), and verification confirms this derivation for the given n.

Variants

Binary Hash Chains

Binary hash chains represent a variant of hash chains designed to enable efficient access to arbitrary positions within a long chain without requiring the storage or computation of every intermediate value. This approach leverages a binary exponentiation-like technique adapted to iterative hashing, allowing the precomputation of key checkpoint values at positions that are powers of two. Specifically, starting from a seed value ss, the checkpoints are defined as h2k=H2k(s)h_{2^k} = H^{2^k}(s), where Hn(s)H^n(s) denotes the hash function HH applied iteratively nn times to ss. This structure facilitates jumping to distant points in the chain by combining segments between checkpoints, reducing the overall resource demands for both storage and traversal. The construction of a binary hash chain begins with the selection of a secure one-way HH and an initial seed ss. The core checkpoints are built through repeated application of the in a doubling manner: compute h1=H(s)h_1 = H(s), then h2=H(h1)=H2(s)h_2 = H(h_1) = H^2(s), followed by h4=H2(h2)=H4(s)h_4 = H^2(h_2) = H^4(s), and continuing iteratively to h2kh_{2^k} until the desired chain length n≈2kn \approx 2^k is covered. For an arbitrary position mm in the chain, where mm is expressed in binary as m=∑bi2im = \sum b_i 2^i with bi∈{0,1}b_i \in \{0,1\}, the value hmh_m can be obtained by sequentially hashing from the seed through the relevant checkpoint segments corresponding to the set bits in mm. This combination process requires O(log⁡n)O(\log n) hash operations per query, as opposed to O(n)O(n) for a full linear traversal. The algorithm, formalized in pebbling strategies, places "pebbles" (stored hash values) only at these power-of-two positions during setup, enabling on-demand computation of intermediates. A primary advantage of binary hash chains is the significant reduction in storage requirements from O(n)O(n) to O(log⁡n)O(\log n), achieved by maintaining solely the k+1k+1 checkpoint values for a chain of length up to 2k2^k. This compact representation is particularly beneficial in resource-constrained environments, such as embedded systems or long-term protocols, where storing an entire chain of millions of values would be impractical. Traversal algorithms, such as those employing high- and low-priority pebbling, further optimize computation, achieving amortized O(1)O(1) hash evaluations per consecutive preimage after initial setup, while keeping peak memory usage at O(log⁡n)O(\log n). For instance, in a chain of length 2302^{30}, only about 30 checkpoints need storage, compared to over a billion values in a naive approach. The security of binary hash chains inherits the properties of the underlying one-way , relying on its preimage resistance to prevent unauthorized computation of chain positions or forgery of values. In the model, inverting a checkpoint or finding a shortcut to a distant position equates to solving a problem in the hash domain, where the "exponent" corresponds to the iteration count. For a providing 80-bit security, an adversary requires approximately 2802^{80} operations to invert any checkpoint or derive an unauthorized preimage, ensuring robustness against brute-force attacks. This maintains the chain's unidirectionality, as forward computation remains feasible only sequentially for legitimate parties. Although the foundational use of iterative hashing for traces back to Lamport's 1979 of one-time digital , where one-way functions enable secure revelation of bit-specific values, the generalization to efficient binary-structured chains for broader traversal and storage optimization was advanced in subsequent work on pebbling algorithms.

Winternitz Chains

Winternitz chains extend the concept of basic hash chains to support the encoding of variable-length messages in one-time schemes by employing w parallel hash chains, where w = 2b represents the window size for b bits per message symbol. This , first proposed by Robert Winternitz and detailed in Ralph Merkle's 1979 work, allows multiple bits of information to be signed per chain, trading increased computational effort for reduced size compared to simpler binary methods. A dedicated chain is incorporated alongside the k message chains to mitigate malleability attacks, ensuring that alterations to the revealed values cannot produce a valid for a different message. In the construction, for a message m = m1 m2 ... mk where each mi ∈ {0, 1, ..., w-1}, a separate hash chain is generated for each position i. Each chain begins with a random secret value h0i and iterates the up to hwi, with the public verification key including hwi for i = 1 to k, plus the endpoint of the checksum chain. To sign, the signer reveals hw - mii from the i-th chain, allowing verification by applying the mi times to reach the public key value. The is computed as the sum of the mi values, which is then treated as an additional symbol to sign on a separate chain, starting from this sum and revealing the corresponding position to bind the message components securely. This setup prevents an adversary from easily modifying revealed values to forge a different message, as altering any mi would require inverting the on the checksum chain. The window size w serves as a key parameter, balancing efficiency: larger w shortens the overall chain length needed for a fixed message size by encoding more bits per chain, but it increases the number of hash computations required during signing and verification for each reveal. For instance, w=2 corresponds to the binary hash chain base case, signing one bit per chain, while w=16 allows four bits per chain at the cost of up to 15 hashes per position. Winternitz chains provide existential unforgeability under chosen-message attack (EU-CMA) security when used once, relying solely on the and second-preimage resistance of the underlying . This one-time security model, introduced in Winternitz's contribution via Merkle, ensures that an adversary cannot produce a valid for a new message after observing one , assuming the hash function is secure. However, the scheme's chain length scales linearly with the number of message bits (approximately ⌈n / b⌉ chains for an n-bit message), making it inefficient for long messages, and it is explicitly not suitable for reuse, as repeated signing on the same chains enables forgery through key recovery.

Applications

Authentication Systems

Hash chains find primary application in authentication systems for generating sequences of one-time passwords (OTPs), where successive positions in the chain are revealed during without transmitting the underlying secret. In this setup, the client and server share an initial commitment to the chain's endpoint, allowing verification through forward hashing while preserving the secrecy of unrevealed portions. A seminal protocol exemplifying this use is S/KEY, developed at Bellcore in the late 1980s. In S/KEY, the client selects a secret seed and passphrase, computes the chain by iteratively applying a hash function (initially MD4), and the server stores the hash of the final chain value after a fixed number of iterations, typically 1000 steps. During authentication, the server challenges the client with the current sequence number and seed; the client responds with the corresponding chain value (e.g., H^{1000 - n}(seed || passphrase)), which the server verifies by hashing it forward to match the stored next expected value, then updates its storage accordingly. This process ensures the secret never traverses the network, mitigating eavesdropping risks. Modern iterations build on this foundation, such as the (HOTP) algorithm defined in RFC 4226. HOTP employs an construction (originally with , now often upgraded to SHA-256 or SHA-512 for enhanced security) over a key and an incrementing event counter as the moving factor, effectively creating a chain of HMAC values. The client and server maintain synchronized counters; upon authentication, the client sends the truncated output, and the server validates it within a small look-ahead window to accommodate potential desynchronization from missed events or transmission delays. These systems provide key security benefits, including —where compromise of the seed or key after does not expose prior OTPs due to the one-way nature of hashing—and resistance to replay attacks, as each counter value or chain position yields a unique, non-reusable password. However, they require pre-sharing the chain endpoint or secret key during initial setup, and counter drift in HOTP can necessitate manual resynchronization or window adjustments, contributing to its partial obsolescence in favor of time-based alternatives like TOTP.

Digital Signatures

Hash chains are integral to certain one-time schemes that build on Leslie Lamport's foundational scheme, which enables for single-use using the of hash functions. In Lamport's scheme, the private key consists of random secret strings, and the public key is their images under a (typically a hash applied once). To sign a , the signer reveals preimages corresponding to the message bits, allowing verification by applying the one-way function to check against the public key. The Winternitz one-time signature (W-OTS) scheme improves on this by integrating to efficiently sign multi-bit message segments, reducing signature size compared to basic Lamport signatures. Each chain now supports signing a block of bb bits by applying the up to 2b−12^b - 1 times, with the public key as the fully hashed endpoint. The signer selects an intermediate point in the chain based on the message block value, revealing a value that, when hashed the appropriate number of remaining times, reaches the public key. Verification involves recomputing these hashes from the revealed values to confirm they match the public key components, providing authenticity for the signed bits. This integration, originally proposed as an to Lamport's design, allows compact representation of larger messages while maintaining reliance on hash chain irreversibility. In the signing protocol, the message is first hashed and divided into blocks of bb bits each, denoted as mim_i for the ii-th block. The signer reveals hf(mi)h_{f(m_i)}, the hash value obtained by applying the f(mi)f(m_i) times starting from the private for that , where f(mi)f(m_i) is typically 2b−1−mi2^b - 1 - m_i to ensure forward progression toward the public key. A is computed over all mim_i values and signed similarly using additional s to prevent tampering that could exploit the non-monotonic revelation. The verifier hashes each revealed value the requisite number of times (to reach 2b−1−f(mi)2^b - 1 - f(m_i) iterations) and checks against the public key, along with verifying the , confirming the message's integrity and origin. These schemes achieve a level of 2t2^t against for a tt-bit output, assuming the underlying resists preimage attacks, as an adversary must invert the hash to forge a valid without the private seed. However, they are strictly one-time use; key reuse enables attacks, as demonstrated in early analyses where signing two messages reveals sufficient chain positions to interpolate and forge signatures for other messages, potentially reducing exponentially with each reuse. To enable multiple signatures without full key regeneration, hash chains are extended by combining them with hash trees in stateful schemes like the eXtended Merkle Signature Scheme (XMSS), which organizes one-time key pairs into a for efficient authentication of used positions under a single long-term public key. XMSS, standardized in RFC 8391 (2018) and recommended by NIST in SP 800-208 (2020) as part of post-quantum cryptography efforts, provides forward security while tracking state to prevent reuse. Despite their robustness, these hash chain-based signatures suffer from large sizes scaling as O(ℓ⋅t)O(\ell \cdot t), where ℓ\ell is the length in bits and tt is the hash size, making them unsuitable for frequent or high-volume signing applications.

Comparisons

Hash Chain vs.

A hash chain consists of a linear, precomputed sequence of cryptographic hashes, where each hash is derived from the previous one, enabling efficient private verification of the chain's without requiring distributed coordination. In contrast, a is a dynamic, composed of blocks linked by hashes, maintained through a consensus mechanism among networked participants to ensure agreement on the state of the . Structurally, a hash chain forms a simple sequential list of hashes, typically without embedded data beyond the linking mechanism, whereas a organizes data into discrete blocks, each containing a hash of the previous block combined with transaction data and metadata, such as in where the block hash is computed via double SHA-256 hashing of the block header. This block-based structure allows blockchains to bundle multiple transactions per link, supporting scalable in distributed environments. Within blockchains, hash chains serve as a foundational element in proof-of-work mechanisms, where miners generate nonce values to produce valid hashes that extend the chain, as seen in Bitcoin's process that requires finding a nonce yielding a hash below a target difficulty. However, blockchains often extend this with additional structures like Merkle trees to aggregate transaction proofs efficiently within blocks. Hash chains offer advantages in simplicity and lower computational overhead for non-distributed applications, as they avoid the resource-intensive network consensus required by blockchains. Historically, concepts, as introduced by in 2008, evolved from earlier hash chain-based timestamping protocols proposed by Haber and Stornetta in 1991, which used linked hashes to certify document timestamps immutably. Hash chains are suitable for lightweight authentication scenarios, such as systems, while are preferred for tamper-proof public records requiring decentralized trust, like transactions.

Relation to Hash Trees

Hash trees, commonly referred to as Merkle trees, are a consisting of a where each leaf node is labeled with the cryptographic hash of a block, and each non-leaf node is labeled with the hash of the concatenation of its two child nodes' labels. This construction ensures that any change to the underlying alters the root hash, providing a compact representation for verifying . The concept was introduced by in his 1979 paper "A Certified ," where it was proposed as part of a scheme relying solely on collision-resistant hash functions. A hash chain represents a degenerate case of a hash tree, reducing the branched structure to a linear path akin to a unary tree with a of one, where each node hashes only a single predecessor. In contrast, hash trees generalize this to enable efficient verification of multiple elements in parallel, allowing the root hash to commit to an entire set of values without revealing them individually. This extension addresses limitations in scalability for hash chains, which are inherently sequential. The primary construction difference lies in verification efficiency: authenticating a specific element in a hash chain requires recomputing up to O(n) hashes along the entire path from the element to the end, whereas a hash supports O(log n) verification using a Merkle proof consisting of hashes along the path to the . This logarithmic scaling makes hash trees suitable for large datasets, as the proof size remains constant regardless of the total number of elements. In applications unique to trees, such as Bitcoin's block structure, the Merkle in each block header enables compact inclusion proofs for transactions, allowing light clients to verify membership without downloading the full block. Security in both structures relies on the and preimage resistance of the underlying , but hash trees introduce additional safeguards through path consistency checks in Merkle proofs, making it computationally infeasible to forge a valid proof for an incorrect path or inconsistent data without breaking the . Over time, the linear hash chain has been integrated into more complex tree-based designs; for instance, the SPHINCS+ signature scheme, selected as a NIST finalist in 2022 and standardized as FIPS 205 (SLH-DSA) in August 2024, employs hypertrees—a multi-level generalization of hash trees—alongside hash chains for few-time signatures, combining linear and branched hashing for enhanced security against quantum attacks.

References

  1. http://merlot.usc.edu/cs530-s05/papers/Lamport81a.pdf
  2. https://arxiv.org/pdf/1008.2452
  3. https://csrc.nist.gov/pubs/fips/205/final
  4. https://csrc.nist.gov/projects/post-quantum-cryptography
  5. https://people.eecs.berkeley.edu/~sastry/sastry-pubs/Postdocs/HuYiChun/YihChunHU.sub-fc05.pdf
  6. https://bitcoin.org/bitcoin.pdf
  7. https://crypto.stackexchange.com/questions/76168/whats-the-difference-between-a-hash-chain-transaction-chain-and-a-blockchain
  8. https://lamport.azurewebsites.net/pubs/password.pdf
  9. https://eprint.iacr.org/2004/035.pdf
  10. https://www.geeksforgeeks.org/computer-networks/avalanche-effect-in-cryptography/
  11. https://dl.acm.org/doi/10.1145/358790.358797
  12. https://doi.org/10.6028/NIST.FIPS.180-4
  13. https://ntt-research.com/wp-content/uploads/2022/07/Construction-and-Traversal-of-Hash-Chain-with-Public-Links.pdf
  14. https://acmccs.github.io/papers/p983-koganA.pdf
  15. https://www.kb.cert.org/vuls/id/836068
  16. https://brennan.io/2016/06/19/hashchains-in-c/
  17. https://datatracker.ietf.org/doc/html/rfc4226
  18. https://fc16.ifca.ai/preproceedings/18_Schoenmakers.pdf
  19. https://berry.win.tue.nl/papers/eobp.pdf
  20. https://lamport.azurewebsites.net/pubs/dig-sig.pdf
  21. https://eprint.iacr.org/2011/191.pdf
  22. https://datatracker.ietf.org/doc/html/rfc8554
  23. https://datatracker.ietf.org/doc/html/rfc1760
  24. https://datatracker.ietf.org/doc/html/rfc6238
  25. http://www.ralphmerkle.com/papers/Certified1979.pdf
  26. https://eprint.iacr.org/2016/1042.pdf
  27. https://datatracker.ietf.org/doc/html/rfc8391
  28. https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-208.pdf
  29. https://blog.cryptographyengineering.com/2018/04/07/hash-based-signatures-an-illustrated-primer/
  30. https://arxiv.org/pdf/1412.4316
  31. https://link.springer.com/article/10.1007/BF00196791
  32. https://developer.nvidia.com/blog/improve-data-integrity-and-security-with-accelerated-hash-functions-and-merkle-trees-in-cupqc-0-4/
  33. https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards
Add your contribution
Related Hubs
User Avatar
No comments yet.