Let's review one popular application of hash chains.

Again, with hash functions,

it is easy to compute the hash from left to right while

it is difficult to reverse it from right to left.

One popular application is called S/key,

which provides one-time passwords that can be used for authentication.

These passwords are one-time because each of them becomes obsolete after its use.

Let's first review the one-time password generation.

The server, which will later check the password for the authentication,

serves the role of the verifier.

The server generates x and H of x, H squared of x,

H to the third power of x and so on until H raised to power of n plus one of x.

Since the server chooses the x,

it is easy to compute and generate such values.

Upon computing the hash chain until

the value of H raised to the power of n plus one of x,

the server discards the secret x so that nobody can access it,

and the server shares the rest of the values with the user.

The user who wants to become authenticated,

serves as the approver when communicating with the server.

The user stores the values H of x,

H squared of x and so on until H to the nth power of x.

The server, on the other hand,

only stores H raised to the power of n plus one of x,

which value it uses for the password verification.

From the user side,

the passwords are designed to be used in the reverse order.

In other words, while the server generated

the passwords from left to right of the hash chain,

the user will use them in the reverse order from right to left.

So let's describe how the user server pair can use the passwords for authentication.

Whenever it wants to log in,

the user presents the one-time password to the server.

The first password that it will use will be H to the nth power of x.

The server, acting as the verifier,

receives the user's password and computes the H function to see whether

the output matches the stored value of H raised to the power of n plus one of x.

If they match, then the user's password is correct,

and the user gets authenticated.

The server also updates the stored value to H to

the nth power so that

the current password H to the nth power becomes obsolete and invalid.

The user would now need to use H raised to

the power of n minus one for the next authentication.

After time passes and when the user wants to log in again,

it uses H raised to the power of n minus one of x.

And similarly to before,

the server takes the user's password and computes

the hash to see if it matches with H to the nth power.

And when the matching is successful and the password is used,

the server update its reference to

the current password, H raised to the power of n minus one.

Because of the server update,

which progresses from right to left in the hash chain as time progresses,

an attacker who compromised the password and wants to use it in

the future application cannot do so because the password is obsolete now.

Also, the attacker may compute

the hash functions itself and compromise the right of the chain,

but it cannot compromise the left up the chain due to one-way property of hash functions.

In other words, attackers' hash computations will provide the history of

the one-time passports that have been used in

the past but not those passwords that will be used in the future.

Such use of hash chain provides an efficient way to generate

one-time passwords as hash computations are computationally easy.

However, the number of passwords that it generates is

limited to n. And after the use of n passwords,

the server and the user needs to go through

secure communications and set up the passwords again.

S/Key: One-Time Password

Cryptographic Hash and Integrity Protection

与讲师见面