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.