Challenge–response authentication

Last updated

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

Contents

The simplest example of a challenge-response protocol is password authentication, where the challenge is asking for the password and the valid response is the correct password.

An adversary who can eavesdrop on a password authentication can authenticate themselves by reusing the intercepted password. One solution is to issue multiple passwords, each of them marked with an identifier. The verifier can then present an identifier, and the prover must respond with the correct password for that identifier. Assuming that the passwords are chosen independently, an adversary who intercepts one challenge-response message pair has no clues to help with a different challenge at a different time.

For example, when other communications security methods are unavailable, the U.S. military uses the AKAC-1553 TRIAD numeral cipher to authenticate and encrypt some communications. TRIAD includes a list of three-letter challenge codes, which the verifier is supposed to choose randomly from, and random three-letter responses to them. For added security, each set of codes is only valid for a particular time period which is ordinarily 24 hours.

Another basic challenge-response technique works as follows. Bob is controlling access to some resource, and Alice is seeking entry. Bob issues the challenge "52w72y". Alice must respond with the one string of characters which "fits" the challenge Bob issued. The "fit" is determined by an algorithm defined in advance, and known by both Bob and Alice. The correct response might be as simple as "63x83z", with the algorithm changing each character of the challenge using a Caesar cipher. In reality, the algorithm would be much more complex. Bob issues a different challenge each time, and thus knowing a previous correct response (even if it is not obfuscated by the means of communication) does not allow an adversary to determine the current correct response.

Other non-cryptographic protocols

Challenge-response protocols are also used in non-cryptographic applications. CAPTCHAs, for example, are meant to allow websites and applications to determine whether an interaction was performed by a genuine user rather than a web scraper or bot. In early CAPTCHAs, the challenge sent to the user was a distorted image of some text, and the user responded by transcribing the text. The distortion was designed to make automated optical character recognition (OCR) difficult and prevent a computer program from passing as a human.

Cryptographic techniques

Non-cryptographic authentication was generally adequate in the days before the Internet, when the user could be sure that the system asking for the password was really the system they were trying to access, and that nobody was likely to be eavesdropping on the communication channel. To address the insecure channel problem, a more sophisticated approach is necessary. Many cryptographic solutions involve two-way authentication; both the user and the system must verify that they know the shared secret (the password), without the secret ever being transmitted in the clear over the communication channel.

One way this is done involves using the password as the encryption key to transmit some randomly generated information as the challenge, whereupon the other end must return as its response a similarly encrypted value which is some predetermined function of the originally offered information, thus proving that it was able to decrypt the challenge. For instance, in Kerberos, the challenge is an encrypted integer N, while the response is the encrypted integer N + 1, proving that the other end was able to decrypt the integer N. A hash function can also be applied to a password and a random challenge value to create a response value. Another variation uses a probabilistic model to provide randomized challenges conditioned on model input. [2]

Such encrypted or hashed exchanges do not directly reveal the password to an eavesdropper. However, they may supply enough information to allow an eavesdropper to deduce what the password is, using a dictionary attack or brute-force attack. The use of information which is randomly generated on each exchange (and where the response is different from the challenge) guards against the possibility of a replay attack, where a malicious intermediary simply records the exchanged data and retransmits it at a later time to fool one end into thinking it has authenticated a new connection attempt from the other.

Authentication protocols usually employ a cryptographic nonce as the challenge to ensure that every challenge-response sequence is unique. This protects against Eavesdropping with a subsequent replay attack. If it is impractical to implement a true nonce, a strong cryptographically secure pseudorandom number generator and cryptographic hash function can generate challenges that are highly unlikely to occur more than once. It is sometimes important not to use time-based nonces, as these can weaken servers in different time zones and servers with inaccurate clocks. It can also be important to use time-based nonces and synchronized clocks if the application is vulnerable to a delayed message attack. This attack occurs where an attacker copies a transmission whilst blocking it from reaching the destination, allowing them to replay the captured transmission after a delay of their choosing. This is easily accomplished on wireless channels. The time-based nonce can be used to limit the attacker to resending the message but restricted by an expiry time of perhaps less than one second, likely having no effect upon the application and so mitigating the attack.

Mutual authentication is performed using a challenge-response handshake in both directions; the server ensures that the client knows the secret, and the client also ensures that the server knows the secret, which protects against a rogue server impersonating the real server.

Challenge-response authentication can help solve the problem of exchanging session keys for encryption. Using a key derivation function, the challenge value and the secret may be combined to generate an unpredictable encryption key for the session. This is particularly effective against a man-in-the-middle attack, because the attacker will not be able to derive the session key from the challenge without knowing the secret, and therefore will not be able to decrypt the data stream.

Simple example mutual authentication sequence

where

This particular example is vulnerable to a reflection attack.

Password storage

