An encryption key not accessible outside a data storage device can be used to encrypt data stored in that device. The received data may have been encrypted under an external key, such as a key associated with a customer of a data storage service. Upon receiving the data encrypted under the external key, the data can be decrypted using a copy of the external key and then re-encrypted, inside the data storage device, using the internal key. If the external key is to be rotated, the stored data does not need to be modified as the data can be decrypted using the internal key and then re-encrypted using the new external key in response to an authorized request for the data after the change to the new external key. Such an approach provides near instant key rotation while not having to re-encrypt data under the new key unless requested.