PaperlayerView exact revision on arXiv

Source-linked AI summary

HardIDX: Practical and Secure Index with SGX

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

arXiv:1703.04583v1cs.CR

TL;DR

Encrypted search must balance efficient range queries with limited leakage, while existing hardware-based database approaches face scalability and security-analysis challenges. HardIDX uses SGX to search a B+-tree index and formally models side-channel leakage; it reports millisecond searches and scaling to almost arbitrarily large indices.

  • Problem

    Encrypted range-search schemes have struggled to combine practical search time with minimal leakage, while hardware-based database approaches have had scalability and formal leakage-analysis limitations.

    Source: §1 · p. 1

  • Method

    HardIDX uses SGX to run B+-tree search in a trusted enclave, with two constructions that manage the tree as a whole or load needed nodes on demand.

    Source: §1 · p. 2

  • Results

    HardIDX compares favorably with existing software- and hardware-based approaches, searches in a few milliseconds, scales to almost arbitrarily large indices, and leaks only access patterns.

    Source: §9 · p. 14

  • Takeaways & Limitations

    HardIDX is presented as a deployable encrypted-database index with a small trusted-code footprint and search support for values and ranges.

    Source: §1 · p. 2, §9 · p. 14

    Construction 1 is bounded by SGX enclave memory, and the active-attacker analysis assumes a mechanism ensures returned results are complete and query-matching.

    Source: §5.1 · p. 7, §5.3 · p. 9

Abstract

from arXiv · show

Software-based approaches for search over encrypted data are still either challenged by lack of proper, low-leakage encryption or slow performance. Existing hardware-based approaches do not scale well due to hardware limitations and software designs that are not specifically tailored to the hardware architecture, and are rarely well analyzed for their security (e.g., the impact of side channels). Additionally, existing hardware-based solutions often have a large code footprint in the trusted environment susceptible to software compromises. In this paper we present HardIDX: a hardware-based approach, leveraging Intel's SGX, for search over encrypted data. It implements only the security critical core, i.e., the search functionality, in the trusted environment and resorts to untrusted software for the remainder. HardIDX is deployable as a highly performant encrypted database index: it is logarithmic in the size of the index and searches are performed within a few milliseconds rather than seconds. We formally model and prove the security of our scheme showing that its leakage is equivalent to the best known searchable encryption schemes. Our implementation has a very small code and memory footprint yet still scales to virtually unlimited search index sizes, i.e., size is limited only by the general - non-secure - hardware resources.

1. INTRODUCTION

Existing encrypted-search schemes struggle to combine efficient range queries with low leakage, while hardware-based database approaches face resource, security-analysis, and code-footprint concerns. HardIDX uses SGX for search, offers two B+-tree constructions, and reports logarithmic search complexity, millisecond searches, and formally characterized leakage.

1. INTRODUCTION

  • Efficient range search remains difficult: prior linear-time schemes are slow, while polylogarithmic alternatives can leak plaintext order, search patterns, or range sizes.The cited lightweight-cryptography schemes still expose search pattern and range size, leaving minimal-leakage range search an open challenge.Source: §1 · p. 1
  • Prior SGX database approaches ran entire unmodified DBMSs in enclaves, did not formally model leakage, and faced enclave-memory and code-footprint limits.TEEs also interact with untrusted host resources, making leakage through those channels relevant to security.Source: §1 · p. 1
  • HardIDX supports single-value and range searches with a B+-tree index, and compares favorably with software- and hardware-based approaches in performance, storage, security, and scalability.The paper describes the index as directly deployable in an encrypted database.Source: §1 · p. 2
  • HardIDX provides two B+-tree management constructions and characterizes their side-channel access-pattern leakage, which differs only in granularity.One construction loads the whole tree; the other loads data on demand and has a small trusted code and memory footprint.Source: §1 · p. 2
  • The scheme has logarithmic index-size complexity, performs searches within a few milliseconds, and proves leakage comparable to the best known searchable-encryption schemes.The implementation and evaluation use two constructions designed for SGX to reduce the trusted computing base.Source: §1 · p. 2

2. BACKGROUND

The background introduces SGX as the trusted execution environment used by HardIDX and explains why its interaction with untrusted resources creates side-channel risks. It also identifies page-granular access traces as a way to observe enclave behavior.

