A secret cryptographic key is stored in a protected state. While in the protected state, the secret cryptographic key is encrypted with a plurality of cryptographic keys, each of which is used to re-create the plaintext version of the secret cryptographic key. A service operated by an online service provider creates an isolated network environment containing a bastion computer system in communication with an HSM. After establishing the isolated network environment, the online service provider provides a service provider key to the HSM. An HSM key is present on the HSM, and an administrator key is provided by one or more key administrators. Using the HSM key, the service provider key, and the administrator key, the HSM performs cryptographic operations using the secret cryptographic key. When complete, the isolated network environment is deconstructed and the secret cryptographic key is returned to online storage in a protected state.