1. A computer-implemented method, comprising: receiving a request to perform an operation, the performance of which involves an encryption operation using a first cryptographic key specified in the request; causing a device to perform the encryption operation using the first cryptographic key; obtaining a stochastically-generated value; and based at least in part on the stochastically-generated value satisfying a set of key rotation criteria, causing the first cryptographic key to be replaced with a second cryptographic key, the set of key rotation criteria having a probability of being satisfied that is associated with a frequency of key rotation.