2.1 Intel Software Guard Extensions (SGX)

  • SGX divides execution between an isolated enclave and an untrusted host process, protecting enclave data from other software, including privileged software.Enclave data outside the CPU package is encrypted and checked when loaded.Source: §2.1 · p. 2
  • Current SGX systems reserve 128 MB for enclave memory and metadata, with about 96 MB available as EPC; the OS can swap pages while SGX protects their integrity, confidentiality, and freshness.The OS manages enclave memory dynamically, including allocation and page swapping.Source: §2.1 · p. 2
  • SGX remote attestation measures enclave code and data, lets a remote party verify enclave creation, and supports establishing a secure channel.A hardware-backed signature authenticates the measurement.Source: §2.1 · p. 2

2.2 Side Channel Attacks

  • Side channels reveal sensitive information through observable processing effects; SGX's untrusted OS can trace enclave code and data accesses at page granularity.The cited SGX deterministic side channel can be used to extract sensitive information.Source: §2.2 · pp. 2–3

3. HIGH LEVEL DESIGN

HardIDX separates a trusted client, an untrusted SGX-enabled server, and an enclave within that server. The client encrypts and deploys an indexed dataset, then sends encrypted queries for enclave search under a model that includes observable side channels.

3.1 HardIDX Overview

  • The system has three entities: a trusted client, an untrusted SGX-enabled server, and a trusted enclave hosted by that server.The enclave performs the security-sensitive search functionality.Source: §3.1 · p. 3
  • The client encrypts B+-tree nodes and data values under separate keys, stores them at pseudorandom positions, and provisions the index key to the enclave over an attested secure connection.The setup is performed once; the client later sends randomized encrypted search queries.Source: §3.1 · p. 3
  • The enclave searches either a fully loaded tree or fetches missing nodes on demand, then returns result pointers; the untrusted component learns the result-set cardinality from that interaction.The untrusted part fetches encrypted values, which the client decrypts; plaintext values are never decrypted on the server.Source: §3.1 · p. 3

3.2 Assumptions and Attacker Model

  • The attacker controls system software and may observe external resource interactions, page-fault access patterns, and cache behavior inside the enclave.The attacker aims to learn the B+-tree structure and indexed order; physical hardware attacks and denial of service are out of scope.Source: §3.2 · pp. 3–4

4. NOTATION AND DEFINITIONS

The paper uses an ordered-key B+-tree whose leaves point to values, and defines encryption and a hardware-secured tree scheme for searching ranges. Its security model extends searchable-encryption leakage to account for secure-hardware interactions.

4.1 B+-tree

  • A B+-tree is a balanced n-ary search tree that indexes values by ordered keys, with internal nodes directing searches and leaves holding keys and value pointers.The constructions use unchained leaves because following leaf links during range queries would reveal relationships among leaves.Source: §4.1 · p. 4
  • The key domain may be any ordered domain with recognizable minimum and maximum elements, rather than a predefined integer range.The branching factor specifies the maximum number of pointers in a tree node.Source: §4.1 · p. 4

4.2 Probabilistic symmetric encryption:

  • The probabilistic authenticated symmetric encryption scheme provides confidentiality, integrity, and authenticity, and is required to be authenticated IND-CCA secure.The paper gives AES-128 in GCM mode as an example.Source: §4.2 · p. 4

4.3 Hardware Secured B+-tree (HSBT)

  • The Hardware Secured B+-tree scheme is defined as six algorithms for setup, encryption, token generation, decryption, and range search on untrusted and trusted hardware.Correctness requires returning exactly the values whose keys lie in the requested range.Source: §4.3 · p. 4
  • CKA2-HW-security extends searchable-encryption security with hardware leakage for secure-hardware inputs, outputs, and inherent leakage, evaluated through real and simulated games.The model assumes a passive attacker; the paper notes that an active attacker can thwart correctness, such as by dropping results.Source: §4.3 · pp. 4–5

5. SEARCH ALGORITHMS

This section describes two SGX-protected B+-tree constructions for logarithmic search, differing in which nodes are loaded and in their memory and access-pattern trade-offs. It also covers node-level access-pattern leakage, defenses that verify traversal and results, and concurrent queries by multiple users.

