RFC 4226, section 7.5 defines two shared key generation schemes: deterministic and random. I would suggest that you use the deterministic scheme, which only requires the server to store a single "master key":
"Deterministic Generation
A possible strategy is to derive the shared secrets from a master
secret. The master secret will be stored at the server only. A
tamper-resistant device MUST be used to store the master key and
derive the shared secrets from the master key and some public
information. The main benefit would be to avoid the exposure of the
shared secrets at any time and also avoid specific requirements on
storage, since the shared secrets could be generated on-demand when
needed at provisioning and validation time."
Addendum: To also avoid storing a separate counter value for each client, you could still use a shared counter for all clients as you suggest, at least as long as the intended purpose of the server is such that it's unlikely for more than one legitimate client to attempt to authenticate simultaneously.
However, simply sending a counter value to the client and having the client reply with the corresponding one-time password could allow an attacker masquerading as the server to send an artificially high counter value to the client and store the response for later use. (If the client enforces the monotonicity of counter values, this could also render the client temporarily unable to authenticate until the server's counter catches up with the bogus counter value sent by the attacker.)
One way to avoid this attack, and eliminate the extra round-trip to request the counter, would be to use a timestamp as the counter, something like this:
When the user want to authenticate, the server sends to the server the current timestamp $T$, its client ID $i$ and the one-time password $P = HOTP(K_i,T)$, where $K_i$ is the client's HOTP key.
On receiving an authentication request $(T,i,P)$, the server checks that:
- $i$ is a valid and non-revoked client ID;
- $T$ is a valid timestamp, and is not too far in the past or the future;
- $T$ is greater than the timestamp $T'$ for the previous successful authentication; and
- $P = HOTP(K_i,T)$, where $K_i$ is the client key derived from the client ID $i$ and the master key $MK$.
If all these checks pass, the client is allowed access.
Thus, the server only needs to store the master key $MK$, the last successful authentication timestamp $T'$, and possibly list of revoked client IDs. (This ability to revoke access for compromised clients is one of the main advantages of not sharing keys between clients.)
The valid time window allows for some degree of clock skew between the clients and the server, and should be set to reflect a balance between that and security requirement.
An attacker intercepting the authentication request in this protocol can't really do much: if they pass the request on to the server, the password they just captured becomes useless (and if the client and server encrypt any further communications with their shared secret $K_i$, the attacker can't even eavesdrop on it); if they don't, the client will know something went wrong, and in any case the password will still expire after the limited time window passes (and possibly sooner, if the client tries to reauthenticate and succeeds).
(Obviously, the protocol also needs to protect against brute force attacks, either by implementing request rate throttling as recommended in the HOTP spec, and/or by making the password long enough. Indeed, if the password need not be human-enterable, one could just as well — and, indeed, preferably — use the full non-truncated HMAC output as the one-time password.)
