Suppose that 2 people have a keyed hash algorithm (that is, a MAC) with a key that they both know. How could they implement challenge-response using their keyed hash algorithm? This confuses me...
It's pretty straightforward.
Let's say, this transaction is happening between Alice (an entity wishing to be verified) and Bob (an entity verifying Alice's identity). They both are in possession of a common secret key and are aware of the algorithm to use for authentication.
Step 1: Bob sends Alice a random string, the challenge. The challenge should be randonly generated for every challenge-response transaction.
Step 2: Alice generates the HMAC of the challenge by running HMAC(key,challenge) and sends the generated the HMAC to Bob, the response.
Step 3: Bob independently generates an HMAC for the challenge by running HMAC(key,challenge). The Alice's response matches Bob's generated HMAC, that proves that Alice is in possession of the right key and hence can be authenticated.