In essence, authentication is an appeal to a shared secret to prove that you are one of the secret sharers. In terms of physical locks and keys, this is relatively straightforward: Only if you have the key, can you open the lock. Thus, anyone who has opened the lock must have the key. Designing communication protocols for authentication, however, requires subtlety, due to the difficulty in proving you know a secret without disclosing the secret itself.

A good example of how not to do this is given by early central locking systems for cars. There are two components: the verifier in the car, and a keyfob, which share a radio signal password. On triggering the keyfob, it will transmit this radio signal to the car, which checks to see if it corresponds to its stored password; if so, the car unlocks.

Unfortunately, anyone with the ability to monitor radio signals can listen in for the password; they can then unlock the car by replaying the signal. This scenario also demonstrates how cryptography is not the same as security: suppose we tried to secure this system by encrypting the password P. Then we obtain a ciphertext, M say, which is to be transmitted by the keyfob to the verifier, where it is decrypted, and, if the result is P, the car unlocks. Our man with the radio scanner can still harvest the signal M, and this suffices as, even though the intruder is oblivious to P, the response of the car to a signal of M is to unlock.

A traditional lock and key presents a problem (the lock) which requires a solution (the key). However, in the system above the verifier and keyfob are not analogous to the lock and key, and so the vulnerability arises. Whilst the verifier (the lock) presents a problem, its solution (the key) is not the keyfob, but the appropriate radio signal. Thus the keyfob's transmission of this signal is equivalent to leaving your car keys on the roof of the car; that is, making the solution publically available.

To resolve this we introduce a challenge-response system. Here the verifier is active rather than passive; it generates fresh problems that can only be solved by a secret sharer. We can abstract and formalise the system as follows. Let V (the verifier) and A (Alice) be the participants, and let Kva be a secret key known only to them. A message written as M will be assumed to be clear to all, whilst {M}K will indicate a message M encrypted with key K - only holders of key K can retrieve M itself from this signal, although note for later that any intruder still has access to the signal {M}K (be it a radio signal, network data packet or so on). Finally, we require the notion of a nonce N - a number used once, or randomly generated signal. Then the challenge response system works as follows

Challenge-response authentication
V → A: Nv
A → V: {Nv}Kva

That is, the verifier broadcasts a challenge Nv which anyone can receive; but only someone holding the shared secret Kva (in this case, only Alice) can respond with Nv encrypted by that key. Thus on receiving such a response, the verifier knows Alice is present. An eavesdropper can collect as many {N}Kva as they like to no avail- since none of those N will be used again, they will never be a valid response.

This of course assumes genuinely fresh nonces1 for each challenge; moreover, we require an unpredictable nonce, or a vulnerability exists as follows. Suppose an intruder I can tell what the next nonce will be, Nnext say. Then the following sequence will allow I to authenticate as A:

Replay Attack
I sends a challenge to A, pretending to be V (written I(V))

I(V) → A: Nnext
A → I(V): {Nnext}Kva

I returns to V and, impersonating A, triggers a challenge, which will be Nnext

V→ I(A): Nnext
I(V) → V: (Nnext}Kva

Now the verifier has received the correct response to its challenge, and thus assumes the respondent to be Alice when it is in fact the intruder; i.e., a central locking system exploited in this way would unlock for someone other than the keyfob holder. Note that I still has no knowledge of Kva, nor any need for it, underlining that the cryptography employed can be secure as you like yet the system as a whole can still be insecure.

Nonetheless, with secure crypto based on a secret shared key and unpredictable unrepeated challenges, the challenge-response system is a secure means for A to authenticate herself to V. There is an obvious limitation, that of the need for a shared secret. For central locking this can be manufactured into the car and keyfob; in effect, buying the car establishes the key. Designing communication protocols for key establishment is harder, since without such prior arrangements you need to somehow secure an insecure channel by communicating over that channel. Less obvious is the problem that challenge-response does not generalise to mutual authentication: that is, authenticating V to A as well as A to V. Again, prior arrangement (buying the car) means that one-way verification suffices for the central locking system: the locking system authenticates to Alice by virtue of being in her car! But for situations such as online shopping (where both vendor and purchaser need to be able to trust the other) or more dramatic examples such as friend-or-foe systems, it turns out that running challenge-response in both directions is flawed.

Reference: Formal analysis of Cryptographic Protocols Taught Postgraduate course, Laboratory for Foundations of Computer Science, University of Edinburgh.
1Quit sniggering at the back, Britnoders!