View source for Challenge–response authentication

{{short description|Type of authentication protocol}}
{{One source|date=February 2019}}
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 [[authentication|authenticated]].<ref name="TilborgJajodia2014">{{cite book|author1=Henk C.A. van Tilborg|author2=Sushil Jajodia|title=Encyclopedia of Cryptography and Security|url=https://books.google.com/books?id=UGyUUK9LUhUC&q=%22Challenge%E2%80%93response+authentication%22|date=8 July 2014|publisher=Springer Science & Business Media|isbn=978-1-4419-5906-5}}</ref>

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 (cryptography)|adversary]] who can [[Network eavesdropping|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 [[United States Armed Forces|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. [[Alice and Bob|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. [[CAPTCHA]]s, for example, are meant to allow websites and applications to determine whether an interaction was performed by a genuine user rather than a [[Web scraping|web scraper]] or [[Internet bot|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 [[Channel (communications)|communication channel]]. To address the [[Secure channel|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 [[Plaintext|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 (protocol)|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.<ref>{{cite book |last1=Ahmed |first1=Ibrahim H. |last2=Hanna |first2=Josiah P. |last3=Fosong |first3=Elliot |last4=Albrecht |first4=Stefano V. |title=Advances in Practical Applications of Agents, Multi-Agent Systems, and Social Good. The PAAMS Collection |series=Lecture Notes in Computer Science |date=2021 |volume=12946 |issue=19 |pages=14–26 |doi=10.1007/978-3-030-85739-4|isbn=978-3-030-85738-7 |s2cid=237611496 }}</ref>

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==
*Server sends a unique challenge value '''''sc''''' to the client
*Client sends a unique challenge value '''''cc''''' to the server
*Server computes '''''sr''''' = hash('''cc''' + secret) and sends to the client
*Client computes '''''cr''''' = hash('''sc''' + secret) and sends to the server
*Server calculates the expected value of '''''cr''''' and ensures the client responded correctly
*Client calculates the expected value of '''''sr''''' and ensures the server responded correctly
where
*'''''sc''''' is the server-generated challenge
*'''''cc''''' is the client-generated challenge
*'''''cr''''' is the client response
*'''''sr''''' is the server response
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 [[password#Form of stored passwords|hash of the password]] rather than storing the password itself. During authentication, the system needs 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, [[pass the hash|an intruder can use the actual hash]], rather than the password, which makes the stored hashes just as sensitive as the actual passwords. [[Salted Challenge Response Authentication Mechanism|SCRAM]] is a challenge–response algorithm that avoids this problem.

==Examples==
Examples of more sophisticated challenge–response [[algorithm]]s are:
* [[Zero-knowledge password proof]] and key agreement systems (such as [[Secure remote password protocol|Secure Remote Password (SRP)]])
* [[Challenge-Handshake Authentication Protocol]] (CHAP) ({{IETF RFC|1994}})
* [[CRAM-MD5]], OCRA: OATH Challenge–Response Algorithm ({{IETF RFC|6287}})
* [[Salted Challenge Response Authentication Mechanism]] (SCRAM) ({{IETF RFC|5802}})
* [[Secure Shell|ssh]]'s challenge–response system based on [[RSA (algorithm)|RSA]].<ref>{{cite web |url=http://www.cag.lcs.mit.edu/~rugina/ssh-procedures/ |title=Archived copy |website=www.cag.lcs.mit.edu |access-date=19 October 2022 |archive-url=https://web.archive.org/web/20041014002830/http://www.cag.lcs.mit.edu/~rugina/ssh-procedures/ |archive-date=14 October 2004 |url-status=dead}}</ref>

Some people consider a [[CAPTCHA]] a kind of challenge–response authentication that blocks [[spambot]]s.<ref>
[http://www.techopedia.com/definition/26138/challenge-response-authentication "Challenge–Response Authentication"].
</ref>

==See also==
{{Wikibooks|Internet Technologies/Email spam}}
*[[Challenge-Handshake Authentication Protocol]]
*[[Challenge–response spam filtering]]
*[[Countersign (military)]]
*[[CRAM-MD5]]
*[[Cryptographic hash function]]
*[[Cryptographic nonce]]
*[[Distance-bounding protocol]]
*[[Kerberos (protocol)]]
*[[Man-in-the-middle attack]]
*[[Needham–Schroeder protocol]]
*[[Otway–Rees protocol]]
*[[Password-authenticated key agreement]]
*[[Reflection attack]]
*[[Replay attack]]
*[[Salted Challenge Response Authentication Mechanism]] (SCRAM)
*[[SQRL]]
*[[WebAuthn]]
*[[Wide Mouth Frog protocol]]

==References==
{{Reflist}}

{{DEFAULTSORT:Challenge-response authentication}}
[[Category:Authentication methods]]
[[Category:Computer access control]]