A key management service creates a key upon user request. The key management service receives a request for a first cryptographic operation. The key management service performs the first cryptographic operation. The key management service returns results of the first cryptographic operation to a dependent service. The key management service receives a notification of key rotation. The key management service receives a request for a second cryptographic operation. The key management service performs the second cryptographic operation. The key management service returns results of the second cryptographic operation to the dependent service. The key management service returns updated key metadata to the dependent service.