[Cryptography] Feedback welcome on autentication/password replacement idea

[Jerry Leichter]

> Hello, I want to share my idea with you. If some places are not clear enough, you can try to guess or just ask me.
> 
> Main idea:
> Boris hashes some secret value many many times recursively (SHA(X), SHA(SHA(X)), ...), yielding chain of hashes.
> Boris gives the last hash in chain to Anne. When Boris want to prove that he came back and is genuine, he transmits previous hash in the chain. Anne hashes it and looks up if she saw that hash before - if she did, it's really Boris....
It's a fine idea, but you've been anticipated by many years:  Leslie Lamport proposed this as a way to have one-time passwords back in the 1980's, and implemented as a system called S/KEY - see https://en.wikipedia.org/wiki/S/KEY.  The idea was exactly as you suggest:  A user chose a password P, computed Hash^K(P), and gave that to the computer.  When he logged in, he presented Hash^{K-1}(P).  The computer hashed it, noted that it equaled the value it had stored, and let him in.  It also replaced its stored value with the one presented.  The next time, the password would be Hash^{K-2}(P).

To make the whole thing usable, you have to add techniques for resynchronizing if, for example, the connection drops after the user has sent his key but before the computer responds.  What should he present as his password the next time around?

                                                        -- Jerry