Challenge-response protocol

From Citizendium
Revision as of 20:26, 20 August 2010 by imported>Sandy Harris
Jump to navigation Jump to search
This article is a stub and thus not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

A challenge-response protocol is a technique for managing source authentication.

As a simple example, consider a user who wants to log in to a computer system. If he sends the actual password, or a hash of it, over the wire, then a wiretapper can get it. Moreover, if an attacker can obtain a list of encrypted passwords from the target system, either by reading it from an account on the system or by intercepting them on the wire, then he can conduct a dictionary attack and break into any account whose password is in the dictionary.

In a challenge-response protocol, the interaction might go like this instead:

  1. the user requests a connection
  2. the system generates a random challenge C, using a strong random number generator
  3. the system sends C to the user
  4. the user encrypts C with a block cipher, using the hash of his password as key, to generate the response R
  5. the user sends R back to the system
  6. the system decrypts R, using the stored hash of the user password as key
  7. if the result is C, the connection is allowed

There are many variations. The example uses a block cipher, but it can also be done with public key techniques — the user encrypts with his private key in step 4 and the system verifies with the public key in step 6. A hash can also be used — step 4 is then to hash some combination of data that includes the challenge and the hashed password to get R, and step 6 is to hash the same data and compare the result to R.

In any case, the actual password is never transmitted. An eavesdropper can see C and R each time, but that does him little good. Next time a different challenge will be used and a different response required. If the cryptography used is sound, then even with a large collection of challenge/response pairs, it should be very difficult for him to discover anything about the password.

The challenge must be large enough to prevent a birthday attack. With a challenge of 2n bits, an attacker who logs the data from 2n/2 interactions has a significant chance of seeing a repeated challenge.