Alice wants to authenticate in Bob's host using a password. Bob holds the one-way hash function result of Alice's password.
Bob no longer stores a table of everybody's valid password, thus the thread of someone breaking into the host ans stealing the passwords list is mitigated.
Somehow Mallory has stealed the hashed passwords list from the Bob's host.
Mallory can compile a list of N (with N big) very common passwords and apply the one-way function to the list. Mallory can now compare the results to each of the hashed passwords list.
If a match is found then Mallory has found the password to be used for the respective user.
Salt is a random string that is concatenated with the password vefore being operated on by the one-way function. A different salt string is used for each different password. Both the salt and the result of the one-way function are stored in the database on the Bob's host.
Salt mitigates the dictionary attack threat. Now Mallory has to do a trial of each password in his dictionary every time he tries to break another person's password, rather that just doin one massive precomputation for all possible passwords (and possibly have it ready for other hosts).
If the password is sent in cleartext then Eve, can intercept it. Thus is recomended to enforce the protocol with a cryptographic protocol.
If Eve has access to the authentication host, then it can read it from a memory dump, before the host hash it for further checks.
To set up the system Alice enters a random number, R. The computer computes f(R), f(f(R)), f(f(f(R))), and so on, about a hundred times. Call these numbers x1,...,x100. The computer prints the list of numbers and Alice puts it away. The computer stores x101 in a login database next to Alice's name.
To log in, Alice enters the number x100. The computer computes f(x100) and if it match x101 then alice is logged in and the value x100 is substituted to x101 in the database. The next time that Alice wants to log in she has to enter x99. And so on.
When Alice runs out of numbers the system should be reinitialized.
With the expiration of the basic patents on public-key cryptography and the widespread use of SSH and other crypto protocols that can secure an entire session, not just the password, S/KEY is falling into disuse.
The Bob's host holds a list of the users public keys.
Neither the Bob's host nor the communication channel needs to be secure.
Alice never sends her private key over the transmission network. Eve listening on the interaction can't get any information that would enable her to imprersonate Alice.
A variant is where Bob sends to Alice an encrypted random string using her public key. Alice must send to Bob the decrypted content to prove that she is the owner of the private key.
Anyway it is not secure to encrypt/decrypt arbitrary strings.
A more secure protocol takes the following form.
With this protocol Alice never encrypts/decrypts strings choosen by Bob and can prove that she have the correct private key.
Alice and Bob are two users that want to authenticate each other. Each of them has a password that the other knows: Alice has PA and Bob has PB.
The following protocol is vulnerable to MitM attack:
A MitM attack here is trivial for Mallory. She can subvert the public keys exchange in step 1 by giving to the peers her public key and easily get PA and PB in the step that follows.
The interlock protocol can make the MitM attack more difficult.
Mallory can't decrypt the message in step 2. And to let the protocol continue he must send "something" to Alice to get the other half of the key. But the protocol is not even started for Bob, so Alice is not authenticated, nor is Bob.
Anyway now Mallory has PA and can easily independently start the protocol with Bob to get in a similar manner the Bob's password PB.
When Alice will restart the protocol then Mallory, knowing PA and PB, can immediatelly forward the messages to the other party and reaching the mutual authentication point.
The protocols use a MAC and thus is assumed that Alice and Bob share a secret key, K. The MAC function is H(K,params), with K the key and params are additional parameters.
SKID2 allows Bob to provide his identity to Alice
SKID3 additionally allows Alice to prove his identity to Bob.