How does asymmetric Challenge-Response improve on the symmetric version, and what new requirements does it introduce?
The client signs the challenge with its private key — Sig = K_priv,A(RAND) — and the server verifies with the public key. The server stores no secret, but the public key's authenticity must be guaranteed (requiring a PKI), RAND must come from a good (P)RNG, and man-in-the-middle remains a risk.
* Symmetric vs asymmetric C-R: no stored secret, but needs a PKI. *
* Man-in-the-middle interposed on the channel. — Miraceti, CC BY-SA 3.0, via Wikimedia Commons. *
The flow (asymmetric):
- Precondition: the server knows Alice's public key k_pub,A
- Client sends ID_Alice
- Server checks the ID is in its database, generates RAND
- Server sends RAND
- Client computes Sig = K_priv,A(RAND) and returns it
- Server verifies with the public key:
K_pub,A(K_priv,A(RAND)) == RAND
The big advantage: no secret key needs to be stored on the server side — only public keys. This eliminates the symmetric system's worst liability (a database of everyone's secrets that, if breached, compromises all clients).
The new requirements / attack surface:
- Public-key authenticity must be guaranteed → you need a PKI (Public Key Infrastructure) — otherwise an attacker substitutes their own public key
- RAND must be generated with a proper PRNG/TRNG — a predictable challenge breaks the scheme
- Man-in-the-middle: a third party masquerades as the server (a typical WLAN attack)
Tip: Symmetric C-R: fast but the server holds dangerous secrets. Asymmetric C-R: server holds no secrets, but you've now signed up for the hard problem of distributing authentic public keys (PKI).
Go deeper:
Public-key cryptography (Wikipedia) — signing a challenge with a private key, and why "is this public key authentic?" forces a PKI.