Description of The S/KEY One-Time Password System
  
   Neil M. Haller	nmh@thumper.bellcore.com
   Philip R. Karn	karn@chicago.qualcomm.com
  
  
				ABSTRACT

The S/KEY one-time password system provides authentication over networks
that are subject to eavesdropping/reply attacks. This system has several
advantages compared with other one-time or multi-use authentication
systems.  The user's secret password never crosses the network during
login, or when executing other commands requiring authentication such as
the UNIX passwd or su commands.  No secret information is stored anywhere,
including the host being protected, and the underlying algorithm may be
(and it fact, is) public knowledge. The remote end of this system can run
on any locally available computer.  The host end could be integrated into
any application requiring authentication.


Trademarks
----------
   Athena and Kerberos of trademarks of MIT.
   S/KEY is a trademark of Bellcore.
   SPX and DEC are trademarks of Digital Equipment Company.
   UNIX is a registered trademark of UNIX System Laboratories, Inc.
 


Attributes of the S/KEY One-Time Password System
------------------------------------------------

The S/KEY authentication system is a simple scheme that protects user
passwords against passive attacks.  It is not as powerful or general in
scope as Kerberos or SDASS; nor does it protect against active attacks.
It can, however, be easily and quickly added to almost any UNIX system
without requiring any additional hardware and without requiring the
system to store information (such as plain text passwords) that would
be more sensitive than the encrypted passwords already stored.  The
S/KEY system can be used with non programmable terminals or personal
computers (e.g., systems running DOS or Apple Macintoshes) with
conventional communications programs.
 
Some of the properties of the S/KEY system are:

   o	Eavesdropping protection

   o	Conceptually simple and easy to use

   o	Based on a memorized secret password; does not require a
	special device although it can easily be adapted to do so.

   o	Can be automated for authentication from a trusted system.
	(Can also be partially automated for fast operation.)

   o	No secret algorithms.

   o	No secrets stored on host.



Description of the S/KEY One-Time Password System
-------------------------------------------------

There are two sides to the operation of our one-time password system.
On the user (or client) side, the appropriate one-time password must
be generated.  On the system (server) side, the one-time password must
be verified.  One time passwords are generated and verified using a
one-way function based on MD4 [Rivest].  (Conversion to MD5 would be
trivial)  
 
We have defined our one-way function to take 8 bytes of input and to
produce 8 bytes of output.  This is done by running the 8 bytes of
input through MD4 and then "folding" pairs of bytes in the 16-byte MD4
output down to 8 bytes with exclusive-OR operations.  This allows us to
apply the one-way function an arbitrary number of times.


Generation of One-Time Passwords 

The sequence of one-time passwords is produced by applying the one-way
function multiple times.  That is, the first one-way password is
produced by running the user's secret password (s) through the one-way
function some specified number of times, (n).  Assuming n=4,

			p(1) =  f(f(f(f(s))))
 
The next one-way password is generated by running the user's password
through the one-way function only n-1  times.
  
			p(2) = f(f(f(s))) 
 
An eavesdropper who has monitored the use of the one-time password  
p(i) will not be able to generate the next one in the sequence p(i+1)
because doing so would require inverting the one-way function. Without
knowing the secret key that was the starting point of the function
iterations, this can not be done.

Seeding the Password

A user might want to use the same secret password on several machines,
or might allow the iteration count to go to zero.  An initial step
concatenates a seed with the arbitrary length secret password, crunches
the result with MD4, and folds the result to 64 bits.  The result of
this process is then iterated n times.


System Verification of Passwords 

The host computer first saves a copy of the one-time password it
receives, then it applies the one-way function to it.  If the result
does not match the copy stored in the system's password file, then the
request fails.  If they match, then the user's entry in the system
password file is updated with the copy of the one-time password that
was saved before the final execution (by the server) of the one-way
function.  This updating advances the password sequence.

Because the number of one-way function iterations executed by the user
decreases by one each time, at some point the user must reinitialize the
system or be unable to log in again.  This is done by executing a
special version of the passwd command to start a new sequence of
one-time passwords.  This operation is essentially identical to a
normal authentication, except that the one-time password receive
over the network is not checked against the entry already in the
password file before it replaces it. In this way, the selection of a
new password can be done safely even in the presence of an eavesdropper.


Operation of S/KEY One-Time Password System
-------------------------------------------

Overview 

The S/KEY one-time password authentication system uses computation to
generate a finite sequence of single-use passwords from a single secret.
The security is entirely based on a single secret that is known only to
the user. Alternatively, part of or the entire secret can be stored in a
non-retrievable way, in the computing device.
 

