In one embodiment, a data storage client may establish a virtual replay protected storage system with an agnostic data storage. The virtual replay protected storage system may maintain a trusted counter and a secret key in a trusted client environment. The virtual replay protected storage system may encode a hash message authentication code signature based on the trusted counter, the secret key, and a data set. The virtual replay protected storage system may send a write request of the data set with the hash message authentication code signature to an agnostic data storage.