Secure data shredding in an imperfect data storage device

Patent metadata

Field	Value
Publication number	US-9680651-B2
Application number	US-201414524823-A
Country	US
Kind code	B2
Filing date	Oct 27, 2014
Priority date	Oct 27, 2014
Publication date	Jun 13, 2017
Grant date	Jun 13, 2017

Abstract

Apparatus and method for secure data shredding in an imperfect data storage device. In some embodiments, a hash function is applied to multi-bit random sequence to generate an output hash. A combinatorial logic function logically combines the output hash with a secret to provide an output value. The random string is processed into a plurality of secret shares which are stored in a first location in a non-volatile memory and the output value is stored in a different, second location of the memory. The secret is subsequently shredded by applying an erasure operation upon the secret shares in the first location of the memory.

First claim

What is claimed is:

1. A computer-implemented method comprising:
applying a hash function to a multi-bit random string to generate a multi-bit output hash, the multi-bit random string having a total of n bits selected responsive to an estimated probability at any given time that a particular erasure operation applied to a set of data will not actually alter the programmed states of the memory locations of the data in a non-volatile memory;
using a combinatorial logic function to logically combine the multi-bit output hash with a multi-bit secret to provide a multi-bit output value;
dividing the multi-bit random string into a plurality of secret shares N where a minimum of M<N secret shares are required to reconstruct the multi-bit random string;
storing the N secret shares and the multi-bit output value in the non-volatile memory;
and shredding the multi-bit secret by applying an erasure operation to at least N−M+1 of the N secret shares.

2. The method of claim 1 , the data are shredded without applying an erasure operation upon the output value from the combinatorial logic function in the non-volatile memory.

3. The method of claim 1 , the hash function is a selected hash function from a family of universal hash functions having a plural number X members, the method further comprising generating a parameterization value from a second multi-bit random string identifying a corresponding value from 1 to X, using the parameterization value to identify the applied hash function, and storing the parameterization value in the non-volatile memory, the secret shredded by applying the erasure operation to the secret shares without applying an erasure operation to the output value or to the parameterization value.

4. The method of claim 1 , the secret comprising a symmetric encryption key associated with a selected encryption function, the method further comprising using an encryption engine which enacts the selected encryption function using the symmetric encryption key to generate ciphertext data from a set of input user data, the ciphertext data stored in the non-volatile memory, the secret shredded by applying the erasure operation to the secret shares without applying an erasure operation to the output value or to the ciphertext data.

5. The method of claim 1 , wherein the total number of bits n in the random string is greater than a total number of bits in the secret.

6. The method of claim 1 , wherein the random string has a total number of bits selected in relation to the average min-entropy of the random string given its residue after an erasure operation to provide a probability of less than 51% of an attacker successfully guessing each bit in the random string after the secure erasure operation.

7. The method of claim 1 , wherein the shredding operation comprises applying only a single erasure operation to the memory locations storing the secret shares, and wherein less than all of the bits of the secret shares are reset to a base value responsive to the single erasure operation.

8. The method of claim 1 , wherein the n total number of bits of the random string is further selected in relation to a possibility of a failure of a block of the memory to which the secret shares are stored.

9. The method of claim 1 , wherein the shredding operation comprises applying multiple erasure operations and writing of random data to the memory locations storing the secret shares.

10. The method of claim 1 , further comprising retrieving the secret prior to the shredding operation by combining the secret shares from the non-volatile memory to reconstitute the random string, applying the hash function to the reconstituted random string to generate a second output value, using the combinatorial function to combine the second output value with the output value from the non-volatile memory to generate the secret, and outputting the secret to a host device.

11. The method of claim 1 , the multi-bit secret is a first secret associated with a first data file stored in the non-volatile memory and the multi-bit random string is a first multi-bit random string, the method further comprising storing a second secret in the non-volatile memory by:
providing a second multi-bit random string;
logically combining the second multi-bit random string with the first multi-bit random string to generate a third multi-bit random string;
applying a selected hash value to the third multi-bit random string to generate a second hash;
logically combining the second hash with the second secret to generate a second output value; and
storing the second multi-bit random string and the second output value in the non-volatile memory, the shredding of the first secret by the application of the erasure operation to the secret shares concurrently shredding the second secret without application of an additional erasure operation to another location of the memory.

12. The method of claim 1 , the non-volatile memory comprising a flash memory.

13. The method of claim 1 , the combinatorial logic function comprising an exclusive-or (XOR) function.

14. An apparatus comprising:
a non-volatile memory;
a processing circuit configured to implement the following:
a hash function block which applies a selected hash function from a family of universal hash functions to a multi-bit random string to generate a multi-bit output hash, the multi-bit random string having a total of n bits selected responsive to an estimated probability at any given time that a particular erasure operation applied to a set of data will not actually alter the programmed states of the memory locations of the data in a non-volatile memory and an estimated probability of a block failure of a portion of the non-volatile memory;
a combinatorial logic block which applies a selected combinatorial logic function to logically combine the multi-bit output hash with a multi-bit secret to provide a multi-bit output value;
a secret sharing module which generates a plurality of N secret shares from the multi-bit random string using an (N, M) secret sharing scheme where N−M shares are required to reconstitute the multi-bit random string;
a write control block which directs storage of the N secret shares in a first location of the non-volatile memory and directs storage of the multi-bit output value to a different, second location of the non-volatile memory;
and a data shredding block which directs an erasure operation upon the N secret shares in the first location of the memory to shred the multi-bit secret from the non-volatile memory without applying an erasure operation upon the multi-bit output value in the second location of the non-volatile memory.

15. The apparatus of claim 14 , wherein the secret comprises a symmetric encryption key associated with a selected encryption function, wherein the apparatus further comprises an encryption engine which enacts the selected encryption function using the symmetric encryption key to generate ciphertext data from a set of input user data, wherein the generated ciphertext data are stored in a third location of the non-volatile memory, and wherein the secret is shredded by applying the erasure operation to the first location without applying an erasure operation to the second and third locations.

16. The apparatus of claim 14 , wherein the total number of bits n in the multi-bit random string is greater than and is selected in relation to a total number of bits in the multi-bit secret.

17. The apparatus of claim 14 , wherein the secret shares are each stored in a separate physical block of memory in the first location of the non-

Assignees

• Seagate Technlogy Llc
• Seagate Technology Llc

Inventors

• Anderson William Erik

Classifications

• H04L9/30

  Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy · CPC title

• H04L9/3242 Primary

  involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC · CPC title

• H04L9/085

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

• H04L9/0894

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

• H04L9/0869

  involving random numbers or seeds · CPC title