Systems and methods for quorum-based data recovery

• US 10,176,056 B2
• Filed: 04/10/2015
• Issued: 01/08/2019
• Est. Priority Date: 06/27/2014
• Status: Active Grant

• Current Assignee: PQ Solutions Limited
• Original Assignee: PQ Solutions Limited
• Inventors: Tomlinson, Martin, Tjhai, Cen Jung, Cheng, Andersen
• Primary Examiner(s): Gracia, Gary S
• Application Number:
  US14/683,379
• Publication Number:
  US 20150378842A1
• Time in Patent Office: 1,369 Days
• Field of Search: 380 28, 714 20
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 21/40 by quorum, i.e. whereby two or more security principals are required
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms

Abstract

The present disclosure includes systems and methods for quorum-based data recovery, in which data is recovered provided at least a minimum number of quorum data portions are presented. In exemplary embodiments, a predetermined minimum number of versions of original data is received, and the original data is reconstructed from the received versions, wherein the original data cannot be reconstructed without loss unless a predetermined minimum number of versions is received. In other embodiments, erroneous or corrupted quorum data portions are detected and associated participants presenting said erroneous or corrupted quorum data portions are identified.

Claims

1. A computer-implemented method of quorum-based data recovery, by a quorum system in communication with a plurality of computing devices via a data network, the computing devices associated with respective users that are entities authorized to participate as quorum members, the method comprising:

receiving, from the plurality of computing devices by the quorum system, at least a predetermined minimum number of quorum portions generated from original data using a secret key that is partitioned into a plurality of key components, wherein each received quorum portion comprises;

at least one ciphertext portion defining a received set of ciphertext portions generated by encrypting the original data using a partial encryption key formed from a corresponding defined combination of said key components; and

at least one received key component of said plurality of key components, wherein the at least one received key component was not included in the defined combination of key components of the partial key used to generate the set of ciphertext portions of the corresponding received quorum portion;

identifying the plurality of received key components from the received quorum portions;

determining a plurality of candidate combinations of the identified received key components, each candidate combination forming a candidate partial key, and wherein each candidate combination corresponds to a defined set of ciphertext portions;

identifying and decrypting, for the defined set of ciphertext portions of each candidate partial key, the corresponding at least one ciphertext portion from the received quorum portions, using the respective candidate partial key; and

determining that at least one candidate partial key is a legitimate partial key to recover the original data by verifying received quorum portions that are correct and received purported quorum portions that include errors from the corresponding decrypted at least one ciphertext portion.

2. The method of claim 1, wherein each ciphertext portion is generated by encrypting data comprising the original data and a hash of each key component of the corresponding partial key.

3. The method of claim 2, wherein the received ciphertext portions are decrypted to recover the original data and hash of said partial encryption keys, and at least one received quorum portion is identified as containing incorrect data based on a discrepancy between the recovered hash of the respective partial encryption key and a computed hash of the received respective partial encryption key.

4. The method of claim 1, wherein the corresponding at least one received ciphertext portions are identified using stored masking data defining the combinations of key components of the partial keys.

5. The method of claim 1, further comprising calculating at least one modifier value derived from said decrypted at least one ciphertext portion, and reconstructing at least one other ciphertext portion using the calculated at least one modifier value.

6. The method of claim 3, further comprising receiving a greater number of quorum portions than said predetermined minimum number, wherein the original data is recovered from a combination of received quorum portions that produces no discrepancies in any of the hash values of the partial encryption keys of said combination of received quorum portions.

7. The method of claim 1, wherein each quorum portion includes encoded control data indicating that the associated quorum portion contains correct or incorrect data values.

8. The method of claim 7, wherein each quorum portion is generated from data including said control data at respective defined positions in the original data, wherein corrupted data values are identified from discrepancies with the control data in the reconstructed original data.

9. The method of claim 8, wherein the control data is generated based on a cryptographic function of the data value of the associated quorum portion, wherein corrupted data values are identified from discrepancies between the reconstructed control data and recomputed control data values based on the cryptographic function of data values from the reconstructed original data.

