Approaches described herein allow a stateless device to recover at least one private key. In particular, a stateless device can provide service-account credentials to a directory service to establish a first session and acquire a certificate and private key using information associated with the stateless device. The stateless device can store its private key before the first session ends. A stateless device can then provide user-account credentials to the directory service to establish a second session. After the second session begins, a private key can be acquired by the stateless device.