HardIDX: Practical and Secure Index with SGX

Benny Fuhry, Raad Bahmani, Ferdinand Brasser, Florian Hahn, Florian Kerschbaum, Ahmad-Reza Sadeghi

Introduction

HardIDX is a high-performance encrypted database index designed to leverage Intel SGX for secure and efficient range searches. By isolating only the security-critical search logic within a Trusted Execution Environment (TEE) and employing an on-demand loading strategy, HardIDX maintains a minimal security footprint while scaling to handle massive datasets.

The Challenge of Secure Cloud Databases

Outsourcing sensitive data to the cloud offers scalability but introduces significant risks of data exposure. Current solutions generally fall into two categories:

  1. Software-based Searchable Encryption: Methods like Fully Homomorphic Encryption (FHE) provide strong mathematical security but are too slow for practical use. Faster "property-preserving" schemes often leak sensitive information, such as data order, making them vulnerable to inference attacks.
  2. Hardware-based TEEs (e.g., Intel SGX): Early attempts to use TEEs often involved placing an entire Database Management System (DBMS) into a secure "enclave." This results in a large Trusted Computing Base (TCB), increasing the attack surface. Additionally, SGX's limited Enclave Page Cache (historically ~96MB) leads to severe performance degradation when memory limits are exceeded.

HardIDX addresses these issues by optimizing for the "Goldilocks" zone: hardware-level speed, formal cryptographic security, and the ability to scale beyond memory constraints.

System architecture of HardIDX showing the interaction between the client and the SGX-enabled server.

System Design and Methods

HardIDX is built upon the $B^+$-tree data structure. The authors propose two primary constructions:

  • Enclave-Full (Construction 1): The entire $B^+$-tree is loaded into the SGX enclave. While extremely fast, it is constrained by the enclave's physical memory size.
  • On-Demand (Construction 2): This primary contribution loads only the necessary nodes for a specific search into the enclave. This ensures constant memory usage ($O(1)$) regardless of the total index size, effectively bypassing SGX memory limits.

Security Mechanisms

To ensure robustness against sophisticated attackers, HardIDX incorporates several key innovations:

Side-Channel Resistance: SGX is susceptible to "deterministic side channels" like page-fault or cache-timing attacks. HardIDX mitigates these by ensuring that every key and pointer within a node is accessed during a search. This uniform access pattern makes the enclave's internal behavior indistinguishable to an observer, regardless of the search query.

Illustration of side-channel threats (Cache and Page-Fault) within the SGX environment that HardIDX is designed to resist.

Active Attacker Defense: To prevent a malicious provider from omitting results or serving stale data, HardIDX utilizes multiset hashes (MSet-XOR-Hash). This allows the enclave to verify the integrity and completeness of the nodes provided by the untrusted host with minimal overhead (~0.3ms).

Randomized Storage: Tree nodes are stored at pseudo-random positions in untrusted memory, preventing attackers from reconstructing the tree structure based on memory access patterns.

Performance Evaluation

The system was evaluated on real Intel "Skylake" CPUs using synthetic datasets of up to 50 million key-value pairs. HardIDX was compared against Logarithmic-URC, a state-of-the-art software-based searchable encryption scheme.

Key Results:

  • Efficiency: A range query on 100,000 records takes only 0.125 milliseconds using the On-Demand construction.
  • Speedup: HardIDX is approximately 8,000 times faster than Logarithmic-URC for large datasets.
  • Scalability: Search times remained near-constant as the database grew, proving the effectiveness of the on-demand loading strategy in mitigating SGX memory constraints.

Conclusion and Future Work

HardIDX demonstrates that TEEs can provide practical, secure, and scalable indexing for cloud databases. By minimizing the TCB and optimizing memory usage, it achieves performance levels far exceeding software-only solutions. Future research may focus on integrating Oblivious RAM (ORAM) to further obscure access patterns and exploring the performance of high-frequency write operations in dynamic environments.

Summary updated

BibTeX
@inproceedings{fuhry2017hardidx,
  author = {Benny Fuhry and Raad Bahmani and Ferdinand Brasser and Florian Hahn and Florian Kerschbaum and Ahmad-Reza Sadeghi},
  title = {{HardIDX: Practical and Secure Index with SGX}},
  booktitle = {DBSec},
  year = {2017},
  doi = {10.1007/978-3-319-61176-1\_22},
}
Figure