A method and system for performing authentication for a backup service provided by a server is provided. The method receives a request for authentication from a client device, the request for authentication including a signature generated using a private key. The method sends a request to obtain a public key corresponding to the private key to the server and receives the public key from the server, the public key being retrieved by the server from a backup of a virtual machine. The method verifies the signature using the public key and generates a token encrypted using the public key, the token enabling the client device to access the server for the backup service. The method sends the token to the client device, the token to be decrypted using the private key by the client device.