To avoid storage of passwords, some operating systems (e.g. Unix-type) store a hash of the password rather than storing the password itself. During authentication, the system need only verify that the hash of the password entered matches the hash stored in the password database. This makes it more difficult for an intruder to get the passwords, since the password itself is not stored, and it is very difficult to determine a password that matches a given hash. However, this presents a problem for many (but not all) challenge-response algorithms, which require both the client and the server to have a shared secret. Since the password itself is not stored, a challenge-response algorithm will usually have to use the hash of the password as the secret instead of the password itself. In this case, an intruder can use the actual hash, rather than the password, which makes the stored hashes just as sensitive as the actual passwords. SCRAM is a challenge-response algorithm that avoids this problem.

Examples

Examples of more sophisticated challenge-response algorithms are:

Some people consider a CAPTCHA a kind of challenge-response authentication that blocks spambots. [4]

See also

Related Research Articles

<span class="mw-page-title-main">Kerberos (protocol)</span> Computer authentication protocol

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.

<span class="mw-page-title-main">Password</span> Text used for user authentication to prove identity

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.

A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key can be different sizes and varieties, but in all cases, the strength of the encryption relies on the security of the key being maintained. A key's security strength is dependent on its algorithm, the size of the key, the generation of the key, and the process of key exchange.

In computing, the Challenge-Handshake Authentication Protocol (CHAP) is an authentication protocol originally used by Point-to-Point Protocol (PPP) to validate users. CHAP is also carried in other authentication protocols such as RADIUS and Diameter.

In cryptography and computer security, a man-in-the-middle (MITM) attack, or on-path attack, is a cyberattack where the attacker secretly relays and possibly alters the communications between two parties who believe that they are directly communicating with each other, where in actuality the attacker has inserted themselves between the two user parties.

<span class="mw-page-title-main">Block cipher mode of operation</span> Cryptography algorithm

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

Transport Layer Security (TLS) is a cryptographic protocol designed to provide communications security over a computer network, such as the Internet. The protocol is widely used in applications such as email, instant messaging, and voice over IP, but its use in securing HTTPS remains the most publicly visible.

A replay attack is a form of network attack in which valid data transmission is maliciously or fraudulently repeated or delayed. This is carried out either by the originator or by an adversary who intercepts the data and re-transmits it, possibly as part of a spoofing attack by IP packet substitution. This is one of the lower-tier versions of a man-in-the-middle attack. Replay attacks are usually passive in nature.

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.

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.

IEEE 802.11i-2004, or 802.11i for short, is an amendment to the original IEEE 802.11, implemented as Wi-Fi Protected Access II (WPA2). The draft standard was ratified on 24 June 2004. This standard specifies security mechanisms for wireless networks, replacing the short Authentication and privacy clause of the original standard with a detailed Security clause. In the process, the amendment deprecated broken Wired Equivalent Privacy (WEP), while it was later incorporated into the published IEEE 802.11-2007 standard.

<span class="mw-page-title-main">One-time password</span> Password that can only be used once

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.

<span class="mw-page-title-main">Digest access authentication</span> Method of negotiating credentials between web server and browser

Digest access authentication is one of the agreed-upon methods a web server can use to negotiate credentials, such as username or password, with a user's web browser. This can be used to confirm the identity of a user before sending sensitive information, such as online banking transaction history. It applies a hash function to the username and password before sending them over the network. In contrast, basic access authentication uses the easily reversible Base64 encoding instead of hashing, making it non-secure unless used in conjunction with TLS.

In cryptography, CRAM-MD5 is a challenge–response authentication mechanism (CRAM) based on the HMAC-MD5 algorithm. As one of the mechanisms supported by the Simple Authentication and Security Layer (SASL), it is often used in email software as part of SMTP Authentication and for the authentication of POP and IMAP users, as well as in applications implementing LDAP, XMPP, BEEP, and other protocols.

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.

<span class="mw-page-title-main">Cryptographic nonce</span> Concept in cryptography

In cryptography, a nonce is an arbitrary number that can be used just once in a cryptographic communication. It is often a random or pseudo-random number issued in an authentication protocol to ensure that each communication session is unique, and therefore that old communications cannot be reused in replay attacks. Nonces can also be useful as initialization vectors and in cryptographic hash functions.

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.

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.

An oblivious pseudorandom function (OPRF) is a cryptographic function, similar to a keyed-hash function, but with the distinction that in an OPRF two parties cooperate to securely compute a pseudorandom function (PRF).

References

  1. ↑ Henk C.A. van Tilborg; Sushil Jajodia (8 July 2014). Encyclopedia of Cryptography and Security. Springer Science & Business Media. ISBN   978-1-4419-5906-5.
  2. ↑ Ahmed, Ibrahim H.; Hanna, Josiah P.; Fosong, Elliot; Albrecht, Stefano V. (2021). Advances in Practical Applications of Agents, Multi-Agent Systems, and Social Good. The PAAMS Collection. Lecture Notes in Computer Science. Vol. 12946. pp. 14–26. doi:10.1007/978-3-030-85739-4. ISBN   978-3-030-85738-7. S2CID   237611496.
  3. ↑ "Archived copy". www.cag.lcs.mit.edu. Archived from the original on 14 October 2004. Retrieved 19 October 2022.{{cite web}}: CS1 maint: archived copy as title (link)
  4. ↑ "Challenge-Response Authentication".
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.