Some embodiments provide a method for recovering user data for a device. To initiate recovery, the method sends to a first server a first request including at least (i) a device identifier and (ii) a first set of cryptographic data for a second set of servers with which the first server communicates. If the first server verifies the device identifier with an attestation authority, the method receives from the second set of servers a second set of cryptographic data generated by the second set of servers. After receiving input of a device passcode for the device, the method sends to the first server a second request comprising at least a third set of cryptographic data for the second set of servers generated based on the device passcode. If the first server verifies the device passcode with the second set of servers, the method receives access to the user data.