View source for S/KEY

{{Short description|One-time password system}}
'''S/KEY''' is a [[one-time password]] system developed for [[authentication]] to [[Unix-like]] [[operating system]]s, especially from [[dumb terminals]] or untrusted public computers on which one does not want to type a long-term password. A user's real password is combined in an offline device with a short set of characters and a decrementing counter to form a single-use password. Because each password is only used once, they are useless to [[Packet sniffer|password sniffers]].

Because the short set of characters does not change until the counter reaches zero, it is possible to prepare a list of single-use passwords, in order, that can be carried by the user. Alternatively, the user can present the password, characters, and desired counter value to a local calculator to generate the appropriate one-time password that can then be transmitted over the network in the clear. The latter form is more common and practically amounts to [[challenge–response authentication]].

S/KEY is supported in [[Linux]] (via [[pluggable authentication modules]]), [[OpenBSD]], [[NetBSD]], and [[FreeBSD]], and a generic open-source implementation can be used to enable its use on other systems. [[OpenSSH]] also implements S/KEY since version OpenSSH 1.2.2 was released on December 1, 1999.<ref>{{cite web
| url=https://www.openssh.com/history.html
| title=OpenSSH Project History
| publisher=[[OpenSSH]]
| accessdate=2019-12-05}}</ref>  One common implementation is called [[OPIE Authentication System|OPIE]]. S/KEY is a trademark of [[Telcordia Technologies]], formerly known as Bell Communications Research (Bellcore).

