If a client/server application uses a challenge/response pattern for authentication, e.g. SCRAM or alike, it often involves the usage of nonces (client nonce and server nonce) for preventing replay attacks.
The server will generate a server nonce, based on a secure random generated number concatenated with the client nonce. Supposing that the server stores the most recent received client nonce, and issued server nonce, to guarantee that "older" or "invalid" nonces will not be accepted, this would open an attack vector.
An attacker could brute-force request challenges to userid's that he guesses, in order to override the valid and agreed client/server nonce with a new value, that the actual client doesn't know. If this happens in between the actual client's challenge and response, the server will deny access as the nonce will not be valid anymore. Which would be some kind of Denial Of Service attack.
If the server decides to only update the actually valid server/client nonce in storage only if the challenge/response was successfully executed as a whole, it would need to decline challenge requests for users that have not responded to the most recent challenge. This would also open an an attack window. The attack could request challenges to (guessed) users in order to prevent them from requesting a challenge in the first place.
Assuming that the server will keep track of a list of unused nonces, both attacks would be prevented, but this opens another vector for the attacker to request huge amount of challenges, leading the server to store all of those nonces in storage. Provoking I/O load and potentially leading to DoS again.
Anyhow I am currently not understanding how to securely implement nonce handling on the server-side to prevent those DoS attacks. Currently I have the feeling that one trades the protection against replay attacks in favour of DoS.
I know that there are other means to prevent this, via request throttling on firewalls etc, but I'd like to solve this problem on the challenge/response implementation level if possible. Thanks for ideas and answers.