When theft protection of a computing device is initiated, credentials of the user are provided to one or more services that verify the credentials and generate a recovery key. A data value is generated based on the recovery key and an identifier of the computing device (e.g., by applying a cryptographic hash function to the recovery key and the computing device identifier), and the data value is provided to the computing device, which stores the data value at the computing device. When a user is prompted to prove his or her ownership of the device, the owner can prove his or her ownership of the device in different manners by accessing the one or more services via a network (e.g., the Internet), or by providing the recovery key (e.g., obtained using another computing device) to the computing device.