Distribution and recovery of a user secret

Patent metadata

Field	Value
Publication number	US-11057210-B1
Application number	US-201916550836-A
Country	US
Kind code	B1
Filing date	Aug 26, 2019
Priority date	Sep 30, 2015
Publication date	Jul 6, 2021
Grant date	Jul 6, 2021

Abstract

A user device can segment a secret (e.g., a data recovery key) into a master segment and a shared segment such that possession of both segments is necessary and sufficient to reconstruct the secret. The user device can provide the master segment to a server system. The user device can further segment the shared segment to generate a set of M shares such that any subset of the shares that includes at least a threshold number t of the shares can be used to reconstruct the shared segment, while fewer than t shares provide no information about the shared segment. The M shares can be distributed to shareholder devices. To reconstruct the secret, a recovery device can obtain the master segment and at least t of the M shares, then reconstruct the secret.

First claim

What is claimed is:

1. A method comprising:
generating, at a user device, a secret, wherein the secret is a cryptographic key used by the user device to encrypt user data;
identifying, at the user device, a set of M shareholder devices, wherein M is an integer greater than 2;
generating, by the user device, from the secret, a primary segment and a shared segment such that the primary segment and the shared segment are necessary and sufficient inputs to an algorithm to reconstruct the secret;
computing, by the user device, based on the shared segment, a set of M shares such that the shared segment is reconstructible using any subset of the shares that includes at least a threshold number t of the M shares and is not reconstructible using any subset of the shares that includes fewer than the threshold number t of the M shares, wherein the threshold number t is greater than 1 and less than M;
providing, by the user device, the primary segment to a server system for storage; and
providing, by the user device, a different one of the M shares to each of the M shareholder devices for storage.

2. The method of claim 1 wherein the secret corresponds to a recovery key usable to recover access to user data stored at the server system.

3. The method of claim 1 wherein identifying the set of M shareholder devices includes:
prompting the user to select M contacts from a contacts list of the user; and
identifying a shareholder device associated with each of the selected contacts.

4. The method of claim 1 further comprising:
generating, by the user device, a private/public key pair based on the shared segment; and
providing, by the user device, the public key to the server system for storage.

5. The method of claim 1 further comprising:
obtaining, at a recovery device, the respective one of the M shares from each of at least the threshold number t of the M shareholder devices such that at least t of the M shares are obtained;
reconstructing, by the recovery device, the shared segment using the at least the threshold number t of the M shares;
providing, by the recovery device, a proof to the server system that the recovery device has reconstructed the shared segment;
receiving, at the recovery device, the primary segment from the server system, wherein the primary segment is received in response to the proof; and
reconstructing, by the recovery device, the secret using the received primary segment and the reconstructed shared segment.

6. The method of claim 5 further comprising:
generating, by the user device, a first private/public key pair based on the shared segment; and
providing, by the user device, the public key to the server system for storage,
wherein providing, by the recovery device, a proof to the server system that the recovery device has reconstructed the shared segment includes:
generating, by the recovery device, a reconstructed private/public key pair based on the reconstructed shared segment; and
using the reconstructed private/public key pair to respond to a challenge from the server system.

7. The method of claim 5 wherein, for at least a first shareholder device of the M shareholder devices, obtaining the respective one of the M shares includes:
presenting, at a user interface of the recovery device, a confirmation code,
wherein the confirmation code is providable by a user operating the recovery device to a shareholder operating the first shareholder device and wherein the first shareholder device provides the respective one of the M shares to the recovery device in response to the confirmation code.

8. The method of claim 5 wherein the user device and the recovery device are different devices.

9. A method comprising:
receiving, at a server system, a primary key segment from a user device, the primary key segment associated with a user account maintained at the server system for a user;
storing, by the server system, the primary key segment in a data repository in association with the user account; subsequently
receiving, by the server system, a request from a recovery device for the primary key segment;
determining, by the server system, whether the recovery device is in possession of a shared key segment corresponding to the primary key segment, wherein the shared key segment was previously used to compute a set of M shares, wherein M is an integer greater than 2 and wherein the M shares were computed such that the shared key segment is reconstructible using any subset of the shares that includes at least a threshold number t of the M shares and is not reconstructible using any subset of the shares that includes fewer than the threshold number t of the M shares, wherein the threshold number t is greater than 1 and less than M, and wherein the M shares were distributed among M shareholder devices,
wherein the determining includes determining whether the recovery device has obtained at least the threshold number t of the M shares from the shareholder devices; and
in response to determining that the recovery device is in possession of the shared key segment, sending the primary key segment to the recovery device.

10. The method of claim 9 further comprising:
at a time prior to sending the primary key segment, performing a user identity verification operation with the recovery device,
wherein the primary key segment is sent only if the user identity verification operation succeeds.

11. The method of claim 9 further comprising:
receiving, from the user device, at the server system, a public key associated with the primary key segment and the user account, the public key having been determined by the user device based on the shared key segment; and
storing, by the server system, the public key in the data repository in association with the user account and the primary key segment,
wherein determining whether the recovery device is in possession of the shared key segment includes:
sending a cryptographic challenge to the recovery device;
receiving a response from the recovery device, the response including a digital signature; and
determining, based at least in part on the digital signature and the public key, whether the recovery device is in possession of the shared key segment.

12. The method of claim 9 wherein the recovery device and the user device are different devices.

13. The method of claim 9 wherein the primary key segment and the shared key segment are together usable to reconstruct a user secret, the user secret including a recovery key that is usable to recover access to secured user data associated with the user account.

14. A method comprising:
initiating, at a recovery device, a recovery process with a server system for recovery of a user secret that was previously enrolled in a recovery service of the server system, wherein as a result of the previous enrollment, the server system stores a primary segment generated from the user secret and a set of M shareholder devices each stores a respective one of a set of M shares of a shared segment generated from the user secret, wherein M is an integer greater than 2 and wherein the shared segment is reconstructible using any subset of the shares that includes at least a threshold number t of the M shares and is not reconstructible using any subset of the shares that includes fewer than the threshold number t of the M shares, wherein the threshold number t is greater than 1 and less than M;
obtaining, by the recovery device, from at least the threshold number t of the M shareholder devices, the respective shares stored thereby, such that at least the threshold number t of the M shares are obtained;
reconstructing, b

Assignees

• Apple Inc

Inventors

• Sierra Yannick L
• Adler Mitchell D

Classifications

• H04L9/3271

  using challenge-response · CPC title

• H04L9/3226

  using a predetermined code, e.g. password, passphrase or PIN (network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083) · CPC title

• H04L9/0894 Primary

  Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage · CPC title

• H04L9/085

  Secret sharing or secret splitting, e.g. threshold schemes · CPC title

• H04L9/3247

  involving digital signatures · CPC title