S/Key was first conceived by Leslie Lamport, and was implemented by Neil M. Haller, Phillip R. Karn, and John S. Walden at Bellcore. S/Key and other one time password systems (e.g. SecurID) are designed to prevent against replay attacks -- that is, someone sniffing your network connection can record your password, and replay it later to gain access to your account (or whatever other resource you were using). Their solution is to make each password valid only once.
To do this, S/Key employs what is known as a cryptographically secure hash function. A hash function is an algorithm designed so that any particular input will produce a smaller output based on that input. A secure hash function has the added restraints that:
functions typically used in S/Key
S/Key uses three other items along with the secure hash to generate a one time password:
To set up S/Key authentication for one's account, you need to run either keyinit (for S/Key) or opiepasswd (for OPIE). This will generate a seed for you, as well as a sequence number, and prompt for your desired passphrase. It then combines your passphrase and seed, and runs it through the secure hash function. It takes the output of the hash function and runs it through the hash function again. And again, and again until the number of iterations has reached your sequence number. At which point it saves this in its internal database.
When you attempt to login and access your account, you will be issued a challenge consisting of the secure hash function used, the seed and your current sequence number, minus one. You should then compute a response, using the same procedure as described above. Don't worry -- plenty of software exists to do this for you, on every platform from huge mainframes to graphing calculators. Then, send this response to the server, which will check its validity by running it through the hash function one more time. It then compares the value in its internal database with this new value computed from your response. If they match, access is granted, and the server subtracts one from your sequence number and stores your original response in its database. If they do not match, access is denied.
The value of this should be apparent -- thanks to the properties of secure hash functions like MD5, it is nearly impossible to compute future passwords knowing one or even several past passwords. Another cool trick is that you can change your passphrase without even sending it to the server -- simply compute a response on the client end, with a given seed and sequence number, and pass these three pieces of data to keyinit or opiepasswd on the server end, both of which will accept the response and store it in their database.
Direct quotations were cited with footnotes. Paraphrases were taken from all of the sources below.
1. The opie(4) manpage, available online at http://www.gsp.com/cgi-bin/man.cgi?section=4&topic=opie
2. Walsh, Chris. "The S/Key Password System." http://www.ece.nwu.edu/CSEL/skey/skey_eecs.html