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..

(Note: Italic text is keyboard input, Striked italic text is hidden keyboard input.)

alice@gleam alice $ skeyinit -t md5
Password: unix password
[Adding alice]
Reminder - Only use this method if you are directly connected
or have an encrypted channel.  If you are using telnet
or rlogin, exit with no password and use skeyinit -s.

Enter secret password: Soylent green is people.
Again secret password: Soylent green is people.

ID alice skey is otp-md5 99 glea92484
Next login password: JOEY BUB LIVE URGE MOOD TRUE

alice@gleam alice $ su - -c "grep alice /etc/skey/skeykeys"
Password: unix password
alice md5 0099 glea92484        a2611ac2f92be7e0  Nov 07,2004 02:54:52

alice@gleam alice $ skey -t md5 -n 5 98  glea92484
Reminder - Do not use this program while logged in via telnet or rlogin.
Enter secret password: Soylent green is people.
 94: BON JESS KANE AX DEEM GANG   
 95: FILE DICE INCH ELY RUBE COED 
 96: KLAN COOL JADE DIRT RENA SEE 
 97: FIR FOOT BALL GIN RAN LOOK   
 98: DAY LEFT BOON MAUL NO WINE   

alice@gleam alice $ ssh localhost
challenge s/key 98 glea92484
password: DAY LEFT BOON MAUL NO WINE
Last login: Sun Nov  7 02:51:40 2004 from localhost

alice@gleam alice $ logout
Connection to localhost closed.

alice@gleam alice $ ssh localhost
challenge s/key 97 glea92484
password: FIR FOOT BALL GIN RAN LOOK
Last login: Sun Nov  7 02:55:50 2004 from localhost

alice@gleam alice $ logout
Connection to localhost closed.

alice@gleam alice $ su - -c "grep alice /etc/skey/skeykeys"
Password: unix password
alice md5 0097 glea92484        141095470b936564  Nov 07,2004 02:56:05

In the example the user alice first initializes the S/KEY system. To be able to do this she must authenticate with her regular unix password and is then asked for her new, secret passphrase. When the process completes successfully a new entry is created in the skeykeys file giving the hash algorithm, the initial sequence number, the seed (which was created from the hostname and some number) the actual hash in hex and a timestamp. Alice then uses the skey utitlity to print the next authentication password(s) in Six Word Format and logs in to the machine using these passwords. Obviously at each login attempt a different password is needed. After each successful login the skeykeys file is modified to reflect the last hash (in hex) and the corresponding sequence number.