Challenge-response authentication
Encyclopedia
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
.
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.
Clearly an adversary that can eavesdrop on a password authentication can then authenticate itself in the same way. One solution is to issue multiple passwords, each of them marked with an identifier. The verifier can pick any of the identifiers, and the prover must have the correct password for that identifier. Assuming that the passwords are chosen independently, an adversary who intercepts one challenge-response message pair has no more chance of responding correctly to a different challenge than an adversary who has intercepted nothing.
For example, when other communications security
methods are unavailable, the U.S.
military uses the AKAC-1553 DRYAD
numeral cipher to authenticate and encrypt some communications. DRYAD 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.
Software in the 1980s and 1990s often used a similar method for copy protection
: challenges would be questions like "What is the second word in the third paragraph on page 418 of the manual?". The security assumption was that copying the manual was more difficult than copying the software disk.
s, for example, are a sort of variant on the Turing test
, meant to determine whether a viewer of a Web
application is a real person. The challenge sent to the viewer is a distorted image of some text, and the viewer responds by typing in that text. The distortion is designed to make automated optical character recognition
(OCR) difficult and preventing a computer program from passing as a human.
, 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 observe the password being entered. To address the insecure channel problem, a more sophisticated approach is necessary. Many cryptographic solutions involve two-way authentication, where both the user and the system must each convince the other that they know the shared secret
(the password), without this secret ever being transmitted in the clear
over the communication channel, where eavesdroppers might be lurking.
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. In other variations, a hash function operates on a password and a random challenge value to create a response value.
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 a 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 important not to use time-based nonces, as these can weaken servers in different time zones and servers with inaccurate clocks.
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.
where
-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 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.
Often, the hashed password is retrieved from the actual password together with a password salt. Then, the hash together with the salt are stored. This makes brute-force-attacking harder as the search space is enlarged by the salt.
s are zero-knowledge password proof
and key agreement systems (such as Secure Remote Password (SRP)
), CRAM-MD5
, and ssh
's challenge-response system based on RSA http://www.cag.lcs.mit.edu/~rugina/ssh-procedures/.
Computer security
Computer security is a branch of computer technology known as information security as applied to computers and networks. The objective of computer security includes protection of information and property from theft, corruption, or natural disaster, while allowing the information and property to...
, 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
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...
.
The simplest example of a challenge-response protocol is password
Password
A password is a secret word or string of characters that is used for authentication, to prove identity or gain access to a resource . The password should be kept secret from those not allowed access....
authentication, where the challenge is asking for the password and the valid response is the correct password.
Clearly an adversary that can eavesdrop on a password authentication can then authenticate itself in the same way. One solution is to issue multiple passwords, each of them marked with an identifier. The verifier can pick any of the identifiers, and the prover must have the correct password for that identifier. Assuming that the passwords are chosen independently, an adversary who intercepts one challenge-response message pair has no more chance of responding correctly to a different challenge than an adversary who has intercepted nothing.
For example, when other communications security
Communications security
Communications security is the discipline of preventing unauthorized interceptors from accessing telecommunications in an intelligible form, while still delivering content to the intended recipients. In the United States Department of Defense culture, it is often referred to by the abbreviation...
methods are unavailable, the U.S.
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
military uses the AKAC-1553 DRYAD
DRYAD
The DRYAD Numeral Cipher/Authentication System is a simple, paper cryptographic system currently in use by the U.S. military for authentication and for encryption of short, numerical messages. Every unit with a radio is given a set of DRYAD code sheets. A single sheet is valid for a limited time...
numeral cipher to authenticate and encrypt some communications. DRYAD 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.
Software in the 1980s and 1990s often used a similar method for copy protection
Copy protection
Copy protection, also known as content protection, copy obstruction, copy prevention and copy restriction, refer to techniques used for preventing the reproduction of software, films, music, and other media, usually for copyright reasons.- Terminology :Media corporations have always used the term...
: challenges would be questions like "What is the second word in the third paragraph on page 418 of the manual?". The security assumption was that copying the manual was more difficult than copying the software disk.
Other non-cryptographic protocols
Challenge-response protocols are also used to assert things other than knowledge of a secret value. CAPTCHACAPTCHA
A CAPTCHA is a type of challenge-response test used in computing as an attempt to ensure that the response is generated by a person. The process usually involves one computer asking a user to complete a simple test which the computer is able to generate and grade...
s, for example, are a sort of variant on the Turing test
Turing test
The Turing test is a test of a machine's ability to exhibit intelligent behaviour. In Turing's original illustrative example, a human judge engages in a natural language conversation with a human and a machine designed to generate performance indistinguishable from that of a human being. All...
, meant to determine whether a viewer of a Web
World Wide Web
The World Wide Web is a system of interlinked hypertext documents accessed via the Internet...
application is a real person. The challenge sent to the viewer is a distorted image of some text, and the viewer responds by typing in that text. The distortion is designed to make automated optical character recognition
Optical character recognition
Optical character recognition, usually abbreviated to OCR, is the mechanical or electronic translation of scanned images of handwritten, typewritten or printed text into machine-encoded text. It is widely used to convert books and documents into electronic files, to computerize a record-keeping...
(OCR) difficult and preventing a computer program from passing as a human.
Cryptographic techniques
Non-cryptographic authentication was generally adequate in the days before the InternetInternet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
, 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
Channel (communications)
In telecommunications and computer networking, a communication channel, or channel, refers either to a physical transmission medium such as a wire, or to a logical connection over a multiplexed medium such as a radio channel...
to observe the password being entered. To address the insecure channel problem, a more sophisticated approach is necessary. Many cryptographic solutions involve two-way authentication, where both the user and the system must each convince the other that they know the shared secret
Shared secret
In cryptography, a shared secret is a piece of data, known only to the parties involved, in a secure communication. The shared secret can be a password, a passphrase, a big number or an array of randomly chosen bytes....
(the password), without this secret ever being transmitted in the clear
In the Clear
In the Clear is an album released by the band Ivy on March 1, 2005 on Nettwerk.When starting sessions for In The Clear, the band tried to strike a balance between the immediacy of their early recordings and the careful sonic detailing of their more recent work...
over the communication channel, where eavesdroppers might be lurking.
One way this is done involves using the password as the encryption
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
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. In other variations, a hash function operates on a password and a random challenge value to create a response value.
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
Dictionary attack
In cryptanalysis and computer security, a dictionary attack is a technique for defeating a cipher or authentication mechanism by trying to determine its decryption key or passphrase by searching likely possibilities.-Technique:...
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
Replay attack
A replay attack is a form of network attack in which a 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 retransmits it, possibly as part of a masquerade attack by IP packet...
, 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
Cryptographic nonce
In security engineering, nonce is an arbitrary number used only once to sign a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused...
as the challenge to ensure that every challenge-response sequence is unique. This protects against a replay attack
Replay attack
A replay attack is a form of network attack in which a 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 retransmits it, possibly as part of a masquerade attack by IP packet...
. If it is impractical to implement a true nonce, a strong cryptographically secure pseudorandom number generator
Cryptographically secure pseudorandom number generator
A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...
and cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
can generate challenges that are highly unlikely to occur more than once. It is important not to use time-based nonces, as these can weaken servers in different time zones and servers with inaccurate clocks.
Mutual authentication
Mutual authentication
Mutual authentication or two-way authentication refers to two parties authenticating each other suitably. In technology terms, it refers to a client or user authenticating themselves to a server and that server authenticating itself to the user in such a way that both parties are assured of the...
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
Key derivation function
In cryptography, a key derivation function derives one or more secret keys from a secret value such as a master key or other known information such as a password or passphrase using a pseudo-random 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 generates unique challenge value cc
- Client computes cr = hash(cc + sc + secret)
- Client sends cr and cc to the server
- Server calculates the expected value of cr and ensures the client responded correctly
- Server computes sr = hash(sc + cc + secret)
- Server sends sr
- 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
Password storage
To avoid storage of passwords, some operating systems (e.g. UnixUnix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
-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 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.
Often, the hashed password is retrieved from the actual password together with a password salt. Then, the hash together with the salt are stored. This makes brute-force-attacking harder as the search space is enlarged by the salt.
Examples
Examples of more sophisticated challenge-response algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s are zero-knowledge password proof
Zero-knowledge password proof
In cryptography, a zero-knowledge password proof is an interactive method for one party to prove to another party that it knows a value of a password, without revealing anything other than the fact that it knows that password to the verifier...
and key agreement systems (such as Secure Remote Password (SRP)
Secure remote password protocol
The Secure Remote Password protocol is a password-authenticated key agreement protocol.- Overview :The SRP protocol has a number of desirable properties: it allows a user to authenticate themselves to a server, it is resistant to dictionary attacks mounted by an eavesdropper, and it does not...
), CRAM-MD5
CRAM-MD5
In cryptography, CRAM-MD5 is achallenge-response authentication mechanism defined in RFC 2195 based on theHMAC-MD5 MACalgorithm...
, and ssh
Secure Shell
Secure Shell is a network protocol for secure data communication, remote shell services or command execution and other secure network services between two networked computers that it connects via a secure channel over an insecure network: a server and a client...
's challenge-response system based on RSA http://www.cag.lcs.mit.edu/~rugina/ssh-procedures/.
See also
- Challenge-handshake authentication protocolChallenge-handshake authentication protocolIn computing, the Challenge-Handshake Authentication Protocol authenticates a user or network host to an authenticating entity. That entity may be, for example, an Internet service provider. CHAP is specified in RFC 1994....
- CRAM-MD5CRAM-MD5In cryptography, CRAM-MD5 is achallenge-response authentication mechanism defined in RFC 2195 based on theHMAC-MD5 MACalgorithm...
- Cryptographic hash functionCryptographic hash functionA cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
- Cryptographic nonceCryptographic nonceIn security engineering, nonce is an arbitrary number used only once to sign a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused...
- Kerberos
- Otway-Rees
- Needham-Schroeder
- Wide Mouth Frog
- Password-authenticated key agreementPassword-authenticated key agreementIn cryptography, a password-authenticated key agreement method is an interactive method for two or more parties to establish cryptographic keys based on one or more party's knowledge of a password.-Types:...
- CAPTCHACAPTCHAA CAPTCHA is a type of challenge-response test used in computing as an attempt to ensure that the response is generated by a person. The process usually involves one computer asking a user to complete a simple test which the computer is able to generate and grade...
- reCAPTCHAReCAPTCHAreCAPTCHA is a system originally developed at Carnegie Mellon University's main Pittsburgh campus. It uses CAPTCHA to help digitize the text of books while protecting websites from bots attempting to access restricted areas. On September 16, 2009, Google acquired reCAPTCHA. reCAPTCHA is currently...
- Distance-bounding protocolDistance-bounding protocolDistance bounding protocols are cryptographic protocols that enable a verifier V to establish an upper bound on the physical distance to a prover P. They are based on timing the delay between sending out a challenge bits and receiving back the corresponding response bits...
- Reflection attackReflection attackA reflection attack is a method of attacking a challenge-response authentication system that uses the same protocol in both directions. That is, the same challenge-response protocol is used by each side to authenticate the other side...
- Replay attackReplay attackA replay attack is a form of network attack in which a 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 retransmits it, possibly as part of a masquerade attack by IP packet...
- Man-in-the-middle attackMan-in-the-middle attackIn cryptography, the man-in-the-middle attack , bucket-brigade attack, or sometimes Janus attack, is a form of active eavesdropping in which the attacker makes independent connections with the victims and relays messages between them, making them believe that they are talking directly to each other...
- Physically unclonable functionPhysically Unclonable FunctionIn practical cryptography, a Physical Unclonable Function or PUF is a function that is embodied in a physical structure and is easy to evaluate but hard to predict. Further, an individual PUF device must be easy to make but practically impossible to duplicate, even given the exact manufacturing...