5. SEARCH ALGORITHMS

  • Both constructions use B+-trees for logarithmic search and SGX to protect data confidentiality and integrity.Construction 1 uses a random permutation of node positions and randomizes returned pointers and traversal order.Source: §5 · p. 5, §5.1 · pp. 5–6

5.1 Construction 1

  • Construction 1 loads and processes the B+-tree inside SGX, but stores encrypted values outside the enclave to reduce transfer overhead and fit its limited protected memory.The untrusted component receives pointers and retrieves the values; the paper states that randomized storage and authenticated IND-CCA encryption preserve their security.Source: §5.1 · p. 5
  • Although SGX protects enclave memory and the B+-tree, it does not fully protect access patterns; the assumed attacker can reveal accessed pages during B+-tree traversal despite operations executing only in protected memory.Source: §5.1 · p. 6

5.2 Construction 2

  • Construction 2 uses O(1) enclave memory for arbitrarily large trees by loading only needed encrypted nodes, batching transfers to reduce context switches, at the cost of node-level access-pattern leakage.The enclave processes up to maxAmount nodes per transfer, where maxAmount depends on reservedSpace; the construction is proved secure according to Definition 3.Source: §5.2 · pp. 7–8
  • Construction 2 decrypts transferred nodes inside the enclave, searches their keys, and returns matching pointers in random order; it is based on a textbook B+-tree traversal.The construction is stated to be correct according to Definition 2 and secure according to Definition 3.Source: §5.2 · p. 8
  • Construction 2 reveals node-level tree and value-pointer access patterns, whereas Construction 1 reveals page-level patterns through SGX.The difference is the granularity of the access pattern visible to the attacker.Source: §5.2 · p. 9

5.3 Active attacker

  • The active attacker can control encrypted data, tokens, and the untrusted search algorithm; deviations can harm correctness, while the analysis assumes clients receive complete, matching results.Authenticated encryption detects modifications or additions to static data and tokens; denial-of-service attacks are out of scope.Source: §5.3 · p. 9
  • The proposed mechanism avoids Merkle proofs’ extra transfer, sibling-access leakage, and client processing, as well as O(r) enclave storage for requested-node lists or result pointers.The secure-channel alternative for sending results would not add protection because untrusted software can observe data accesses.Source: §5.3 · pp. 9–10
  • Multiset hashes let the enclave verify expected nodes and let the client verify returned results, protecting against protocol deviations with O(1) additional enclave storage.The enclave compares hashes of expected and received node IDs, then returns an HMAC over result-value hashes for the client to check.Source: §5.3 · p. 10
  • About 0.3ms of overhead was measured for the active-attacker protections at a query result size of 100.Source: §5.3 · p. 10

5.4 Multiple users

  • Multiple users can query concurrently; each needs SKk to create tokens and SKv to decrypt results, and separate SKk keys can hide users’ search patterns from one another.Separate keys require client information accompanying each token so the enclave can select the decryption key.Source: §5.4 · p. 10

6. IMPLEMENTATION

The implementation addresses access-pattern and secret-key exposure across external-resource, page-fault, and cache-timing channels, while optimizing trusted/untrusted memory transfers and securely provisioning keys.

6. IMPLEMENTATION

  • The implementation uses the Intel SGX SDK, and SGX attestation establishes a secure channel for provisioning the enclave with the client’s secret key.The enclave creates a key pair, the client verifies the enclave measurement, and the enclave decrypts the provisioned key.Source: §6 · pp. 10–11
  • The implementation considers external-resource, page-fault, and cache-timing channels because each can expose memory access patterns that may reveal sensitive information.The attacker may seek information about the tree structure, value order, or cryptographic secrets.Source: §6 · p. 11
  • Construction 2 includes external B+-tree node accesses in its leakage; page faults add no information because nodes are smaller than pages and node accesses are already leaked.The page-fault channel observes accesses at a relatively coarse 4 kB granularity; Construction 1 explicitly accounts for tree-structure leakage through it.Source: §6 · p. 11
  • The implementation accesses every key and pointer, whether followed or not, to achieve data-independent accesses and thwart cache-timing side channels.The analysis considers an adversary able to observe accesses within a node.Source: §6 · p. 11
  • Leakage-resilient implementations and hardware features are used against key leakage; the AES implementation uses AES-NI to hold S-Boxes in CPU registers instead of RAM.The paper says this hampers cache side-channel attacks.Source: §6 · p. 11
  • Construction 2 batches requested nodes to reduce context switches and lets the enclave fetch, decrypt, and process nodes directly from host-process memory.The authors report this is more efficient than explicitly copying nodes into enclave memory first.Source: §6 · p. 11