10. The method of claim 1, wherein the original data comprises a portion of a data file or data stream, and wherein the data recovery process is repeated for each of a plurality of portions of the data file or data stream.

11. The method of claim 1, further comprising generating said plurality of quorum portions from original data, and distributing the plurality of quorum portions between a plurality of entities.

12. The method of claim 11, wherein the entities comprise one or more of:

a computing device, an authentication token and a security dongle.

13. The method of claim 11, wherein identified discrepancies in received quorum portions are used to identify the associated entity presenting quorum portions containing corrupted or erroneous values.

14. The method of claim 11, wherein one or more of said entities receives a greater proportion of said quorum portions.

15. The method of claim 1, wherein each quorum portion is received from a corresponding computing device, together with additional data associated with the computing device, and wherein the defined series of reconstruction relationships encode dependencies between data values of the received versions and the additional data.

16. The method of claim 15, wherein the additional data is associated with a current location and/or current time and/or current date and/or identity of the computing device.

17. The method of claim 1, wherein the original data is an encryption or decryption key, an authentication key or a password.

18. The method of claim 1, wherein at least one quorum portion includes metadata associated with validity of the quorum portion.

19. The method of claim 1, wherein the verifying is based on a comparison of a reconstructed hash of each partial key in the candidate combination to a computed hash of the corresponding received partial key.

20. The method of claim 1, wherein said subset consists of one of the defined combination of partial encryption keys used to generate the ciphertext portions.

21. The method of claim 1, wherein the verifying comprises determining the identity or identities of one or more quorum members that contributed to erroneous reconstructed data.

22. A quorum system comprising one or more processors in communication with a plurality of computing devices, each computing device associated with respective users that are entities authorized to participate as quorum members for quorum-based data recovery, the system configured to:

receive, from the plurality of computing devices, at least a predetermined minimum number of quorum portions generated from original data using a secret key that is partitioned into a plurality of key components, wherein each received quorum portion comprises;

at least one ciphertext portion defining a received set of ciphertext portions generated by encrypting the original data using a partial key formed from a corresponding defined combination of said key components; and

at least one received key component of said plurality of key components, wherein the at least one received key component was not included in the defined combination of key components of the partial key used to generate the set of ciphertext portions of the corresponding received quorum portion;

determine a plurality of candidate combinations of the identified received key components, each candidate combination forming a candidate partial key, and wherein each candidate combination corresponds to a defined set of ciphertext portions;

identify and decrypt, for the defined set of ciphertext portions of each candidate partial key, the corresponding at least one received ciphertext portion from the received quorum portions, using the respective candidate partial key; and

determine that at least one candidate partial key is a legitimate partial key to recover the original data by verifying received quorum portions that are correct and received quorum portions that include errors from the corresponding decrypted at least one ciphertext portion.

23. A non-transitory computer-readable medium comprising computer-executable instructions that, when executed, perform a method of quorum-based data recovery, by a quorum system in communication with a plurality of computing devices via a data network, the computing devices associated with respective users that are entities authorized to participate as quorum members, comprising:

receiving, from the plurality of computing devices by the quorum system, at least a predetermined minimum number of quorum portions generated from original data using a secret key that is partitioned into a plurality of key components, wherein each received quorum portion comprises;

at least one ciphertext portion defining a received set of ciphertext portions generated by encrypting the original data using a partial encryption key formed from a corresponding defined combination of said key components; and

at least one received key component of said plurality of key components, wherein the at least one received key component was not included in the defined combination of key components of the partial key used to generate the set of ciphertext portions of the corresponding received quorum portion;

identifying the plurality of received key components from the received quorum portions;

determining a plurality of candidate combinations of the identified received key components, each candidate combination forming a candidate partial key, and wherein each candidate combination corresponds to a defined set of ciphertext portions;

identifying and decrypting, for the defined set of ciphertext portions of each candidate partial key, the corresponding at least one ciphertext portion from the received quorum portions, using the respective candidate partial key; and

determining that at least one candidate partial key is a legitimate partial key to recover the original data by verifying received quorum portions that are correct and received purported quorum portions that include errors from the corresponding decrypted at least one ciphertext portion.