Application servers are programmed such that when an application server changes a compromised service key, the compromised key is saved by the application server until all tickets that may have been issued under the compromised key expire. Whenever the application server receives a ticket from a client issued under the compromised key, it generates an authenticator for an error message using the session key extracted from the ticket and sends the error message with this authenticator to the client. Clients are programmed to be able to receive error messages from application servers that have changed their service keys. Because the error messages include an authenticator generated by the application server using the session key extracted from the compromised ticket, the client is able to rely on the error message. The client is able to automatically request a new ticket from a key distribution center in response to a successful authentication of the error message.