Network Working Group N. Haller Request for Comments: 1760 Bellcore Category: Informational February 1995
The S/KEY One-Time Password System
Status of this Memo
This memo provides information for the Internet community. This memo does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
Abstract
This document describes the S/KEY* One-Time Password system as released for public use by Bellcore and as described in reference [3]. A reference implementation and documentation are available by anonymous ftp from ftp.bellcore.com in the directories pub/nmh/...
Overview
One form of attack on computing system connected to the Internet is eavesdropping on network connections to obtain login id's and passwords of legitimate users. The captured login id and password are, at a later time, used gain access to the system. The S/KEY One-Time Password system is designed to counter this type of attack, called a replay attack.
With the S/KEY system, only a single use password ever crosses the network. The user's secret pass-phrase never crosses the network at any time, including during login or when executing other commands requiring authentication such as the UNIX commands passwd or su. Thus, it is not vulnerable to eavesdropping/replay attacks. Added security is provided by the property that no secret information need be stored on any system, including the host being protected.
The S/KEY system protects against external passive attacks against the authentication subsystem. It does not prevent a network eavesdropper from gaining access to private information, and does not provide protection against "inside jobs" or against active attacks where the potential intruder as able to intercept and modify the packet stream.
Haller [Page 1]
RFC 1760 The S/KEY One-Time Password System February 1995
Introduction
There are two sides to the operation of the S/KEY one-time password system. On the client side, the appropriate one-time password must be generated. On the host side, the server must verify the one-time password and permit the secure changing of the user's secret pass- phrase.
An S/KEY system client passes the user's secret pass-phrase through multiple applications of a secure hash function to produce a one-time password. On each use, the number of applications is reduced by one. Thus a unique sequence of passwords is generated. The S/KEY system host verifies the one-time password by making one pass though the secure hash function and comparing the result with the previous one- time password. This technique was first suggested by Leslie Lamport [1].
Secure Hash Function
A secure hash function is a function that is easy to compute in the forward direction, but computationally infeasible to invert. The S/KEY system is based on the MD4 Message Digest algorithm designed by Ronald Rivest [2]. Since the S/KEY authentication system went into use, the MD5 Message Digest was released. We have chosen to continue to use MD4 due the large number of client programs that have been distributed. Some sites have generated functionally similar systems based on MD5. Clearly clients and hosts must use the same secure hash function to interoperate.
The S/KEY system one-time passwords are 64 bits in length. This is believed to be long enough to be secure and short enough to be manually entered (see below, Form of Passwords) when necessary.
The S/KEY system applies the secure hash function multiple times, producing a 64 bit final output. MD4 accepts an arbitrary number of bits as input and produces a 128 bit output. The S/KEY secure hash function consists of applying MD4 to a 64 bit input and folding the output of MD4 with exclusive or to produce a 64 bit output.
Generation of One-Time Passwords
This section describes the computation of the S/KEY one-time passwords. It consists of a preparatory step in which all inputs are combined, a generation step where the secure hash function is applied multiple times, and an output function where the 64 bit one-time
Haller [Page 2]
RFC 1760 The S/KEY One-Time Password System February 1995
password is displayed in readable form.
The client's secret pass phrase may be of any length and should be more than eight characters. As the S/KEY secure hash function described above accepts a 64 bit input, a preparatory step is needed. In this step, the pass phrase is concatenated with a seed that is transmitted from the server in clear text. This non-secret seed allows a client to use the same secret pass phrase on multiple machines (using different seeds) and to safely recycle secret passwords by changing the seed. (For ease in parsing, the seed may not contain any blanks, and should consist of strictly alphanumeric characters.) The result of the concatenation is passed through MD4, and then reduced to 64 bits by exclusive-OR of the two 8-byte halves.
The following code fragment uses the MD4 implementation defined in RFC 1320 [2] and defines the preparatory step:
/* Fold result to 64 bits */ md.buffer[0] ^= md.buffer[2]; md.buffer[1] ^= md.buffer[3];
A sequence of one-time passwords is produced by applying the secure hash function multiple times to the output of the preparatory step (called S). That is, the first one-time password is produced by passing S through the secure hash function a number of times (N) specified by the user. The next one-time password is generated by passing S though the secure hash function N-1 times. An eavesdropper who has monitored the transmission of a one-time password would not be able to generate any succeeding password because doing so would require inverting the hash function.
Form of Passwords
The one-time password generated by the above procedure is 64 bits in length. Entering a 64 bit number is a difficult and error prone process. Some S/KEY system one-time password calculator programs insert this password into the input stream, others make it available for system cut and paste. Some arrangements require the one-time password to be entered manually. The S/KEY system is designed to facilitate this manual entry without impeding automatic methods. The one-time password is therefore converted to, and accepted as, a sequence of six short (1 to 4 letter) English words. Each word is chosen from a dictionary of 2048 words; at 11 bits per word, all
Haller [Page 3]
RFC 1760 The S/KEY One-Time Password System February 1995
one-time passwords may be encoded. Interoperability requires at all S/KEY system hosts and calculators use the same dictionary. The standard dictionary is attached to this RFC.
Verification of One-Time Passwords
A function on the host system that requires S/KEY authentication is expected to issue an S/KEY challenge. This challenge give the client the current S/KEY parameters - the sequence number and seed. It is important that the S/KEY challenge be in a standard format so that automated clients (see below) can recognize the challenge and extract the parameters. The format of the challenge is:
s/key sequence_integer seed
The three tokens are separated by single space characters. The challenge is terminated by a blank or a newline.
Given the parameters and the secret pass phrase, the client can compute (or lookup) the one time password. It then passes it to the host system where it can be verified.
The host system has a file (on the UNIX reference implementation it is /etc/skeykeys) containing, for each user, the one-time password from the last successful login, or it may be initialized with the first one-time password of the sequence using the keyinit command (this command name may be implementation dependent). To verify an authentication attempt, it passes the transmitted one-time password through the secure hash function one time. If the result of this operation matches the stored previous one-time password, the authentication is successful and the accepted one-time password is stored for future use.
Because the number of hash function applications executed by the client decreases by one each time, at some point the user must reinitialize the system of be unable to login again. This is done by using the keyinit command which allows the changing of the secret pass phrase, the iteration count, and the seed. A frequent technique is to increment a trailing digit(s) of the seed and to reset the iteration count (to something in range of 500-1000).
Clients
Several programs are available to calculate S/KEY one time passwords. Included in the reference implementation are command line interfaces for UNIX and PC systems (key), TSR interfaces for PCs (ctkey, termkey, and popkey), and GUI interfaces for Macintosh and Windows (keyapp and un-named Macintosh interface).
Haller [Page 4]
RFC 1760 The S/KEY One-Time Password System February 1995
The most basic calculator is the key command whose format is:
key [-n count] sequence seed
The optional count is used to display more than a single one time password. This is useful to create a paper list of one time passwords.
The most automated calculator is the termkey program that runs as a Terminate and Stay Resident (TSR) program on a PC. It scans the screen to find the S/KEY parameters, prompts for the secret pass phrase, and stuffs the one time password into the keyboard buffer.
Acknowledgements
The idea behind S/KEY authentication was first proposed by Leslie Lamport [1]. The specific system described was proposed by Phil Karn, who also wrote most of the reference implementation.
References
[1] Lamport, L., "Password Authentication with Insecure Communication", Communications of the ACM 24.11, November 1981, 770-772.
[2] Rivest, R., "The MD4 Message-Digest Algorithm", RFC 1320, MIT and RSA Data Security, Inc., April 1992
[3] Haller, N., "The S/KEY One-Time Password System", Proceedings of the ISOC Symposium on Network and Distributed System Security, February 1994, San Diego, CA
[4] Haller, N., and R. Atkinson, "On Internet Authentication", RFC 1704, Bell Communications Research and Naval Research Laboratory, October 1994
Haller [Page 5]
RFC 1760 The S/KEY One-Time Password System February 1995
Security Considerations
This entire document is about Security Considerations.
Author's Address
Neil Haller Bellcore MRE 2Q-280 445 South Street Morristown, NJ, 07960-6438, USA
RFC 1760 The S/KEY One-Time Password System February 1995
Dictionary for Converting Between S/KEY 6-Word and Binary Formats
This dictionary is from the module put.c. The code for this module, and an implementation of the entire S/KEY One Time Password System is available by anonymous ftp from ftp.bellcore.com in the directory pub/nmh/skey.