METHODS FOR CRYPTOGRAPHIC DELEGATION AND ENFORCEMENT OF DYNAMIC ACCESS TO STORED DATA

• US 20150288512A1
• Filed: 09/05/2014
• Published: 10/08/2015
• Est. Priority Date: 01/27/2006
• Status: Active Grant

• Current Assignee: Sysxnet Ltd.
• Original Assignee: Trustwave Holdings Incorporated (Singapore Telecommunications Limited)
• Inventors: White, Matthew N., McGregor, John Patrick
• Granted Patent: US 9,559,837 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

Efficient methods for assigning, revoking, and realizing access to stored data involve a cryptographic key hierarchy and a set of operations performed on cryptographic keys and performed on the data objects to be protected. In addition to providing confidentiality and integrity for data objects, the methods allow access to selected data objects to be permanently revoked for all entities without requiring all instances of the data objects to be destroyed or overwritten. The methods also support access right modifications for a data object without requiring the re-encryption of the entire data object; instead, certain keys are selectively re-encrypted and re-authenticated to implement access control changes. The key hierarchy is parameterized to enable flexible performance tuning, and to provide efficient random access, keying and other security operations are performed for individual blocks within a data object rather than only for the entire data object.

Claims

1. (canceled)

2. A computer implemented method for reading a protected data object stored in a memory of a computer, the protected data object comprising encrypted data blocks and a region of data block metadata, the region of data block metadata associated with at least one of the encrypted data blocks, the method comprising:

reading a first encrypted data block of the encrypted data blocks from the memory;

reading a hierarchical key tree associated with the protected data object from a) the region of data block metadata or b) a data object header stored in the protected data object;

decrypting, in succession, using a set of first decryption algorithms, encrypted first path keys on a first key path of the hierarchical key tree from a top node of the hierarchical key tree comprising a plaintext version of a received data object decryption key to a node in a bottom row of the hierarchical key tree comprising an encrypted per-block decryption key for the first encrypted data block, the decrypting including decrypting the encrypted first path keys starting with decrypting one of the encrypted first path keys immediately following the data object decryption key using the data object decryption key and continuing with decrypting the next encrypted first path key with a decrypted version of a preceding first path key moving from the top node to the bottom row until a decrypted version of the per-block decryption key for the first encrypted data block is obtained; and

decrypting, using the per-block decryption key and a second decryption algorithm, the first encrypted data block to produce a first decrypted data block.

3. The computer implemented method as defined in claim 2, wherein the protected data object comprises a plurality of regions of data block metadata and wherein the plurality of regions of data block metadata is interleaved between the encrypted data blocks.

4. A computer implemented method for reading a protected data object stored in a memory of a computer, the protected data object comprising encrypted data blocks and a region of data block metadata, the region of data block metadata associated with at least one of the encrypted data blocks, the method comprising:

reading a first encrypted data block of the encrypted data blocks from the memory;

reading a hierarchical key tree associated with the protected data object from a) the region of data block metadata or b) a data object header stored in the protected data object; and

decrypting, in succession, using a set of first decryption algorithms, encrypted first path keys on a first key path of the hierarchical key tree from a top node of the hierarchical key tree comprising a plaintext version of a received data object decryption key to a node in a bottom row of the hierarchical key tree comprising an encrypted per-block hash key for the first encrypted data block, the decrypting including decrypting the encrypted first path keys starting with decrypting one of the encrypted first path keys immediately following the data object decryption key using the data object decryption key and continuing with decrypting the next encrypted first path key with a decrypted version of a preceding first path key moving from the top node to the bottom row until a decrypted version of the per-block hash key for the first encrypted data block is obtained.

5. The computer implemented method as defined in claim 4, further comprising generating for the first encrypted data block, a generated per-block hash value or a generated per-block hash message authentication code (HMAC) using as inputs at least one of the per-block hash key and data contained in the first encrypted data block.

6. The computer implemented method as defined in claim 5, further comprising comparing the generated per-block hash value for the first encrypted data block with a stored per-block hash value read from the memory.

7. The computer implemented method as defined in claim 5, further comprising comparing the generated per-block HMAC for the first encrypted data block with a stored per-block HMAC read from the memory.

8. The computer implemented method as defined in claim 5, further comprising reading a portion of a hash tree associated with the protected data object and a stored data object hash value or data object HMAC from the region of data block metadata and the data object header.

