Techniques are provided for authenticating a user using shared secret updates. One method comprises, in response to a first authentication of a client using a given shared secret, updating, by the server, the given shared secret using information from the first authentication as part of a secret update protocol to generate an updated shared secret; and evaluating a second authentication using the updated shared secret. An anomaly may be detected when the client attempts the second authentication using a shared secret and the server determines that the shared secret was previously used for an authentication. The server may detect a breach of shared secrets of multiple users by monitoring a number of the detected anomalies across a user population and initiate a predefined recovery flow depending upon a number of impacted users.