1. A computer-implemented method for managing cryptographic keys in a distributed system, comprising: under the control of one or more computer systems configured with executable instructions, receiving a request to perform an operation, the performance of which involves an encryption operation using a first cryptographic key specified in the request; and as a result of receiving the request: causing a device to perform the encryption operation using the first cryptographic key; obtaining a stochastically-generated value; and as a result of the stochastically-generated value satisfying a set of key rotation criteria, causing the first cryptographic key to be replaced with a second cryptographic key.