S/KEY is also sometimes referred to as [[Lamport's scheme]], after its author, [[Leslie Lamport]]. It was developed by Neil Haller, [[Phil Karn]] and John Walden at Bellcore in the late 1980s. With the expiration of the basic patents on
[[public-key cryptography]] and the widespread use of [[laptop computers]] running [[Secure Shell|SSH]] and
other cryptographic protocols that can secure an entire session, not just the password, S/KEY is falling
into disuse.{{citation needed|date=January 2013}}  Schemes that implement [[two-factor authentication]], by comparison, are growing in use.<ref>{{cite web
 | url = https://www.researchandmarkets.com/reports/4368880/global-multi-factor-authentication-market-2017
 | title = Global Multi-factor Authentication Market 2017-2021
 | date = August 2017
 | publisher = TechNavio 
 | url-access = subscription
 | accessdate = 2019-12-05
}}</ref>

==Password generation==
The ''server'' is the computer that will perform the authentication.

[[File:Skey password generation.svg|thumb|280px|S/KEY password generation]]
# This step begins with a secret key ''W''. This secret can either be provided by the user, or can be generated by a computer. Either way, if this secret is disclosed, then the security of S/KEY is compromised.
# A [[cryptographic hash function]] ''H'' is applied ''n'' times to ''W'', thereby producing a [[hash chain]] of ''n'' one-time passwords. The passwords are the results of the application of the cryptographic hash function: 
#:''H''(''W''), ''H''(''H''(''W'')), ..., ''H''<sup>''n''</sup>(''W'').
# The initial secret ''W'' is discarded.
# The user is provided with the ''n'' passwords, printed out in reverse order:
#:''H''<sup>''n''</sup>(''W''), ''H''<sup>''n''−1</sup>(''W''), ..., ''H''(''H''(''W'')), ''H''(''W'').
# The passwords ''H''(''W''), ''H''(''H''(''W'')), ..., ''H''<sup>''n''−1</sup>(''W'') are discarded from the server. Only the password ''H''<sup>''n''</sup>(''W''), the one at the top of the user's list, is stored on the server.

==Authentication==
[[File:skey authentication.svg|thumb|320px|S/KEY authentication]]
After password generation, the user has a sheet of paper with ''n'' passwords on it. If ''n'' is very large, either storing all ''n'' passwords or calculate the given password from ''H''(''W'') become inefficient. There are methods to efficiently calculate the passwords in the required order, using only <math>\left\lceil\frac{\log n}{2}\right\rceil</math> hash calculations per step and storing <math>\lceil\log n\rceil</math> passwords.<ref>D. Yum, J. Seo, S. Eom, and P. Lee, “Single-Layer Fractal Hash Chain Traversal with Almost Optimal Complexity,” Topics in Cryptology–CT-RSA 2009, pp. 325–339, 2009. [https://doi.org/10.1007/978-3-642-00862-7_22]</ref>

More ideally, though perhaps less commonly in practice, the user may carry a small, portable, secure, non-networked computing device capable of regenerating any needed password given the secret passphrase, the [[Salt (cryptography)|salt]], and the number of iterations of the hash required, the latter two of which are conveniently provided by the server requesting authentication for login.

In any case, the first password will be the same password that the server has stored.  This first password will not be used for authentication (the user should scratch this password on the sheet of paper), the second one will be used instead:
* The user provides the server with the second password {{kbd|pwd}} on the list and scratches that password.
* The server attempts to compute ''H''({{tt|pwd}}), where {{tt|pwd}} is the password supplied. If ''H''({{tt|pwd}}) produces the password the server has stored, then the authentication is successful. The server will then store {{tt|pwd}} as the current reference.

For subsequent authentications, the user will provide {{kbd|password}}<sub>''i''</sub>. (The last password on the printed list, {{tt|password}}<sub>''n''</sub>, is the first password generated by the server, ''H''(''W''), where ''W'' is the initial secret).
The server will compute ''H''({{tt|password}}<sub>''i''</sub>) and will compare the result to {{tt|password}}<sub>''i''−1</sub>, which is stored as reference on the server.

==Security==
The security of S/KEY relies on the difficulty of reversing [[cryptographic hash functions]]. Assume an attacker manages to get hold of a password that was used for a successful authentication. Supposing this is {{tt|password}}<sub>''i''</sub>, this password is already useless for subsequent authentications, because each password can only be used once. It would be interesting for the attacker to find out {{tt|password}}<sub>''i''−1</sub>, because this password is the one that will be used for the next authentication.

However, this would require inverting the hash function that produced {{tt|password}}<sub>''i''−1</sub> using {{tt|password}}<sub>''i''</sub> (''H''({{tt|password}}<sub>''i''−1</sub>) = {{tt|password}}<sub>''i''</sub>), which is extremely difficult to do with current [[cryptographic hash functions]].

Nevertheless, S/KEY is vulnerable to a [[man in the middle attack]] if used by itself. It is also vulnerable to certain [[race condition]]s, such as where an attacker's software sniffs the network to learn the first ''N'' − 1 characters in the password (where ''N'' equals the password length), establishes its own TCP session to the server, and in rapid succession tries all valid characters in the ''N''-th position until one succeeds. These types of vulnerabilities can be avoided by using [[Secure shell|ssh]], [[Secure Sockets Layer|SSL]], SPKM, or other encrypted transport layer.

Since each iteration of S/KEY doesn't include the salt or count, it is feasible to find collisions directly without breaking the initial password.  This has a complexity of 2<sup>64</sup>, which can be pre-calculated with the same amount of space.  The space complexity can be optimized by storing chains of values, although collisions might reduce the coverage of this method, especially for long chains.<ref>{{cite web|title=S/Key Dungeon Attack|date=2011-07-01|last=Samuel|first=Michael|url=https://www.miknet.net/security/skey-dungeon-attack/|accessdate =2019-12-05}}</ref>

Someone with access to an S/KEY database can break all of them in parallel with a complexity of 2<sup>64</sup>.  While they wouldn't get the original password, they would be able to find valid credentials for each user.  In this regard, it is similar to storing unsalted 64-bit hashes of strong, unique passwords.

The S/KEY protocol can loop.  If such a loop were created in the S/KEY chain, an attacker could use user's key without finding the original value, and possibly without tipping off the valid user.  The pathological case of this would be an OTP that hashes to itself.

==Usability==
Internally, S/KEY uses [[64-bit]] numbers. For human [[usability]] purposes, each number is mapped to six short words, of one to four characters each, from a publicly accessible 2048-word dictionary. For example, one 64-bit number maps to "ROY HURT SKI FAIL GRIM KNEE".<ref>{{cite journal
 | url = https://tools.ietf.org/html/rfc2289#page-4-19
 | title = Appendix D: Dictionary for Converting Between 6-Word and Binary Formats
 | journal = A One-Time Password System
 | first1 = Neil | last1 = Haller
 | first2 = Craig | last2 = Metz
 | first3 = Philip J. | last3 = Nesser II
 | first4 = Mike | last4 = Straw
 | year = 1998
 | publisher = [[IETF]]
| doi = 10.17487/RFC2289
 | doi-access = free
 }}</ref>

==See also==
* [[OTPW]]
* [[OPIE Authentication System]]
* PGP [[biometric word list]] uses two lists of 256 words, each word representing 8 bits.

==References==
{{Reflist}}

==External links==
* [https://www.rfc-editor.org/rfc/rfc1760 The S/KEY One-Time Password System (RFC 1760)]
* [https://www.rfc-editor.org/rfc/rfc2289.html A One-Time Password System (RFC 2289)]
* [https://www.ocf.berkeley.edu/~jjlin/jsotp/ jsotp: JavaScript OTP & S/Key Calculator]
* [http://www.orange-carb.org/SkeyCalc/documentation.html#about Introduction to the system]

{{DEFAULTSORT:S KEY}}
[[Category:Cryptographic software]]
[[Category:Password authentication]]