Deletion of content in digital storage systems

Patent metadata

Field	Value
Publication number	US-9298951-B2
Application number	US-201414547940-A
Country	US
Kind code	B2
Filing date	Nov 19, 2014
Priority date	Nov 20, 2013
Publication date	Mar 29, 2016
Grant date	Mar 29, 2016

Abstract

A data processing and storage apparatus has a hardware security module and a data storage medium storing encrypted data objects and a hierarchical data maintenance structure of encrypted partition tables and hash-nodes forming a rooted tree, where a given partition table comprises a first reference to a given encrypted data object and a first cryptographic key for decryption thereof, where a given hash-node comprises a second reference to a partition tables or hash-node and a second cryptographic key being suitable for decryption thereof, and where the root node is decipherable using a master cryptographic key stored in the hardware security module, the given data object being assigned to the root node via the first and second references of the given partition table and the given hash-nodes forming a set of successive nodes in the rooted tree.

First claim

The invention claimed is:

1. A data processing and storage apparatus comprising:
a data storage medium; and
a hardware security module, said hardware security module having an internal storage for securely storing a master cryptographic key, said data storage medium being configured for storing a number of individually encrypted data objects and a data maintenance structure comprising a number of individually encrypted partition tables and individually encrypted hash-nodes, the encrypted partition tables and the encrypted hash-nodes forming a hierarchical data structure via a rooted tree, wherein:
a given partition table of said partition tables comprises a first reference assigning a given encrypted data object of the encrypted data objects to the given partition table, wherein said given partition table further comprises a first cryptographic key being suitable for decryption of said given encrypted data object,
a given hash-node of said hash-nodes comprises a second reference assigning one of the encrypted partition tables or one of the hash-nodes to the given hash-node, wherein said given hash-node comprises a second cryptographic key being suitable for decryption of said one of the encrypted partition tables or one of the hash-nodes assigned to the given hash node via the second reference, and
the root node of the rooted tree is decipherable using the master cryptographic key, the given data object being assigned to the root node via the first and second references of the given partition table and the given hash-nodes, wherein said given partition table and the given hash-nodes form a first set of successive nodes in the tree; and

wherein the data processing and storage apparatus comprises an application program, the application program being operable for receiving an instruction for deleting said given data object, wherein the application program is further operable in response to receiving the instruction for deleting said given data object for:
traversing the first set of successive nodes in the tree by successively decrypting all hash-nodes and the partition table starting from the root node using the second cryptographic keys obtained by decrypting each of the nodes, and
recursively traversing the first set of successive nodes starting from the partition table and re-encrypting all said recursively traversed nodes with new second cryptographic keys, whereby the first cryptographic key is removed from the partition table or disregarded in the re-encryption of the partition table.

2. The data processing and storage apparatus of claim 1 , further being configured for adding a new data object to the data storage medium, said adding comprising:
encrypting said new data object with a new first cryptographic key;
storing the encrypted new data object on the data storage medium for assigning the new data object to the root node via the first and second references of the given partition table and the given hash-nodes;
traversing the first set of successive nodes in the tree by successively decrypting all hash-nodes and the partition table starting from the root node using the second cryptographic keys obtained by decrypting each of the nodes;
adding a further first reference and the new first cryptographic key to the given partition table, the further first reference assigning the encrypted new data object to the given partition table; and
re-encrypting said given partition table with a third cryptographic key.

3. The data processing and storage apparatus of claim 2 , further being configured for recursively traversing the first set of successive nodes starting from the given partition table, thereby re-encrypting all said recursively traversed nodes with new second cryptographic keys.

4. The data processing and storage apparatus according to claim 2 , further being configured for recursively traversing the first set of successive nodes starting from the given partition table and re-encrypting all said recursively traversed nodes with their respective second cryptographic keys, wherein the third cryptographic key corresponds to the second cryptographic key of the given partition table.

5. The data processing and storage apparatus according to claim 1 , further being configured for rebalancing the data maintenance structure of the hash-nodes and the partition tables, thereby distributing data from a source hash-node of the given hash-nodes or the given partition table to a target hash-node of said hash nodes or a target partition-table of said partition tables, the source hash node or the given partition table being assigned to the root node via the second references of the given hash-nodes, wherein said given partition table and the given hash-nodes form a second set of successive nodes in the tree, the target hash node or the target partition table being assigned to the root node via the second references of the given hash-nodes, wherein said target partition table and the given hash-nodes form a third set of successive nodes in the tree, the apparatus being configured for performing the rebalancing, said rebalancing comprising:
traversing the second set of successive nodes in the tree by successively decrypting all nodes starting from the root node using the second cryptographic keys obtained by decrypting each of the nodes, said traversing resulting in a decrypted given partition table or decrypted source hash-node;
traversing the third set of successive nodes in the tree by successively decrypting all hash-nodes and the partition table starting from the root node using the second cryptographic keys obtained by decrypting each of the nodes, said traversing resulting in a decrypted target partition table or decrypted target hash-node;
adding at least a part of the references and cryptographic keys comprised in the decrypted given partition table or decrypted source hash-node to the decrypted target partition table or decrypted target hash-node;
removing said moved part from the respective decrypted given partition table or decrypted source hash-node;
recursively traversing the second set of successive nodes starting from the given partition table or the source hash-node and re-encrypting all said recursively traversed nodes with new second cryptographic keys; and
recursively traversing the third set of successive nodes starting from the target partition table or the target hash-node and re-encrypting all said recursively traversed nodes with new second cryptographic keys.

6. The data processing and storage apparatus according to claim 1 , whereby the given data object is assigned a unique identifier.

7. The data processing and storage apparatus according to claim 6 , the given hash-node of said hash-nodes having associated a hash-function description, said hash-function description providing a mapping of the unique identifier to the second reference assigning one of the encrypted partition tables or one of the hash-nodes to the given hash-node.

8. The data processing and storage apparatus according to claim 7 , said rebalancing further comprising replacing the hash-function description in the source hash-node and the target hash node in order to reflect the change in the cardinality of the set of second references comprised in these hash-nodes.

9. The data processing and storage apparatus according to claim 1 , said hardware security module being configured for performing the decryption and encryption thereby confining the master cryptographic key and the first cryptographic keys and the second cryptographic keys and any decrypted plain-text representation of data objects involved in the decryption or encryption operation to the internal storage.

10. The data processing and storage apparatus according to

Assignees

• IBM

Inventors

• Barney Jonathan M
• Lebutsch David
• Mega Cataldo
• Schleipen Stefan
• Waizenegger Tim

Classifications

• H04L9/3242 Primary

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

• G06F2221/2143

  Clearing memory, e.g. to prevent the data from being stolen · CPC title

• G06F21/78 Primary

  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 title

• G06F3/0652

  Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket · CPC title

• G06F3/062

  Securing storage systems · CPC title