Aspects of the subject matter described herein relate to disclosing recovery keys. In aspects, when a recovery key is disclosed, data is updated to indicate that the recovery key has been disclosed. A machine that has locked data may determine whether a recovery key for the locked data has been disclosed and whether a new key needs to be generated for the locked data. If a new key needs to be generated for the locked data, the machine may generate the new key and send it to a recovery store for storage. In addition, old keys that protect the locked data may be deleted after the new key has been generated and stored.