9. The computer implemented method as defined in claim 8, wherein the hash tree has a row of bottom nodes each comprising (i) a stored per-block hash value for the first encrypted data block or (ii) a stored per-block HMAC for the first encrypted data block.

10. The computer implemented method as defined in claim 9, further comprising generating a generated data object hash value for the protected data object using the hash tree by at least one of:

(i) substituting the generated per-block hash value for the first encrypted data block for the stored per-block hash value for the first encrypted data block in the row of bottom nodes, and

recalculating the portion of the hash tree to produce the generated data object hash value;

or

(ii) substituting the generated per-block HMAC for the first encrypted data block for the stored per-block HMAC for the first encrypted data block in the row of bottom nodes, and

recalculating the portion of the hash tree to produce the generated data object hash value.

11. The computer implemented method of claim 10, further comprising generating a generated data object HMAC for the generated data object using a decrypted version of an encrypted data object hash key read from at least one of the regions of data block metadata or the data object header and the data object hash value as inputs to a hash function.

12. The computer implemented method of claim 11, further comprising comparing the generated data object HMAC for the generated data object with a stored data object HMAC for the data object read from the memory.

13. The computer implemented method of claim 12, further comprising issuing a notification that the data from the first encrypted data block has been at least one of modified or accessed without authorization if the generated data object HMAC for the generated data object is not equal to the stored data object HMAC for the generated data object.

14. The computer implemented method of claim 12, further comprising issuing a notification that the data from the first encrypted data block has been at least one of modified or accessed without authorization if the generated per-block HMAC for the first data block is not equal to the stored per-block HMAC for the first data block.

15. A computer implemented method for modifying a protected data object stored in a memory of a computer, wherein the protected data object comprises data blocks and a region of data block metadata, the region of data block metadata associated with at least one of the data blocks, the method comprising:

generating new first path decryption keys for first path keys on a first key path, the generating including generating the new first path decryption keys for a per-block decryption key but not a data object decryption key, the first key path from a hierarchical key tree read from at least one of the region of data block metadata or a data object header associated with the protected data object.

16. The computer implemented method of claim 15, further comprising encrypting a first modified data block with a first encryption algorithm using a new per-block encryption key that corresponds to the per-block decryption key to produce an encrypted first modified data block.

17. The computer implemented method of claim 16, further comprising:

logically inserting the new per-block encryption key into a node in a bottom row of the hierarchical key tree corresponding to the first modified data block;

inserting the first path keys into their respective nodes on the first key path; and

starting with new per-block decryption key for the first modified data block, encrypting the new first path decryption keys on the first key path with a new encryption key that corresponds to a next of the new first path decryption keys on the first key path moving in a direction on the first key path from a bottom row to a top node of the hierarchical key tree, the new first path key immediately preceding the data object decryption key on the first key path with respect to the direction being encrypted with a data object encryption key corresponding to the data object decryption key.

18. The computer implemented method of claim 17, further comprising:

writing the encrypted first modified data block to one of the data blocks of the protected data object; and

writing the first path keys to the data block metadata of the protected data object.

19. A computer implemented method for enforcing access rights changes for a protected data object stored in a memory of a computer, wherein the protected data object comprises data blocks and a region of data block metadata associated with at least one of the data blocks, the method comprising:

reading a hierarchical key tree from the memory, wherein the hierarchical key tree comprises A) a first data object decryption key disposed in a top node of the hierarchical key tree and B) at least one of

     1) an intermediate row of nodes wherein each of the nodes contains an encrypted intermediate decryption key and a bottom row of nodes wherein each of the nodes contains at least one key and

     2) an encrypted per-block decryption key, wherein a plurality of key paths, each consisting of two keys, have been defined in the hierarchical key tree, the key paths having a first end point comprising the top node and a second end point comprising one of the nodes in the intermediate row of nodes or one of the nodes in the bottom row nodes;

decrypting, using the first data object decryption key, each encrypted key in succession on each of the plurality of key paths, except for the first data object decryption key, the decrypting starting with decrypting the encrypted key immediately following the first data object decryption key using the first data object decryption key and continuing with decrypting the next encrypted key on the key path with decrypted version of a preceding key on the key path moving from the top node to the second end point of the key path;

generating a new data object decryption key and a corresponding new data object encryption key associated with the data object; and

encrypting each key on each of the plurality of key paths, by starting at the second end point of each of the key paths and encrypting each key on the key path, except for the new data object encryption key, with the new data object encryption key.

