276 lines
11 KiB
Plaintext
276 lines
11 KiB
Plaintext
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.
|