Computing devices utilizing trusted execution environments as virtual smart cards are designed to support expected credential recovery operations when a user credential, e.g., personal identification number (PIN), password, etc. has been forgotten or is unknown. A computing device generates a cryptographic key that is protected with a PIN unlock key (PUK) provided by an administrative entity. If the user PIN cannot be input to the computing device the PUK can be input to unlock the locked cryptographic key and thereby provide access to protected data. A computing device can also, or alternatively, generate a group of challenges and formulate responses thereto. The formulated responses are each used to secure a computing device cryptographic key. If the user PIN cannot be input to the computing device an entity may request a challenge. The computing device issues a challenge from the set of generated challenges. Upon receiving a valid response back, the computing device can unlock the secured computing device cryptographic key associated with the issued challenge and subsequently provide access to protected data.