S/KEY

Last updated December 09, 2024

S/KEY is a one-time password system developed for authentication to Unix-like operating systems, 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 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.^[1] One common implementation is called 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 SSH and other cryptographic protocols that can secure an entire session, not just the password, S/KEY is falling into disuse.^{[ citation needed ]} Schemes that implement two-factor authentication, by comparison, are growing in use.^[2]

Password generation

The server is the computer that will perform the authentication.

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ⁿ(W).
The initial secret W is discarded.
The user is provided with the n passwords, printed out in reverse order:
Hⁿ(W), Hⁿ⁻¹(W), ..., H(H(W)), H(W).
The passwords H(W), H(H(W)), ..., Hⁿ⁻¹(W) are discarded from the server. Only the password Hⁿ(W), the one at the top of the user's list, is stored on the server.

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 $\left\lceil {\frac {\log n}{2}}\right\rceil$ hash calculations per step and storing $\lceil \log n\rceil$ passwords.^[3]

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, 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 pwd on the list and scratches that password.
The server attempts to compute H(pwd), where pwd is the password supplied. If H(pwd) produces the password the server has stored, then the authentication is successful. The server will then store pwd as the current reference.

For subsequent authentications, the user will provide password_i. (The last password on the printed list, password_n, is the first password generated by the server, H(W), where W is the initial secret). The server will compute H(password_i) and will compare the result to password_i−1, 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 password_i, 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 password_i−1, because this password is the one that will be used for the next authentication.

However, this would require inverting the hash function that produced password_i−1 using password_i (H(password_i−1) = password_i), 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 conditions, 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 ssh, 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⁶⁴, 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.^[4]

Someone with access to an S/KEY database can break all of them in parallel with a complexity of 2⁶⁴. 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".^[5]

Related Research Articles

Kerberos is a computer-network authentication protocol that works on the basis of tickets to allow nodes communicating over a non-secure network to prove their identity to one another in a secure manner. Its designers aimed it primarily at a client–server model, and it provides mutual authentication—both the user and the server verify each other's identity. Kerberos protocol messages are protected against eavesdropping and replay attacks.

A password, sometimes called a passcode, is secret data, typically a string of characters, usually used to confirm a user's identity. Traditionally, passwords were expected to be memorized, but the large number of password-protected services that a typical individual accesses can make memorization of unique passwords for each service impractical. Using the terminology of the NIST Digital Identity Guidelines, the secret is held by a party called the claimant while the party verifying the identity of the claimant is called the verifier. When the claimant successfully demonstrates knowledge of the password to the verifier through an established authentication protocol, the verifier is able to infer the claimant's identity.

The Secure Shell (SSH) Protocol is a cryptographic network protocol for operating network services securely over an unsecured network. Its most notable applications are remote login and command-line execution.

An authenticator is a means used to confirm a user's identity, that is, to perform digital authentication. A person authenticates to a computer system or application by demonstrating that he or she has possession and control of an authenticator. In the simplest case, the authenticator is a common password.

A passphrase is a sequence of words or other text used to control access to a computer system, program or data. It is similar to a password in usage, but a passphrase is generally longer for added security. Passphrases are often used to control both access to, and the operation of, cryptographic programs and systems, especially those that derive an encryption key from a passphrase. The origin of the term is by analogy with password. The modern concept of passphrases is believed to have been invented by Sigmund N. Porter in 1982.

In computer security, challenge-response authentication is a family of protocols in which one party presents a question ("challenge") and another party must provide a valid answer ("response") to be authenticated.

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function. KDFs can be used to stretch keys into longer keys or to obtain keys of a required format, such as converting a group element that is the result of a Diffie–Hellman key exchange into a symmetric key for use with AES. Keyed cryptographic hash functions are popular examples of pseudorandom functions used for key derivation.

passwd is a command on Unix, Plan 9, Inferno, and most Unix-like operating systems used to change a user's password. The password entered by the user is run through a key derivation function to create a hashed version of the new password, which is saved. Only the hashed version is stored; the entered password is not saved for security reasons.

The Encrypting File System (EFS) on Microsoft Windows is a feature introduced in version 3.0 of NTFS that provides filesystem-level encryption. The technology enables files to be transparently encrypted to protect confidential data from attackers with physical access to the computer.

In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage.

