Controlling verification of key-value stores

Patent metadata

Field	Value
Publication number	US-10396991-B2
Application number	US-201615199673-A
Country	US
Kind code	B2
Filing date	Jun 30, 2016
Priority date	Jun 30, 2016
Publication date	Aug 27, 2019
Grant date	Aug 27, 2019

Abstract

Deferred verification of the integrity of data operations over a set of data that is hosted at an untrusted module (UM) is controlled. The controlling includes generating a request for a data operation on the set of data. The request includes an authentication portion. The request is sent to the UM. A response to the request is received from the UM. The response includes cryptographic verification information attesting the integrity of the data operation with respect to prior data operations on the set of data. The response includes results from deferred verification at a trusted module (TM).

First claim

What is claimed is:

1. A client system comprising:
at least one hardware device processor; and
a memory storing a client secure key value, and storing executable instructions that, when executed, cause the at least one hardware device processor to:
control deferred verification of the integrity of data operations over a set of data that is hosted at a server having an untrusted module and a trusted module having secure hardware, the deferred verification being controlled by:
generating a request for at least one data operation on the set of data, the request including an authentication portion generated using the client secure key value;
sending the request from the client system to the server; and
receiving, by the client system from the server, a response to the request, the response including cryptographic verification information attesting to the integrity of the at least one data operation with respect to multiple prior data operations on the set of data, the response including results from deferred verification generated by the secure hardware of the trusted module of the server,
wherein the deferred verification by the secure hardware involves separate verification of multiple verification epochs, and at least one of the verification epochs includes two or more operations that are concurrently verified by the secure hardware of the trusted module.

2. The client system of claim 1 , wherein:
the data operations include insert, lookup, delete, and update operations.

3. The client system of claim 1 , wherein:
the set of data is included in a key-value store that is hosted at the untrusted module of the server.

4. The client system of claim 1 , wherein the response to the request is received from the untrusted module of the server and the response to the request includes a message authentication code-based attestation of the integrity for a result of the at least one data operation with respect to the multiple prior data operations on the set of data.

5. The client system of claim 1 , wherein:
generating the request comprises including, in the request, a message authentication code that is based at least on the client secure key value, the client secure key value being a cryptographic key that is shared with the trusted module of the server, and
receiving the response to the request includes receiving the response to the request from the trusted module of the server, via forwarding by the untrusted module of the server.

6. The client system of claim 1 , wherein:
generating the request includes generating a unique transaction identifier corresponding to the at least one data operation, the request including an encrypted authentication portion that includes a message authentication code that is based at least on the client secure key value, the client secure key value being a cryptographic key that is shared with the trusted module of the server,
wherein the request includes an encrypted version of:
the unique transaction identifier, and
an indicator identifying the at least one data operation.

7. The client system of claim 1 , wherein the executable instructions, when executed, cause the at least one hardware device processor to:
in an instance when the response indicates the deferred verification has failed, resort to a previously-verified backup of the set of data.

8. A method performed by a trusted module of a computing device, the method comprising:
controlling deferred verification of the integrity of data operations over a set of data that is hosted at an untrusted module by:
receiving, at the trusted module, a first message indicating a request from a client that shares a cryptographic key with the trusted module, the request being for at least one data operation on the set of data;
performing deferred verification of the at least one data operation with respect to multiple prior data operations by designating verification epochs and separately verifying the verification epochs, wherein at least one of the verification epochs includes multiple operations that are concurrently verified by secure hardware of the trusted module; and
sending a second message from the trusted module in response to the request from the client, the response including cryptographic verification information generated by the trusted module using the cryptographic key, the cryptographic verification information attesting to the integrity of the at least one data operation with respect to the multiple prior data operations on the set of data.

9. The method of claim 8 , wherein:
the first message includes a received operation identifier, a received value of a key, a received proof cell corresponding to a verified memory cell that is stored in the untrusted module, and a received operation cryptographic hash that is included in an authentication portion of the first message received from the client,
wherein the method includes:
determining an operation type of a first data operation indicated by the request.

10. The method of claim 9 , wherein the operation type is a lookup operation,
wherein the method includes:
verifying integrity of the lookup operation, by using the received operation cryptographic hash;
verifying a correctness of the received proof cell for the received value of the key; and
determining a success value of the lookup operation, based at least on a comparison of a key value in the received proof cell with the received value of the key.

11. The method of claim 9 , wherein the operation type is a lookup operation,
wherein the method includes:
verifying integrity of the lookup operation, by using the received operation cryptographic hash;
verifying a correctness of the received proof cell for the received value of the key; and
determining a failure value of the lookup operation, based at least on determining inequality of a key value in the received proof cell with the received value of the key.

12. The method of claim 9 , wherein the operation type is an insert operation,
wherein the method includes:
verifying integrity of the insert operation, by using the received operation cryptographic hash;
verifying a correctness of the received proof cell for the received value of the key; and
determining a success value of the insert operation, based at least on verifying that a second received proof cell is an empty proof cell, prior to performance of the insert operation.

13. The method of claim 9 , wherein the operation type is a delete operation,
wherein the method includes:
verifying integrity of the delete operation, by using the received operation cryptographic hash;
verifying a correctness of the received proof cell for the received value of the key; and
determining a success value of the delete operation, based at least on verifying that a second received proof cell is a prior-key proof cell that stores a next-key value that corresponds to a key value of the received proof cell prior to performance of the delete operation,
wherein the next-key value indicates a value of a following key that immediately follows the value of the key value of the received proof cell in an ordering of values of keys for the set of data stored at the untrusted module.

14. The method of claim 8 , wherein:
the first message includes an operation identifier for an operation that includes reading contents of a memory location of the untrusted module,
wherein the method includes:
verifying, by the trusted module, that the operation includes accessing contents of a most recent successful write, the most recent successful write being performed by the trusted module to the memory location of the untr

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Arasu Arvind
• Eguro Kenneth
• Kaushik Raghav
• Kossmann Donald
• Ramamurthy Ravishankar
• Meng Pingfan
• Pandey Vineet

Classifications

• G06F21/645 Primary

  using a third party · CPC title

• G06F21/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 title

• G06F16/00

  Information retrieval; Database structures therefor; File system structures therefor · CPC title

• H04L9/3242

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

• H04L9/3236

  using cryptographic hash functions · CPC title