An authentication process for an endpoint device uses a pair of tokens. Tokens are generated at an authentication server that maintains a data store of token states, where the states are defined to include a “normal” state sequence along which a token is expected to advance. The endpoint device can store a token pair in non-volatile local storage. To authenticate, the endpoint device can provide its stored token pair to the authentication server, which can determine whether authentication succeeds based on the states of the tokens in the token pair. After successful authentication, the authentication server can provide a new token pair to the endpoint device and advance the token states along the normal sequence. When the endpoint device confirms receipt of the new token pair, which replaces the previous token pair, the authentication server can advance the state of the tokens again.