Controlling secure processing of confidential data in untrusted devices

• US 10,073,981 B2
• Filed: 10/09/2015
• Issued: 09/11/2018
• Est. Priority Date: 10/09/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Arasu, Arvind, Eguro, Kenneth, Joglekar, Manas Rajendra, Kaushik, Raghav, Kossmann, Donald, Ramamurthy, Ravishankar
• Primary Examiner(s): Plecha, Thaddeus J
• Application Number:
  US14/880,186
• Publication Number:
  US 20170103217A1
• Time in Patent Office: 1,068 Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 21/606 by securing the transmission between two devices or processes
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 21/76 in application-specific integrated circuits [ASIC] or field-programmable devices, e.g. field-programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: H04L 2463/062 applying encryption of the keys cryptographic mechanisms or cryptographic arrangements for key distribution using key encryption key H04L9/0822
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 9/0637 Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]
• CPC Class Codes: H04L 9/0819 Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) network architectures or network communication protocols for key distribution in a packet data network H04L63/062
• CPC Class Codes: H04L 9/0822 using key encryption key
• CPC Class Codes: H04L 9/088 Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068

Abstract

A number of transmissions of secure data communicated between a secure trusted device and an unsecure untrusted device in a DBMS is controlled. The data is communicated for database transaction processing in the secure trusted device. The number of transmissions may be controlled by receiving, from the untrusted device, an encrypted key value of a key and a representation of an index of a B-tree structure, decrypting, at the trusted device, the key and one or more encrypted index values, and initiating a transmission, a pointer value that identifies a lookup position in the index for the key. The index comprises secure, encrypted index values. Other optimizations for secure processing are also described, including controlling available computation resources on a secure trusted device in a DBMS and controlling transmissions of secure data that is communicated between a secure trusted device and an unsecure untrusted device in a DBMS.

Claims

1. A system comprising:

secure hardware;

at least one hardware device processor; and

a computer-readable storage medium storing executable instructions that, when executed, cause the at least one hardware device processor to;

receive, from an untrusted module, an encrypted search key value of a search key and a sorted vector representation of an index of a tree structure, the sorted vector representation of the index comprising encrypted key values;

using the secure hardware, decrypt the encrypted search key value to obtain a decrypted search key value;

using the secure hardware, perform a binary search over the sorted vector representation to identify a lookup position of the decrypted search key value in the sorted vector representation; and

provide an identifier of the lookup position to the untrusted module,

wherein the secure hardware is configured to;

perform the binary search by decrypting specific encrypted key values in the sorted vector representation that are used in comparison operations during the binary search; and

perform the binary search without decrypting at least some other encrypted key values in the sorted vector representation that are not used in the comparison operations during the binary search.

2. The system of claim 1, the identifier comprising a pointer value.

3. The system of claim 1, further comprising:

a bus connecting the at least one hardware device processor and the secure hardware.

4. The system of claim 3, wherein the bus comprises a Peripheral Component Interconnect Express bus.

5. The system of claim 1, wherein the encrypted search key value and the sorted vector representation are received in a single transmission from the untrusted module to the secure hardware.

6. The system of claim 1, wherein the executable instructions, when executed, cause the at least one hardware device processor to:

cache an unencrypted vector representation of at least part of the index at the secure hardware;

use the secure hardware to identify, in the cached unencrypted vector representation, another lookup position of another search key value in the index; and

transmit, to the untrusted module, another identifier of the another lookup position.

7. The system of claim 1, wherein the secure hardware comprises one or more stack machines.

8. The system of claim 7, wherein the executable instructions, when executed, cause the at least one hardware device processor to:

receive, from the untrusted module, an indicator identifying a particular stack program provided by the one or more stack machines, the particular stack program performing the binary search within the secure hardware.

9. The system of claim 1, wherein the secure hardware includes one or more field-programmable gate arrays (FPGAs).

10. The system of claim 1, wherein the secure hardware includes one or more field-programmable gate arrays (FPGAs) having respective FPGA cores and respective plaintext data caches storing decrypted versions of data corresponding to encrypted versions of data stored in the untrusted module.

11. A method comprising:

receiving, from an untrusted device, an encrypted search key value of a search key and a sorted vector representation of an index of a tree structure, the sorted vector representation of the index comprising encrypted key values;

using secure hardware, decrypting the encrypted search key value to obtain a decrypted search key value;

using the secure hardware, performing a binary search over the sorted vector representation to identify a lookup position of the decrypted search key value in the sorted vector representation, the performing the binary search comprising;

decrypting specific encrypted key values in the sorted vector representation that are used in comparison operations during the binary search; and

not decrypting at least some other encrypted key values in the sorted vector representation that are not used in the comparison operations during the binary search; and

transmitting the lookup position to the untrusted device.

12. The method of claim 11, further comprising:

identifying commonly-accessed index key vectors;

caching plaintext versions of the commonly-accessed index key vectors on the secure hardware; and

responding to queries directed to the commonly-accessed index key vectors using the cached plaintext versions.

13. The method of claim 11, further comprising:

decrypting the specific encrypted key values using the secure hardware as the specific encrypted key values are accessed during the binary search.

14. The method of claim 11, the untrusted device comprising a database management system.

15. The method of claim 11, the secure hardware comprising a field-programmable gate array (FPGA).

16. A system comprising:

a field-programmable gate array (FPGA);

at least one hardware device processor; and

a computer-readable storage medium storing executable instructions that, when executed, cause the at least one hardware device processor to;

obtain an encrypted search key value of a search key and a sorted vector representation of an index of a tree structure, the sorted vector representation of the index comprising encrypted key values;

provide the encrypted search key value and the sorted vector representation to the FPGA; and

receive, from the FPGA, an identifier of a lookup position of the search key in the sorted vector representation,

wherein the FPGA is configured to;

perform a binary search over the sorted vector representation to identify the lookup position, the binary search comprising;

decrypting specific encrypted key values in the sorted vector representation that are used in comparison operations during the binary search; and

not decrypting at least some other encrypted key values in the sorted vector representation that are not used in the comparison operations during the binary search.

17. The system of claim 16, wherein the executable instructions, when executed, cause the at least one hardware device processor to:

perform database concurrency control processing outside of the FPGA using encrypted data, the index identifying storage locations of the encrypted data.

18. The system of claim 16, wherein the executable instructions, when executed, cause the at least one hardware device processor to:

perform database recovery processing outside of the FPGA using encrypted data, the index identifying storage locations of the encrypted data.

19. The system of claim 16, wherein the executable instructions, when executed, cause the at least one hardware device processor to:

perform comparison, arithmetic, and cryptographic operations using the FPGA while performing database concurrency control processing outside of the FPGA.

20. The system of claim 16, wherein the executable instructions, when executed, cause the at least one hardware device processor to:

perform comparison, arithmetic, and cryptographic operations using the FPGA while performing database recovery processing outside of the FPGA.