Hash chain
Encyclopedia
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.
to a string.
For example,
gives a hash chain of length 4, often denoted
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, he supplies 
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 function
s, 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 is exhausted. Each time the hash value is different, and thus cannot be duplicated by an attacker.
Cryptographic 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...
to a piece of data. In computer security
Computer security
Computer security is a branch of computer technology known as information security as applied to computers and networks. The objective of computer security includes protection of information and property from theft, corruption, or natural disaster, while allowing the information and property to...
, a hash chain is a method to produce many one-time keys
One-time password
A one-time password is a password that is valid for only one login session or transaction. OTPs avoid a number of shortcomings that are associated with traditional passwords. The most important shortcoming that is addressed by OTPs is that, in contrast to static passwords, they are not vulnerable...
from a single key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
or password
Password
A password is a secret word or string of characters that is used for authentication, to prove identity or gain access to a resource . The password should be kept secret from those not allowed access....
. For non-repudiation
Non-repudiation
Non-repudiation refers to a state of affairs where the purported maker of a statement will not be able to successfully challenge the validity of the statement or contract. The term is often seen in a legal setting wherein the authenticity of a signature is being challenged...
a hash function can be applied successively to additional pieces of data in order to record the chronology of data's existence.
Definition
A hash chain is a successive application of a 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...
to a string.For example,
gives a hash chain of length 4, often denoted
Applications
LamportLeslie Lamport
Leslie Lamport is an American computer scientist. A graduate of the Bronx High School of Science, he received a B.S. in mathematics from the Massachusetts Institute of Technology in 1960, and M.A. and Ph.D. degrees in mathematics from Brandeis University, respectively in 1963 and 1972...
suggested the use of hash chains as a password protection scheme in an insecure environment. A server which needs to provide authentication
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...
may store a hash chain rather than a plain text
Plain text
In computing, plain text is the contents of an ordinary sequential file readable as textual material without much processing, usually opposed to formatted 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, he supplies 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 authenticationAuthentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...
since the server now expects
. Due to the one-way propertyOne-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
of cryptographically secure hash function
Cryptographic 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...
s, 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 is exhausted. Each time the hash value is different, and thus cannot be duplicated by an attacker.
See also
- Challenge-response authenticationChallenge-response authenticationIn computer security, challenge-response authentication is a family of protocols in which one party presents a question and another party must provide a valid answer to be authenticated....
- Hash listHash listIn computer science, a hash list is typically a list of hashes of the data blocks in a file or set of files. Lists of hashes are used for many different purposes, such as fast table lookup and distributed databases...
- In contrast to the recursive structure of hash chains, the elements of a hash list are independent of each other. - One-time passwordOne-time passwordA one-time password is a password that is valid for only one login session or transaction. OTPs avoid a number of shortcomings that are associated with traditional passwords. The most important shortcoming that is addressed by OTPs is that, in contrast to static passwords, they are not vulnerable...