Nomenclature
“One-Time Passwords”, with a hyphen between the first couple of words and not the latter words, is the way that the words are written in RFC 2289. Certainly there are many uses of the phrase “One Time Passwords” without any hyphens.
Overview

A mixture of a neat/new technology (one time credentials) and an archaic technology (passwords that are short enough to be reasonably typed on demand) that would, in many cases, be best to be replaced (with rather automated, but highly controlled, handling of longer keys).

The basic idea of one-time passwords is that a secret (key/passphrase) is used to generate a series of credentials (such as passphrases). In at least some cases, the same sequence of credentials may be easily recreated as long as the same secret is used to seed the same algorithm. Therefore, if a portable device (such as a laptop or something smaller such as a PDA or perhaps a “smart” wireless phone) is both trusted and available, that device may re-generate the sequence of credentials (or at least a relevant portion of that sequence). Those credentials may then be used on a less truthworthy client. If a keyboard logger captures a passphrase that is successfully used, that should not cause a breach of security because those exact same credentials will not be accepted again. The next time the person logs in, different credentials (from the same series of credentials) will be required.

The effectiveness is discussed in RFC 3631 Section 3.1.

For this to work, the software which is requesting credentials needs to support the one-time password feature. At minimum, the software needs to invalidate credentials that are accepted so that they do not work again. (Typically, the way that the authenticating software, such as a remote command line or an FTP site, invalidates such credentials is to call a function/plugin/module which both performs the authentication and which will invalidate any successfully used credentials.)

