Secure storage of full disk encryption keys

• US 9,235,532 B2
• Filed: 06/03/2011
• Issued: 01/12/2016
• Est. Priority Date: 06/03/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Callas, Jonathan D., Reece, Russell D.
• Primary Examiner(s): Choe, Yong
• Assistant Examiner(s): Chappell, Daniel C
• Application Number:
  US13/153,311
• Publication Number:
  US 20120311288A1
• Time in Patent Office: 1,684 Days
• Field of Search: 711/166
• US Class Current: 1/1
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/78 to assure secure storage of data address-based protection against unauthorised use of memory G06F12/14; record carriers for use with machines and with at least a part designed to carry digital markings G06K19/00
• CPC Class Codes: G06F 2221/2107 File encryption

Abstract

Data is securely stored on a storage device by encoding a data block into multiple encoded blocks, any number of which can be recombined to recover the data block. The encoded blocks are stored at known logical locations corresponding to physical locations on a storage device that change over time. When the data needs to be destroyed, at least one of the encoded blocks is overwritten with arbitrary data. In one aspect, the encoded blocks include at least one random block that is used to encode the data block. In another aspect, the known logical locations are stored in metadata.

Claims

1. A method comprising:

generating, by a processor, a plurality of random blocks of a pre-determined size for each data block to be encoded, the pre-determined size based on an allocation unit of a storage device;

encoding, by the processor, a first data block into a single encoded data block of the pre-determined size using the plurality of generated random blocks, the single encoded data block generated by performing a mathematical operation on the first data block and each generated random block, wherein the single encoded data block and at least a subset of the generated random blocks are recombined to recover the first data block;

storing the single encoded data block and each generated random block separately at different known logical locations, wherein a physical location on the storage device that corresponds to a known logical location changes over time; and

overwriting at least one of the stored generated random blocks with arbitrary data.

2. The method of claim 1, wherein the encoding comprises:

performing a multipart function with redundancy on the first data block, wherein the mathematical operation is one part of the multipart function.

3. The method of claim 1, wherein the overwriting comprises:

generating a number of arbitrary data blocks, the number of arbitrary data blocks calculated by subtracting a number of blocks in the subset of generated random blocks from a number of blocks in the plurality of generated random blocks plus one.

4. The method of claim 1 further comprising:

saving the known logical locations in metadata.

5. The method of claim 1, wherein the first data block comprises an encryption key to encrypt the storage device.

6. A non-transitory machine-readable storage medium embodied with machine-executable instructions, which when executed by a processor in a machine, cause the processor to perform a method comprising:

generating a plurality of random blocks of a pre-determined size for each data block to be encoded, the pre-determined size based on an allocation unit of a storage device;

encoding a first data block into a single encoded data block of the pre-determined size using the plurality of generated random blocks, the single encoded data block generated by performing a mathematical operation on the first data block and each generated random block, wherein the single encoded data block and at least a subset of the generated random blocks are recombined to recover the first data block;

storing the single encoded data block and each generated random block separately at different known logical locations, wherein a physical location on the storage device that corresponds to a known logical location changes over time; and

overwriting at least one of the stored generated random blocks with arbitrary data.

7. The non-transitory machine-readable storage medium of claim 6, wherein the encoding comprises:

performing a multipart function with redundancy on the first data block, wherein the mathematical operation is one part of the multipart function.

8. The non-transitory machine-readable storage medium of claim 6, wherein the overwriting comprises:

generating a number of arbitrary data blocks, the number of arbitrary data blocks calculated by subtracting a number of blocks in the subset of the generated random blocks from a number of blocks in the plurality of generated random blocks plus one.

9. The non-transitory machine-readable storage medium of claim 6, further comprising:

saving the known logical locations in metadata.

10. The non-transitory machine-readable storage medium of claim 6, wherein the first data block comprises an encryption key to encrypt the storage device.

11. A system comprising:

a processor coupled to a memory through a bus;

a storage device coupled to the processor through the bus; and

a secure storage process executed from the storage device by the processor to cause the processor to generate a plurality of random blocks of a pre-determined size for each data block to be encoded, the pre-determined size based on an allocation unit of the storage device, encode a first data block into a single encoded data block of the pre-determined size using the plurality of generated random blocks, the single encoded data block generated by the processor performing a mathematical operation on the first data block and each generated random block, wherein the single encoded data block and at least a subset of the generated random blocks are recombined to recover the first data block;

store the single encoded data block and each generated random block separately at different known logical locations, wherein a physical location on the storage device that corresponds to a known logical location changes over time; and

overwrite at least one of the generated random blocks with arbitrary data.

12. The system of claim 11, wherein the secure storage process causes the processor to perform a multipart function with redundancy on the first data block to encode the first data block, wherein the mathematical operation is one part of the multipart function.

13. The system of claim 11, wherein the secure storage process causes the processor to generate a number of arbitrary data blocks, the number of arbitrary data blocks calculated by subtracting a number of blocks in the subset of generated random blocks from a number of blocks in the plurality of generated random blocks plus one.

14. The system of claim 11, wherein the secure storage process further causes the processor to save the known logical locations in metadata.

15. The system of claim 11, wherein the first data block comprises an encryption key to encrypt the storage device.

16. A method comprising:

overwriting, by a processor, at least one of a plurality of generated random blocks on a storage device with arbitrary data, the generated random blocks corresponding to a data block and having a pre-determined size based on an allocation unit of the storage device, wherein a single encoded data block having the pre-determined size and previously generated by performing a mathematical operation on a first data block and each generated random block is also stored on the storage device, wherein the single encoded data block and at least a subset of the generated random blocks are recombined to recover the first data block, and wherein the single encoded data block and each generated random block is stored separately at a different known logical location, each known logical location corresponding to a physical location on the storage device that changes over time.

17. A non-transitory machine-readable storage medium embodied with machine-executable instructions, which when executed by a processor in a machine, cause the processor to perform a method comprising:

overwriting at least one of a plurality of generated random blocks on a storage device with arbitrary data, the generated random blocks corresponding to a data block and having a pre-determined size based on an allocation unit of the storage device, wherein a single encoded data block having the pre-determined size and previously generated by performing a mathematical operation on a first data block and each generated random block is also store on the storage device, wherein the single encoded data block and at least a subset of the generated random blocks are recombined to recover the first data block, and wherein the single encoded data block and each generated random block is stored separately at a different known logical location, each known logical location corresponding to a physical location on the storage device that changes over time.

18. A system comprising:

a processor coupled to a memory through a bus;

a storage device coupled to the processor through the bus; and

an overwrite process executed from the memory by the processor to cause the processor to overwrite at least one of a plurality of generated random blocks on the storage device with arbitrary data, the generated random blocks corresponding to a data block and having a pre-determined size based on an allocation unit of the storage device, wherein a single encoded data block having the pre-determined size and previously generated by performing a mathematical operation on a first data block and each of the generated random blocks is also stored on the storage device, wherein the single encoded data block and at least a subset of the generated random blocks are recombined to recover the data block, and wherein the single encoded data block and each of the generated random blocks is stored separately at a different known logical location, each known logical location corresponding to a physical location on the storage device that changes over time.