7. PERFORMANCE EVALUATION

The evaluation compares two SGX constructions, their memory-management behavior, and Construction 2 against Logarithmic-URC. It reports query-time, scalability, storage, and leakage differences across these comparisons.

7.1 Construction 1 vs. Construction 2

  • Construction 1’s single enclave switch and one-time decryption contrast with Construction 2’s O(log_b n) switches and per-node decryption during queries.Construction 2 also transfers part of the B+-tree between trusted and untrusted code, whereas Construction 1 transfers the query and result set.Source: §7.1 · p. 11
  • Construction 2 is slower than Construction 1 by a small factor, while their runtimes converge as result-set size increases.The comparison holds the tree at 1,000,000 key-value pairs and varies the result-set size; the figure plots median runtime against result-set size.Source: §7.1 · pp. 11–12, Figure 5 · p. 11

7.2 Memory Management

  • Construction 2 is unaffected by paging and supports unlimited tree size; higher branching factors improve performance and bring its runtime closer to Construction 1.Construction 1’s runtime rises sharply above 10^6 records as SGX memory is exhausted and the operating system swaps pages.Source: §7.2 · p. 12

7.3 Comparison with related work

  • About a tenth of a millisecond for Construction 2, versus multiple milliseconds up to seconds for Logarithmic-URC, with moderate growth across tree sizes.The comparison used branching factor 100 and range queries containing 100 results; Table 1 presents the time comparison.Source: §7.3 · p. 12, Table 1 · p. 12
  • Unlike Logarithmic-URC, Construction 2 does not require a fixed search-key domain, and domain size does not affect its performance.Construction 2 requires O(n) index storage, compared with O(n log D) for Logarithmic-URC; Logarithmic-URC also leaks domain size, range size, and search pattern.Source: §7.3 · pp. 12–13

8. RELATED WORK

The related work covers searchable encryption, encrypted databases, and TEE-based systems. HardIDX is positioned against approaches with linear search, order leakage, access-pattern exposure, or constraints on deployment and scale.

8.1 Searchable encryption

  • Prior range-searchable schemes either have linear search time or, among earlier polylogarithmic approaches, reveal plaintext order; the paper presents HardIDX as the first polylogarithmic range scheme leaking only access patterns.The related-work discussion also notes a Lu implementation requiring seconds or minutes for a range search, even with a weaker security parameter.Source: §8.1 · p. 13

8.2 Encrypted Databases

  • Encrypted-database alternatives include schemes vulnerable to plaintext-recovery attacks and range-query systems with extra leakage, false positives, non-colluding-party requirements, or interactive rounds.The discussion identifies OXT-based approaches, encrypted bloom filters, ZeroDB, and Arx as examples with differing trade-offs.Source: §8.2 · p. 13

8.3 TEE-Based Applications

  • TEE-based alternatives leave gaps in leakage analysis or enclave scale: TDB does not address leakage or side channels, and Haven does not address access patterns and is limited by enclave size.The paper also contrasts its treatment of enclave interactions with VC3, which excludes information leakage from its adversary model.Source: §8.3 · p. 13

9. CONCLUSION

HardIDX uses SGX to search ranges and values over encrypted data as a secure database index. The paper reports a formal proof that includes side channels, favorable comparisons with existing approaches, millisecond searches on large data, and scaling to almost arbitrarily large indices.

9. CONCLUSION

  • HardIDX searches ranges and values over encrypted data using SGX, with a formal security proof that explicitly includes side channels.The paper reports few-millisecond searches on large data, almost arbitrarily large indices, access-pattern-only leakage, and a small trusted codebase.Source: §9 · p. 14
Loading 1703.04583v1…