How does symmetric Challenge-Response authentication work, and what are its security drawbacks?

The server stores a reference key for the client, sends a random RAND, the client encrypts it C = Enc(RAND, K) and returns it; the server checks Enc(RAND, K_ref) == C. Drawbacks: RAND and C travel over an insecure channel (enabling known-plaintext and dictionary attacks), and the server must store every client's secret key long-term.

* Symmetric challenge-response; the server stores every client's secret. *

The flow (symmetric):

1. The client sends its ID ("I am Alice")
2. The server looks up Alice's key; if found, generates a random RAND
3. The server sends RAND as the challenge
4. The client computes the response C = Enc(RAND, K_Alice) and returns it
5. The server checks Enc(RAND, K_ref) == C

(A MAC can be used instead of encryption.) Used in GSM/UMTS, WLAN, PIN/TAN home banking, transponder/key systems.

The security drawbacks:

• Both RAND and the response travel over an insecure channel (the air interface!) → an attacker can try to derive the key from RAND and C — this known-plaintext attack has been successfully demonstrated against GSM (Ekdahl, Johansson)
• Dictionary attack: the attacker overhears RAND, computes responses for guessed keys, compares to Alice's response → defense: encrypt the challenge, or use zero-knowledge methods
• Long-term secret storage: the server (Bob) must store every client's secret key, securely, for a long time — one of the biggest real-world security headaches → solution: asymmetric methods

Go deeper:

• Challenge–response authentication (Wikipedia) — the nonce + keyed-response pattern that GSM, WLAN and PIN/TAN banking all instantiate.