Challenge-response authentication
|
|
In computer security, challenge-response authentication relies on the possession of a secret of some sort to perform authentication. A very simple example is asking for a password, where the challenge is asking for the password, and the adequate response is the correct password. This was 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 observe the password being entered.
These days, a more sophisticated approach is necessary involving 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. The 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.
Note that the exchange itself does not supply enough information to allow an eavesdropper to deduce what the password is (but see dictionary 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.
It is important to note that there is a fundamental conflict between challenge-response authentication and the hashed storage of passwords commonly used on Unix-type operating systems: the latter tries to avoid the storage of the authentication secret (the password) in any easily-decodable form on the server, but challenge-response authentication precisely requires the server to be able to easily determine what the secret is, otherwise it could not convince the client that it knows what it is. The usual consequence of this is that the secret becomes the hashed version of the password (the client performing the hashing before proceeding to do challenge-response with the result); but then, it becomes every bit as essential to protect the secrecy of this hashed version as it is to protect that of the original password.
Examples of sophisticated challenge-response algorithms are Secure Remote Password (SRP), CRAM-MD5, and ssh's challenge-response system based on RSA [1] (http://www.cag.lcs.mit.edu/~rugina/ssh-procedures/).