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 which consists of the $seed$ and $n-1$ (where $h_{n}$ is the hash value that is stored on the host) and also mentions 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.