A method of rotating cryptographic keys used by a client device to cryptographically authenticate itself to a service or application of a server, the method comprising: storing, by the server, a set of cryptographic keys associated with the client device that includes: a bootstrap cryptographic key for initially authenticating the client device to the server, a currently active cryptographic key used to authenticate the client device to the service or application of the server, and a cryptographic key for replacing the currently active cryptographic key; receiving, at the server, an authentication request from the client device that includes: a client-indicated bootstrap key, a client-indicated authentication key, and a client-indicated cryptographic key for replacing the currently active cryptographic key for authenticating the client device; making, by the server, a determination that the client device is authenticated based in part on whether there is a match between the client-indicated authentication key and either the server-stored currently active cryptographic key or the server-stored cryptographic key for replacing the currently active cryptographic key for authenticating the client device; setting, by the server, the server-stored currently active cryptographic key for authenticating the client device to the client-indicated cryptographic key for replacing the currently active cryptographic key for authenticating the client device, when the client-indicated authentication key matches the server-stored cryptographic key for replacing the currently active cryptographic key for authenticating the client device; and providing, by the server and based on the determination, an authentication response to the client indicating that the client has been authenticated, wherein the client device sets its client-indicated authentication key to the client-indicated cryptographic key for replacing the currently active cryptographic key for authenticating the client device, in response to the authentication response. storing, by the server, a set of cryptographic keys associated with the client device that includes: a bootstrap cryptographic key for initially authenticating the client device to the server, a currently active cryptographic key used to authenticate the client device to the service or application of the server, and a cryptographic key for replacing the currently active cryptographic key; receiving, at the server, an authentication request from the client device that includes: a client-indicated bootstrap key, a client-indicated authentication key, and a client-indicated cryptographic key for replacing the currently active cryptographic key for authenticating the client device; a bootstrap cryptographic key for initially authenticating the client device to the server, a currently active cryptographic key used to authenticate the client device to the service or application of the server, and a cryptographic key for replacing the currently active cryptographic key; receiving, at the server, an authentication request from the client device that includes: a client-indicated bootstrap key, a client-indicated authentication key, and a client-indicated cryptographic key for replacing the currently active cryptographic key for authenticating the client device; a client-indicated bootstrap key, a client-indicated authentication key, and a client-indicated cryptographic key for replacing the currently active cryptographic key for authenticating the client device; making, by the server, a determination that the client device is authenticated based in part on whether there is a match between the client-indicated authentication key and either the server-stored currently active cryptographic key or the server-stored cryptographic key for replacing the currently active cryptographic key for authenticating the client device; setting, by the server, the server-stored currently active cryptographic key for authenticating the client device to the client-indicated cryptographic key for replacing the currently active cryptographic key for authenticating the client device, when the client-indicated authentication key matches the server-stored cryptographic key for replacing the currently active cryptographic key for authenticating the client device; and providing, by the server and based on the determination, an authentication response to the client indicating that the client has been authenticated, wherein the client device sets its client-indicated authentication key to the client-indicated cryptographic key for replacing the currently active cryptographic key for authenticating the client device, in response to the authentication response.