Various methods and systems for protecting against chosen plaintext attacks when encrypting data for storage on an untrusted storage system are disclosed. One method involves generating an encryption key for use in encrypting data and generating an identifier for the data. Generation of the encryption key is based upon a hash of the data to be encrypted. The method also involves detecting whether an encrypted copy of the data is already stored by a storage system, based upon the identifier. The method also modifies the data to be encrypted or the encryption key, based upon a client-specific value, prior to generating the identifier.