Typically the software, when asking for authentication credentials, will also report a number which represents a specific set of credentials. The user logging in can then use that number, along with the secret key/passphrase, to generate a very specific set of disposable credentials that is being requested by the software. The software asking for authentication will somehow need to keep track of that number to make sure that the same credentials aren't being re-used. The user won't need to keep track of the number because it is displayed each time. (However, the user may be able notice somebody logging into the account if that number ever gets lowered unexpectedly. If a user regularly uses such credentials from two different locations each day, the user who hasn't really memorized the exact number could notice a change if the number is even when it was expected that the number is odd.)

Implementations note

There are multiple implementations for one-time passwords. RFC 2289 describes “A One-Time Password System” (which the RFC refers to as “OTP”) and states that “OTP evolved from the S/KEY (SKEY is a trademark of Bellcore) One-Time Password System that was released by Bellcore”. OpenBSD FAQ 8.10 - S/Key shows that OpenBSD seems to prefer a method known as s/key. (This may be the same as what is described by RFC 1760: S/KEY One-Time Password System. OpenBSD's man page for skey does state “This implementation of S/Key is RFC 2289 compliant.”) RFC 2444: OTP-SASL describes yet another mechanism.

Implementations Details
OpenBSD Guide to using S/Key with OpenSSH

This is basically coming from the steps from OpenBSD FAQ 8.10 - S/Key. (The instructions have been modified using information from sources such as the OpenBSD man page for skeyinit and/or OpenBSD man page for skeyinfo, although that FAQ covers the basics.)

Creating the keys
First time only: Enable

First, see if S/Key was ever initialized: “ ls -d /etc/skey* ” may reveal “ls: /etc/skey*: No such file or directory” This indicates that S/Key hasn't yet been “enabled” by the superuser, so that needs to be performed. (The (OpenBSD) Man page for skeyinit notes, “Only the superuser may use the -E option.” Because of that, some method of elevating privileges should be performed. (The following example uses sudo which is included in a regular OpenBSD installation.)

ls -ld /etc/skey
sudo skeyinit -E
ls -ld /etc/skey*
sudo ls -la /etc/skey/.

With a “new-style database”, as described by OpenBSD's manual page for skeyinit (in the section about the -C parameter), the data is stored in a subdirectory called /etc/skey. If so, the immediately visible results of those command lines may be:

ls: /etc/skey/*: No such file or directory

drwx-wx--T  2 root  auth  512 Mon DD hh::mm /etc/skey

drwx-wx--T   2 root  auth    512 Mon DD hh::mm .
drwx-wx--T  24 root  wheel  2560 Mon DD hh::mm ..

(As can be seen by that example display of the permissions, the group named “auth” may be able to write to the directory, but cannot read from it. The owner is the user account named “root”. These same permissions shown by the example mean that those who are not the specified user account that owns this directory, and also are not part of the specified group, do not have access. Such a person may neither read from, nor write to, this directory.)

If the results show a file named /etc/skeykeys then the data is stored in what OpenBSD's manual page for skeyinit calls an “old-style database”. If so, it may be desirable to see about making sure that recent software is being used and then checking into converting the database using “ skeyinit -C ”.

Making the keys

Note: Although the skeyinit -E command needed to be run as root, this process must be done by running commands as the end user who will then be using the keys.

Then, ensure that the console session is secure. (If there is a remote session being used, make sure that it is done so securely.) Ensure that the skeyinit command being used is run as the end user for whom the new series of keys will be generated. That means that if the end user that will be using the keys has a user name of myusrnam, then the following command that generates the keys needs to be run as the user named myusrnam, and should not be run from another user (such as root.)

The command that the end user should run may be something like the following:

skeyinit -x -n 9999 -sha1

This will ask for the user to authenticate. Enter in the user's password. (The above example command line will use the default “-a passwd” method. Other methods may be used by specifying -a krb5 or, if S/Key had previously been set up and a new keychain is being created, -a skey. Using authorization key files (like SSH key files) is NOT a supported option, so if that is the only authentication method that the user has to be able to log into the machine, another method will need to be set up (at least temporarily) so that the user may authenticate.

Once the user is authenticated, then it will ask the user to come up with a secret passphrase. The end user should be able to recall this passphrase.

If the passphrase is accepted, then OpenBSD FAQ 8.10 - S/Key points out that one of the lines in the output “gives a lot of information to the user.” The following example output is similar to what could be generated if the -x parameter was not used.

ID username skey is otp-hashtype number-of-keys host12345
Next login password: SIX WORD LESS THAN FIVE CHAR

Speculation: Perhaps RFC 2289 Appendix D may contain the list fo words that gets used?

If the -x parameter is used, the output may be something that looks a bit more similar in structure to the following:

ID username skey is otp-hashtype number-of-keys host12345
Next login password: 0123 4567 89AB CDEF

If the -x parameter was used, then the next login password will be made up of eight hexadecimal digits broken up into four groups (with a space between each 16-bit word). Otherwise, it shows up as six words which are (generally?) three or four characters long. If the six english words are used, they must be converted to the same sort of value that is shown with -x, because entering either style of passphrase will generally work fine. This reveals that those words don't equate to anything different than the hexademical digits: Either is accepted. The -x parameter simply affects how the passphrase is displayed. However, during a bit of manual testing, there have been some cases where a passphrase displayed without -x seemed to not be accepted, and the solution was just to use -x when the passphrases were being displayed.

A name has been assigned to the newly generated key for this user. In the (example) text above, the name of the key is “host12345”. (It will likely start with four characters from the current system name, plus a five or six digit value which seems random the first time that skeyinit generates keys. However, it clearly isn't strictly purely random, because the number is incremented when more keys are made.)

Be sure to record that name which has been assigned to the newly generated key for this user. That name will be needed anything a new sequence of passwords must be generated. If it is lost, a system administrator may obtain the key by viewing the file. If the user is logged in and can sudo, then the name is part of the output (specifically it may be the fourth line of output) when running the following command:

sudo cat /etc/skey/$( whoami )
Finding out what the passphrases are

Then, generate some passphrases.

skey -x -sha1 -n 5 9999 uniq12345

If a -x parameter wasn't used with skeyinit then don't use it for skey to generate and display codes, and if -x parameter was used with skeyinit then do use it for skey to generate and display codes. The importance of matching those commands is so that the same code may be displayed, so that it may be confirmed that the codes match.

The number after “ -n ” is how many passphrases to show. The next number after that (shown as 9999 in the command line syntax) is the initial “sequence number”. There are a few ways to determine the sensible value for the initial “sequence number”. One way is to look at the output of the skeyinit command, between the hash type and the name of the key. That will be the same as the number that was specified by the optional “ -n ” command line parameter when skeyinit generated the key, so another way is to refer to that command. Another way is to check the file visible by running:

sudo cat /etc/skey/$( whoami )

Yet another way to get the sequence number may be to get asked for the credentials, which can happen by trying to create a connection that would use the credentials.

Finally, the last part shown in that example command line is the name of the key being used for this user account. The name of the key being used for the user account was provided by the skeyinit that generated the key for that user. (It was host12345 in the example that showed a key being created.) The key also shows up after the sequence number when a program is seeking to authenticate by using one of the disposable passphrases. (That may not be visible until after the username has been specified.)

Example input/output:

$ skey -x -sha1 -n 5 9999 host12345
Reminder - Do not use this program while logged in via telnet.
Enter secret passphrase:
9995: 4567 89AB CDEF 0123
9996: 3456 789A BCDE F012
9997: 2345 6789 ABCD EF01
9998: 1234 5678 9ABC DEF0
9999: 0123 4567 89AB CDEF

Review the key provided for the initial sequence number. (In the example command line shown above, the initial sequence number was 9999. Therefore, for that example, review the output that starts with the line “9999: ”.) That key will never be able to be used to authenticate a user, however, it can be compared with the key that was output from the skeyinit command. If they match, that indicates that the name of the newly generated key (“host12345” in the example text), and the user's passphrase were properly entered, and so the other passphrases listed are likely to be useful. Hopefully this also means that the name of the key (e.g. “host12345”) and the user's passphrase were both successfully recorded, and so they will be able to be used again at a later time (if needed). If the keys don't match, that probably means that the passphrase was entered incorrectly (even though the non-matching passphrase does appear to be accepted). In such a case, try again to generate keys. If the resulting keys continue to not match the original key (and perhaps do match each other), that suggests there may have been a typo from when the keys were generated. In that case, (start over by proceeding to) generate a new set of keys.

Note that the skey program can give out strings of passphrases even if the specified algorithm (e.g. “ -sha1 ” on the command line) is wrong (or omitted and defaulting to the wrong algorithm) and/or if the key (e.g. host12345) specified on the command line is wrong and/or if the passphrase is wrong. If any of these things are wrong, passphrases are shown without error messages or any other sort of trouble, but the passphrases shown are not likely to match what the server is expecting. (Naturally, if the passphrase does not match what the server is expecting, the key passphrase will be rejected. Therefore, the passphrases shown are likely useless.) It is also possible to print multiple passphrases which were never valid: “ skeyinit -sha1 -n 4 ” will generate 4 working keys (which are key number zero through key number three). Then running skey -sha1 -n 8 6 host123456 will start at the key number that was specified on the command line (key number 6), even though key number 6 and key number 5 have never been valid and serve no purpose. The next key, key number 4, represents the initial sequence number: This number also has never been valid for logging in (the first usable sequence number was key 3), although this key may be compared with the output from skeyinit to help validate that the rest of the keys are valid. (Note that the command line specifies to show 8 keys: Only seven will be shown, numbered zero through six, because the skey program always stops at zero.) So...

Do not trust the passphrases will be valid just because they were printed. Mistyping a passphrase may still generate some keys that look valid, but are not. If there is a possibility that a passphrase was mistyped, be sure to compare the passphrases with one known working passphrase before trusting any of the passphrases that have been printed.

It seemed (on multiple occasions and using different keys) through testing (even through both careful typing and using copy and paste) that sometimes the valid passphrases, as printed by the skey command, may not be accepted. Of course, this is disasterous because if one key does not work well, the login will never occur and so the current sequence number will never lower, so the rest of the keys also end up not being usable (until the earlier one starts to work). The solution was to use -x to print out a valid passphrase that uses hexademical digits rather than words. That key worked (even though the skeyinit command that created the key being used did not use the -x parameter).

Once a list of passphrases are known, to check which passphrase will actually be asked for next, run: “ skeyinfo -v”. That will show the hash type, the current sequence number (which will be less than the initial sequence number), and the key that was provided by the skeyinit. All passphrases in the list before the next one that will be asked for are useless. (If such useless passphrases have been recorded/printed, they are useless so they may be “crossed off”/deleted/erased/shredded at will.)

To generate more keys, one option is to use the skey command. In OpenBSD, another option to get a single password is to run the output of the skeyinfo -v command. The output of “ skeyinfo -v ” will show the hashtype (starting with the string “otp-”) and some other information: The reason this works is because OpenBSD has an executable (in the path) named after each supported hash type, so it may logically be accurantely concluded that running the hash type as a command will work: the remaining output of “ skeyinfo -v ” is formatted in a way that it works as the parameters for the command that is named after the hash type being used. In an sh-compatible shell, use “ $( skeyinfo -v ) ”. The biggest downside of doing it that way is that command line parameters such as -x and “ -n number must come before the sequence number (which must come before the key), so those parameters can't be used when trying to find keys using this sort of method.

If the current sequence number (shown by skeyinfo -v as well as any program which is accepting input) is -1 (negative one), then the last usable passphrase has been used and it is not possible to log in. Be sure to create a new set of credentials, by creating a new key, before running out of usable keys! (Routinely running skeyaudit may help generate warnings. For details, see OpenBSD's man page for skeyaudit.)

Putting the passphrases to use

To put them to use, try using “username:skey” instead of just “username” when logging into the OpenBSD version of any of the following programs that come with OpenBSD: OpenSSH (sshd), or ftpd, or telnetd. (Likely some others as well. Local logins?)

Note: Some SSH software might not support using a username that ends with “:skey” in the same way as other possible usernames. For instance, PSCP (which is SCP file transfer software that is part of the PuTTY uite of SSH software) supports using “ username@hostname:/fileDir” syntax. In that case, anything after the colon will be treated like a directory, and so the username will be treated like a network host name, which will not work. An alternative for this software is to use “ -l username:skey hostname:/fileDir ”. The use of the -l syntax, to specify a login name, is also supported by the OpenSSH client (mentioned on the page about SSH software).

It was previously noted here that the -l syntax is supported by the OpenSSH suite of software. However, it appears that the scp and sftp software use -l for a different purpose. Using “ -o User=acctname:skey ” will be helpful in this case.

Unfortunately, at the time of this writing, it seems that curl does not support specifying a login (username) containing a colon. (There is a short old Usenet thread about such logins.)

Troubleshooting
Verifying a sensible password prompt

When making the connection and specifying “:skey” as the last part of the specified username, the prompt should show which key is being asked for. The output may look like the following:

“Using keyboard-interactive authentication.
otp-sha1 9998 uniq12345
S/Key Password:”

If that isn't happening, make sure that the user's key information is stored in a file that is named after the user and is stored in /etc/skey/.

Using the right key

Failed password attempts (possibly caused by another person) may use up a key. In that case, the password prompt will start asking for another key. Make sure the number provided by the password prompt corresponds to number by the key that is being used.

It seems likely that if the passphrase was manually typed when creating a keychain, then the passphrase was typed correctly. This is because that portion of the process requires that the passphrase is typed twice in a row, and that the input matches. (This protection mechanism is easily defeated if a user just copied and pasted the incorrect text twice in a row.) However, the process of showing keys requires that the passphrase be typed in. If there was a typo at that point, then there will be no error message displayed, but the keys shown won't be useful.

If necessary, re-make the keys by copying and pasting the same passphrase at every stage of the step. Also make sure that every other portion of the process, like specifying the “name” of the key (which is shown as “uniq12345 ” in some of the example text) is correct.

Try using hexadecimal

Some tests have indicated that the non-hexadecimal codes may occassionally not work. If that is the case, use the -x parameter to get hexadecimal codes. Those codes should work even if the keychain wasn't created using hexadecimal codes.

Checking logs
See /var/log/authlog in case that file provides any clues.1
Solutions for Android
OTPDroid

Google Play: OTPDroid states that this app “has access to these permissions”: “Phone calls”, “read phone status and identity”

Presumably that is to get some sort of identifier. This seems fairly benign, as it is simply reading information.

Open Source OTPDroid source home (Github) identifies this as a “fork of http://android.f00d.nl/opiekey/”.

This works: place in the required information and click “Calculate”. However, the output is only words; it does not seem to have an option to show hexadecimal characters as output.

The default may be to show 3 responses. This is configurable. If you are concerned that might record (by memorizing or writing down) the next series of words, change that to show 1 response.

Others

Perhaps search for OTP or opie? Following is some information about untested or non-recommended software.

https://play.google.com/store/apps/details?id=nu.kelvin.potato
https://play.google.com/store/apps/details?id=ro.len.mobile
https://play.google.com/store/apps/details?id=net.laserbunny.android.otp
https://play.google.com/store/apps/details?id=nl.f00d.android.opiekey requires more permissions
Also, http://motp.sf.net may list some software.

Mobile-OTP
https://play.google.com/store/apps/details?id=org.cry.otp
http://chris-miceli.blogspot.com/2009/12/mobile-otp-android-client.html
DroidOTP

DroidOTP at Google Play says “This application requires no special permissions to run.”

This does not seem to use the same OTP as OTPDroid. The challenge seems to expect a PIN, not a text string. Likely not compatible/useful for trying to use with OpenBSD's s/key implementation.

After installing and running the program, press the Menu button. Choose to Add a profile.