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, storing a first cryptographic key in each of a plurality of security modules; receiving a request to perform an operation, the performance of which involves an encryption operation using the first cryptographic key specified in the request; and as a result of receiving the request: causing a selected security module from the plurality of security modules to perform the encryption operation using the first cryptographic key; performing a stochastic process to generate a value; and when the value satisfies a set of key rotation criteria that limit the probability of using the same nonce multiple times with the first cryptographic key, causing each security module of the plurality of security modules to replace the first cryptographic key with a second cryptographic key.