Generation of S/KEY One-Time Passwords 

As mentioned above, the one-time password sequence is derived from the
secret password using a computer.  The required computation has been
executed on a variety of PC and UNIX class machines including notebook
and palm-tops. A vendor has estimated that credit card size devices
could be built for less than $30 in large quantities.

The program can also be stored on and executed from a standard floppy
disk.  This would allow operation on a remote computer that could not be
entirely trusted not to contain a Trojan Horse that would attempt
to capture the secret password.  It is sometimes useful to pre-compute
and print several one-time passwords.  These could be carried on a trip
where public terminals or workstations were available, but no trusted
local computation was available. 


Description of Operation 

The following narrative describes the procedure for logging into a UNIX
system using the S/KEY one-time password system.  To illustrate the
most complex case, we assume a hand-held PC compatible computer is used.
 
  o  The user, call her Sue, identifies herself to the system by login name.
 
  o  The system issues a challenge including the sequence number of the
     one-time password expected and a "seed" that is unique to the system.
     This "seed" allows Sue to securely use a single secret for several
     machines.  Here the seed is "unix3" and the sequence number is 54.
 
  o  Sue enters 54 and unix3 into her palm-top computer.  She is prompted
     for her secret password.
 
  o  Sue enters her secret password that may be of any length.  The palm-top
     computes the 54th one-time password and displays it.
 
  o  Sue enters the one-time password and is authenticated.
 
  o  Next time Sue wants access, she will be prompted for one-time
     password sequence number 53.
 

Semi-Automated Operation 

The complexity illustrated above is necessary only when using a terminal
that is not programmable by the user, or when using a non-trusted
terminal.  We have built semi-automatic interfaces for clients using
communications software on popular personal computers.  The following
example illustrates logging in using a trusted personal computer and a
popular terminal emulation program.

  o  Before starting the communication program, Sue runs the CTKEY
     program that ties a TSR to a "hot-key" such as F10.

  o  Sue identifies herself by login name as above.

  o  The system issues the same challenge including the seed "unix3"
     and the sequence number 54.  The host system now expects an
     s/key one-time password.

  o  Sue presses the hot-key and is then prompted for a secret password
     by the TSR program on the local system.

  o  In response to Sue's secret password, the 54th one-time password
     is displayed at the position of the cursor.

  o  Sue presses "Insert" and the terminal emulator transmits the
     one-time password completing the authentication.

If the personal computer were in a trusted location, an option of the
CTKEY program allows the secret password to be stored in a local file.


Form of Password 

Internally the one-time password is a 64 bit number.  Entering a 64 bit
number is not a pleasant task.  The one-time password is therefore
converted to a sequence of six short words (1 to 4 letters). Each word
is chosen from a dictionary of 2048 words.  The contents of this
dictionary is not a secret.


Source Screening 

It is frequently desirable to allow internal access with a multi-use
password while requiring one-time passwords for external access.
A screening table provides this function.  When this table is present,
login attempts that pass the screening test are permitted to use the
normal password or a one-time password.  Others are notified that the
use of the one-time password is required.


Password echo 

Normally systems disable printing during the typing of a password so
that an onlooker cannot steal the password.  With a one-time password,
this is unnecessary.  The replacement  login  command allows the user
to turn echo on by pressing "return" at the password prompt.  This
makes it easier to enter the longer one-time password.


Acknowledgments
---------------
The idea behind our system was originally described by Leslie Lamport. 
Some details of the design were contributed by John S. Walden who
wrote the initial version of the client software.


References
----------

Eugene H. Spafford, "The internet worm program: An analysis."  Computer
Communications Review 19(1):17-57, January 1989.

 
D. C. Feldmeier and P. R. Karn, "UNIX Password Security - Ten Years
Later", Crypto '89 Conference , Santa Barbara, CA August 20-24, 1989.

 
J. G. Steiner, C. Neuman, and J. I. Schiller. "Kerberos: An
authentication service for open network systems."   USENIX Conference
Proceedings, pp. 191-202, Dallas, Texas, February 1988.

 
Catherine R. Avril and Ronald L. Orcutt. Athena: MIT's Once and
Future Distributed Computing Project.  Information
Technology Quarterly , Fall 1990, pp. 4-11.

 
R. L. Rivest, The MD4 Message Digest Algorithm,  Crypto '90 Abstracts
(August 1990), 281-291.

 
Leslie Lamport, "Password Authentication with Insecure Communication",
 Communications of the ACM  24.11 (November 1981), 770-772.