Methods for cryptographic delegation and enforcement of dynamic access to stored data

• US 9,559,837 B2
• Filed: 09/05/2014
• Issued: 01/31/2017
• Est. Priority Date: 01/27/2006
• Status: Active Grant

• Current Assignee: Sysxnet Ltd.
• Original Assignee: Trustwave Holdings Incorporated (Singapore Telecommunications Limited)
• Inventors: McGregor, John Patrick, White, Matthew N.
• Primary Examiner(s): Tabor, Amare F
• Application Number:
  US14/478,998
• Publication Number:
  US 20150288512A1
• Time in Patent Office: 879 Days
• Field of Search: 380/37
• 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. 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, the protected data object including a plurality of regions of data block metadata interleaved between the encrypted data blocks;

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 including a plaintext version of a received data object decryption key to a node in a bottom row of the hierarchical key tree including 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.

19. The computer implemented method as defined in claim 1, wherein substantially all of the data block metadata associated with its corresponding data block reside in a location preceding its corresponding encrypted data block in a location ranging from the immediate preceding adjacent location to its corresponding encrypted data block to a potential maximum distance location at a location following the data object header but preceding the first allowable data block location.

20. The computer implemented method as defined in claim 1, wherein substantially all of the data block metadata associated with its corresponding data block reside in a location following its corresponding encrypted data block in a location ranging from an immediately-following location to its corresponding encrypted data block to a potential maximum distance location at a location after the location of the last data block within the data object.

21. The computer implemented method as defined in claim 1, wherein substantially all of the data block metadata can be parsed to multiple pieces consisting of varying lengths or sizes up to any sufficient number of N bits and such individual parsed data block metadata reside in locations both preceding and following said corresponding data block in locations including but not limited to immediately adjacent to a potential maximum distance location at a location following the data object header but preceding the first allowable data block location, or to a potential maximum distance location at a location after the location of the last data block within the data object.

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, the protected data object including a plurality of regions of data block metadata interleaved between the encrypted data blocks;

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 including a plaintext version of a received data object decryption key to a node in a bottom row of the hierarchical key tree including 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.

3. The computer implemented method as defined in claim 2, further including 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.

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

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

6. The computer implemented method as defined in claim 3, further including 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.

7. The computer implemented method as defined in claim 6, wherein the hash tree has a row of bottom nodes each including (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.

8. The computer implemented method as defined in claim 7, 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.

9. The computer implemented method of claim 8, further including 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.

10. The computer implemented method of claim 9, further including 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.

11. The computer implemented method of claim 10, further including 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.

12. The computer implemented method of claim 10, further including 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.

22. The computer implemented method as defined in claim 3, further including incrementing the version number for the data object prior to generating the new data object hash message authentication code.

13. 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 includes 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 including the top node and a second end point including 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 protected data object, the protected data object including a plurality of regions of data block metadata interleaved between the data blocks; 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.

14. The computer implemented method of claim 13, further including, 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.

15. The computer implemented method of claim 13, further including 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.

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

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

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

23. The computer implemented method of claim 13, further including, 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 accessed by the machine via network interface to another memory location that is capable of storing such information.

24. The computer implemented method of claim 13, further including, 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 accessed by the machine via peripheral storage medium such as removable storage.