
Title:
0249 Hash Chain Solution

Description:

[Evans] The answer is Alice needs to send the value of hashing s 98 times.

The hash chain is going backwards.

We can only verify hashes in 1 direction.

The hash is hard to compute in 1 direction.

That's the valuable property the hash function gives us.

And so we have to go backwards if we want to use it for authentication.

Here we're using it to authenticate Alice.

If someone just knows x, if someone intercepts p, knows the previous password value,

they could compute any of these other values.

Those are easy to compute once you have p.

This was p, this one is just computing the hash of p,

and this one is computing the hash of the hash of p.

The only one that would be hard to compute is this one.

The server can check that that's correct using the same process.

At this point, the value of x is hash 99 of s.

So when the value of p that's sent is hash to the 98th power of s,

doing hash 98 times, then this equation will be true only if the value sent was correct.

So what I've described is what's known as the S/Key password system.

The way S/Key would work, the server would generate the hash chain.

Let's say there are 100 entries.

Alice would print these out in a list,

and they would be turned into strings that are easier to type than pure bit sequences.

The server would store the last entry in that hash chain and nothing else.

And so what's stored in the server could not be used to log in.

The list that Alice has could be used, and I should correct this

that if Alice starts with H 100 as the first thing in her list,

what the server should actually store would be H 101.

This has a pretty big downsidethat it requires Alice to carry around with her

a list of passwords, and instead of remembering something

that becomes easier and easier to type, she'd have to look at that list,

type the password correctly, cross that one off, and use the next one next time.

And at some point she's going to run out.

She's going to need to get on a secure connection again to generate a new hash chain

to be able to keep doing this.