Lecture
Hash chain — the result of successively applying a cryptographic hash function to a string. In computer security, a hash chain is used to generate a large number of one-time passwords from a single key or password. Hash chains are also used to implement non-repudiation[en] by applying the function to data in order to record the history of its existence.
to the string 
.For example,
gives a hash chain of length 4, which is often denoted as 
Lamport proposed using hash chains as a password protection scheme in an insecure environment. A server that needs to provide authentication can store a hash chain instead of a plaintext password, thereby preventing the password from being stolen during transmission to the server or directly from the server. For example, the server starts out storing the record 
, which is supplied by the user. When the user wants to authenticate, they send the server the string 
. The server computes the string 
and checks that it matches the record stored on the server. After that, the server stores the record for subsequent authentication.
An attacker who intercepts will not be able to reproduce and send the server the beginning of the chain when contacting it, because the server now expects 
. Thanks to the one-way property of cryptographic hash functions, the attacker cannot invert the hash function to obtain the beginning of the chain. In this example, the user can authenticate up to 1000 times before the chain is exhausted. Each time, the value of the transmitted hash is different, so intercepting a single hash does not allow the attacker to authenticate again.
Binary hash chains are typically used together with hash trees. A binary hash chain takes a pair of hash values as input, concatenates them, and applies the hash function to the resulting string, thereby producing a third hash.
The diagram shows a hash tree made up of 8 leaf nodes and the hash chain for the third leaf. In order to reconstruct the hash chain, in addition to the hash values themselves one needs to know the order of concatenation (right or left, 1 or 0).
Comments