In one implementation, a media stream is recorded using one or more keys. The one or more keys are also encrypted. The one or more encrypted keys may be stored with the encrypted media session at a cloud storage service. A network device receives a request to record a media stream and accesses at least one stream key for the media stream. The stream key is for encrypting the media stream. The network device encrypts the stream key with a master key. The encrypted stream key is stored in association with the encrypted media stream.