20. The computer implemented method of claim 19, further comprising, after the encrypting, writing the encrypted keys on the plurality of key paths to a subset of the nodes of the hierarchical key tree that is stored in the memory.

21. The computer implemented method of claim 19, further comprising discarding at least one of encrypted versions or plaintext versions of the first data object decryption key and of any data object encryption key corresponding to the first data object decryption key.

22. The computer implemented method of claim 19, wherein the new data object encryption key is equivalent to the new data object decryption key.

23. The computer implemented method of claim 19, wherein the new data object encryption key is not equivalent to the new data object decryption key.

24. The computer implemented method of claim 19, wherein the generating is initiated by an entity having authority to modify access rights to the protected data object.

25. A computer implemented method for an entity to disable access to a protected data object stored in a memory of a computer, the method comprising:

encrypting a data object key using an encryption key and a second encryption algorithm to produce an encrypted data object key, the data object key received at the entity from the computer that encrypted the protected data object with the data object key using a first encryption algorithm;

sending the encrypted data object key to the computer; and

destroying a decryption key corresponding to the encryption key to disable access to the protected data object.

26. The computer implemented method of claim 25, wherein the encrypting the data object key is performed Q times and wherein, if Q is greater than one, inputs to a jth encryption operation are the encryption key and an output of a (j−

1)th encryption operation, where j is greater than one and fewer than Q+1.

27. The computer implemented method of claim 26, further comprising, prior to the destroying of the decryption key to disable access to the protected data object, sending the data object key in decrypted form to the computer.

28. The computer implemented method of claim 27, further comprising decrypting, on the computer, the encrypted data object using the data object key and a decryption algorithm corresponding to the first encryption algorithm to produce the protected data object.

29. The computer implemented method of claim 27, wherein the encrypted data object consists of a plurality of encrypted data blocks, further comprising decrypting, on the computer, the encrypted data blocks using the data object key and a decryption algorithm corresponding to the first encryption algorithm to produce data blocks of the protected data object.

30. The computer implemented method of claim 26 wherein the entity is at least one of embedded in hardware on the computer, embedded in software on the computer, or located on another computer.

31. The computer implemented method of claim 26, further comprising, after sending the data object key from the computer to the entity, destroying, on the computer, remaining plaintext copies of the data object key stored in the computer.

32. The computer implemented method of claim 28, further comprising, after receiving the data object encryption key from the entity at the computer, destroying, on the computer, remaining plaintext copies of the data object key stored in the computer.

33. The computer implemented method of claim 25, further comprising sending, by the computer, the encrypted data object and the encrypted data object key to a second computer.

34. The computer implemented method of claim 33, further comprising, prior to the destroying of the decryption key to disable access to the protected data object, receiving the data object key in decrypted form at the second computer from the entity.

35. The computer implemented method of claim 34, further comprising decrypting, on the second computer, the encrypted data object using the data object key and a decryption algorithm corresponding to the first encryption algorithm to produce the protected data object.

36. The computer implemented method of claim 34, wherein the encrypted data object comprises a plurality of encrypted data blocks, the method further comprising decrypting, on the second computer, the encrypted data blocks using the data object key and a decryption algorithm corresponding to the first encryption algorithm to produce data blocks of the protected data object.

37. A computer implemented method for deleting a first data block from a protected data object stored in a memory of a computer, wherein the protected data object comprises a data block and a region of data block metadata associated with the data blocks, the method comprising:

deleting the first data block from the memory; and

deleting a key path corresponding to the first data block in a hierarchical key tree read from at least one of the data block metadata or a data object header, the deleting including deleting a bottom row node on the key path in a bottom row of the hierarchical key tree containing a per-block cryptographic key corresponding to the first data block.

38. The computer implemented method of claim 37, further comprising deleting a node on the key path, wherein the node is not a top node.

39. A computer implemented method for appending a first data block from a protected data object stored in a memory of a computer, wherein the protected data object comprises a data block and a region of data block metadata associated with at least one of the data blocks, the method comprising:

appending the first data block to the protected data object in the memory; and

adding a key path corresponding to the first data block in a hierarchical key tree read from at least one of the region of data block metadata or a data object header, the adding including adding a bottom row node on the key path in a bottom row of the hierarchical key tree containing a per-block cryptographic key corresponding to the first data block.

40. The computer implemented method of claim 39, further comprising adding a node on the key path, wherein the node is not a top node.