S/KEY

The S/KEY One-Time Password system originally came from Bellcore and is described in RFC 1760. It further evolved through RFC 1938 and RFC 2289 under the name "A One-Time Password System". The system uses a cryptographically strong hash function to generate a sequence of One-Time Passwords from a passphrase and a system identifier or seed. There are several possible hash functions that can be used with the system — MD-4, MD-5 and SHA-1 — but only MD-5 is mandatory to support.

The output of the hash function is not used directly but rather folded down to 64 bits and then either input as a hex string or transformed to the so-called Six Word Format. For this a dictionary of 2048 short (mostly english) words is used, giving 11 bits per word. Six words make up the representation of the hash function's output. The additional two bits are used to store a simple checksum. An example for a resulting password would be TORN ACID SAD VAN RUM BEN.

Let's define the hash function to be used as $H(pass,seed):=F(H_{o}(C(seed,pass)))$, where $F$ is the folding applied, $H_{o}$ is the original secure hash function (e.g. MD-4, MD-5 or SHA-1) and $C$ is the string concatenation.

The folding function $F$ must shorten the result of $H_{o}$ (either 128 bits for MD-4 and MD-5, or 160 bits for SHA-1) down to a fixed size of 64 bits. This is done by XOR'ing the first and the last halves of the hash for MD-4 and MD-5 and in a similar fashion for SHA-1. See the aforementioned RFC for details.

Initialization

The system must be initialized before it can be used. During this process a $seed$ (also called system identifier) is generated which can be between 1 and 16 characters in length and may for example be made up of the host name's first few characters and some random numbers. The seed should be different for each system the same passphrase is used on and should not be reused during successive initializations (at least as long the passphrase is not changed).

During the initialization step the user must choose a password or passphrase ($pass$) which should be at least 10 characters long and must be kept secret. Reusing the same passphrase on different systems should be safe, as long as the seeds differ from each other.

A further parameter choosed during initialization is the initial sequence number or iteration count. A good choice would for example be 100. This number is decremented at each authentication process, and the system must be reinitialized once the sequence number reaches zero.

When initializing the system, a value $h_{I}$ is computed, where $I$ is the initial sequence number. The computation is done through:
$h_{0}:=H(pass,seed)$
$h_{n+1}:=H(h_{n},seed)$

This value is stored together with the seed and the sequence number somewhere on the host that is to be authenticated to. As the passphrase must not be exposed to any attacker, the calculation should be done on a trustworthy system over a secure connection. The $h_{I}$ however does not need to be kept secret.

Authentication

When authentication is desired the host transmits a challenge to the user consisting of the $seed$ and $n-1$ (where $h_{n}$ is the hash value that is stored on the host) and also naming the $H_{o}$ to be used. The user then comes up with $h_{n-1}$ and transmits this hash to the host. The host computes $H(h_{n-1},seed)$ and compares this value with the one in its storage. The user is authenticated, if the result matches in which case $h_{n-1}$ and $n-1$ are stored on the host (replacing $h_{n}$ and $n$). Otherwise the authentication fails.

The system is secure against an eavesdropping attacker because the next authentic hash ($h_{n-1}$) can not be easily computed from a transmitted hash ($h_{n}$). For the very same reason it also is secure against read-only attacks on the host's password storage where only $h_{n}$ is stored.

The user has several ways to come up with $h_{n-1}$. The most obvious approach would be a locally run program on the computer the user wants to authenticate from. This program would take the user's passphrase, the seed and the hash algorithm and compute the necessary authentication hash. As the challenge is transmitted in a machine-parseable format the latter two values can be determined automatically and a modified telnet client could make the process completely transparent to the user, simply prompting her for her passphrase. A similar approach would be to use a pocket calculator style device to user could carry with her.

The most interesting feature with regard to usage as One-Time Password system however is the fact that all the challenges are known in advance and thus the authentication hashes can be computed in advance. Thus the user can use a program on a trusted host, enter the seed and initial sequence number from the initialization process and generate a list of all (or the next 23 or so) authentication hashes. She can then print this list and take it with her.

Then, when doing authentication, the user can mostly ignore the challenge and simply take the next password from her list, marking all used passwords in some way.

Full example

Following is a full example of the complete process. The user's name is alice. The host system is a Gentoo Linux box with an S/KEY PAM module. The passphrase will be Soylent green is people..