Challenge-response protocol: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Sandy Harris
No edit summary
imported>Sandy Harris
No edit summary
Line 13: Line 13:
# if the result is C, the connection is allowed
# 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 (cryptography)|hash]] can also be used — steps 4 and 6 are then identical, hashing some combination of data that includes the challenge and the hashed password.
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 (cryptography)|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.  
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 2<sup>n</sup> bits, an attacker who logs the data from 2<sup>n/2</sup> interactions has a significant chance of seeing a repeated challenge.
The challenge must be large enough to prevent a [[birthday attack]]. With a challenge of 2<sup>n</sup> bits, an attacker who logs the data from 2<sup>n/2</sup> interactions has a significant chance of seeing a repeated challenge.

Revision as of 07:35, 26 July 2010

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 the list of encrypted passwords from the target system, 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.