A one-time password (OTP), also known as a one-time PIN, one-time passcode, one-time authorization code (OTAC) or dynamic password, is a password that is valid for only one login session or transaction, on a computer system or other digital device. OTPs avoid several shortcomings that are associated with traditional (static) password-based authentication; a number of implementations also incorporate two-factor authentication by ensuring that the one-time password requires access to something a person has as well as something a person knows.

The Secure Remote Password protocol (SRP) is an augmented password-authenticated key exchange (PAKE) protocol, specifically designed to work around existing patents.

A rainbow table is a precomputed table for caching the outputs of a cryptographic hash function, usually for cracking password hashes. Passwords are typically stored not in plain text form, but as hash values. If such a database of hashed passwords falls into the hands of attackers, they can use a precomputed rainbow table to recover the plaintext passwords. A common defense against this attack is to compute the hashes using a key derivation function that adds a "salt" to each password before hashing it, with different passwords receiving different salts, which are stored in plain text along with the hash.

In a Windows network, NT LAN Manager (NTLM) is a suite of Microsoft security protocols intended to provide authentication, integrity, and confidentiality to users. NTLM is the successor to the authentication protocol in Microsoft LAN Manager (LANMAN), an older Microsoft product. The NTLM protocol suite is implemented in a Security Support Provider, which combines the LAN Manager authentication protocol, NTLMv1, NTLMv2 and NTLM2 Session protocols in a single package. Whether these protocols are used or can be used on a system, which is governed by Group Policy settings, for which different versions of Windows have different default settings.

In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking, and key stretching is intended to make such attacks more difficult by complicating a basic step of trying a single password candidate. Key stretching also improves security in some real-world applications where the key length has been constrained, by mimicking a longer key length from the perspective of a brute-force attacker.

A hash chain is the successive application of a cryptographic hash function to a piece of data. In computer security, a hash chain is a method used to produce many one-time keys from a single key or password. For non-repudiation, a hash function can be applied successively to additional pieces of data in order to record the chronology of data's existence.

OTPW is a one-time password system developed for authentication in Unix-like operating systems by Markus Kuhn. A user's real password is not directly transmitted across the network. Rather, a series of one-time passwords is created from a short set of characters and a set of one-time tokens. As each single-use password can only be used once, passwords intercepted by a password sniffer or key logger are not useful to an attacker.

crypt is a POSIX C library function. It is typically used to compute the hash of user account passwords. The function outputs a text string which also encodes the salt, and identifies the hash algorithm used. This output string forms a password record, which is usually stored in a text file.

In cryptography, the Salted Challenge Response Authentication Mechanism (SCRAM) is a family of modern, password-based challenge–response authentication mechanisms providing authentication of a user to a server. As it is specified for Simple Authentication and Security Layer (SASL), it can be used for password-based logins to services like LDAP, HTTP, SMTP, POP3, IMAP and JMAP (e-mail), XMPP (chat), or MongoDB and PostgreSQL (databases). For XMPP, supporting it is mandatory.

References

↑ "OpenSSH Project History". OpenSSH . Retrieved 2019-12-05.
↑ "Global Multi-factor Authentication Market 2017-2021" . TechNavio. August 2017. Retrieved 2019-12-05.
↑ 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.
↑ Samuel, Michael (2011-07-01). "S/Key Dungeon Attack" . Retrieved 2019-12-05.
↑ Haller, Neil; Metz, Craig; Nesser II, Philip J.; Straw, Mike (1998). "Appendix D: Dictionary for Converting Between 6-Word and Binary Formats". A One-Time Password System. IETF. doi: 10.17487/RFC2289 .

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "OpenSSH Project History". OpenSSH . Retrieved 2019-12-05.

[2] "Global Multi-factor Authentication Market 2017-2021" . TechNavio. August 2017. Retrieved 2019-12-05.

[3] 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.

[4] Samuel, Michael (2011-07-01). "S/Key Dungeon Attack" . Retrieved 2019-12-05.

[5] Haller, Neil; Metz, Craig; Nesser II, Philip J.; Straw, Mike (1998). "Appendix D: Dictionary for Converting Between 6-Word and Binary Formats". A One-Time Password System. IETF. doi: 10.17487/RFC2289 .

[1]

[2]

[3]

[4]

[5]