BULKOR: Enabling Bulk Loading for Path ORAM

BULKOR: Enabling Bulk Loading for Path ORAM

Speakers: Xiang Li, Yunqian Luo, Mingyu Gao

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=hlUXYyZtLt0

Overview

In an era where cloud computing is ubiquitous, the security of sensitive data processed in remote environments is a paramount concern. While Trusted Execution Environments (TEEs) like Intel SGX and AMD SEV offer hardware-backed isolation to protect data and code from a compromised host, they are not impervious to side-channel attacks, particularly those exploiting access patterns. This talk, "BULKOR: Enabling Bulk Loading for Path ORAM," presented by Xiang Li, Yunqian Luo, and Mingyu Gao, addresses a critical bottleneck in deploying Oblivious RAM (ORAM), a cryptographic primitive designed to hide access patterns, within these TEEs: the inefficiency of ORAM initialization, or "bulk loading."

The speakers highlight that while existing ORAM implementations for TEEs focus on optimizing individual access operations, the initial construction of the ORAM structure itself remains a significant performance hurdle. This slow initialization hinders the adoption of ORAM for various applications, including the construction of efficient oblivious algorithms and robust crash recovery mechanisms. BULKOR introduces a novel, theoretically sound, and practically efficient algorithm for bulk loading Path ORAM inside TEEs, achieving significant speedups and making ORAM-based privacy-preserving computations more viable and performant.

Background

▶ Watch: Introduction: ORAM, TEEs, and access pattern leakage (0:00)

The increasing reliance on cloud infrastructure for computation and storage raises significant privacy and security concerns. Users often outsource sensitive data and applications to cloud providers, who may themselves be compromised or subject to malicious internal actors. Trusted Execution Environments (TEEs), such as Intel SGX and AMD SEV, emerged as a hardware-based solution to this problem. TEEs create isolated enclaves where code and data can execute with strong confidentiality and integrity guarantees, even if the underlying operating system or hypervisor is malicious.

However, TEEs are not a panacea. They are known to be vulnerable to various side-channel attacks, where an attacker observes non-private information to infer sensitive data. A major category of these attacks targets access patterns – the sequence and timing of memory accesses. For instance, attacks like cache timing attacks, branch shadow attacks, and page fault attacks can reveal which memory locations are being accessed, even if the data itself remains encrypted within the TEE.

To counter access pattern leakage, Oblivious RAM (ORAM) was introduced. ORAM is a cryptographic primitive that transforms a program's memory access pattern into a sequence that is computationally indistinguishable from random, thus hiding the actual data access locations. Path ORAM is a widely adopted variant, organizing memory blocks into a tree structure. When a block is accessed, its entire path from the root to a leaf is fetched, and the block is then randomly reassigned to a new path to obscure its location. To handle blocks temporarily not on their assigned paths, a small client-side stash is used.

When ORAM is deployed within a TEE, an additional layer of security, known as double obliviousness, becomes necessary. This means not only must accesses to the ORAM server storage be oblivious, but also accesses to the ORAM controller structures (like the position map, which tracks block locations) residing within the TEE's memory must be oblivious. Existing solutions like Oblix and Zero Trees have focused heavily on optimizing the performance and security of ORAM accesses once the ORAM structure has been built.

Despite these advancements, the initial setup phase, or ORAM initialization (bulk loading), has remained largely unaddressed. The naive approach of inserting blocks one by one through the standard ORAM access protocol is prohibitively slow. The state-of-the-art ORAM initialization methods within TEEs also suffer from high complexity, creating a significant performance bottleneck. This slow initialization has several detrimental effects:

1. Hindering Oblivious Algorithms: Many oblivious algorithms (e.g., oblivious BFS) require building an ORAM structure upfront. If initialization is slow, the end-to-end performance suffers, potentially making the oblivious approach less attractive than simpler, but insecure, scanning methods for a small number of queries. The talk cited an oblivious BFS algorithm where initialization consumed one-third of the total execution time.
2. Impeding Crash Recovery: In systems that rely on ORAM, a crash might necessitate rebuilding the entire ORAM structure, leading to prolonged periods of system unavailability.
3. Increasing Cloud Storage Costs: ORAM structures are typically larger than their plain-text counterparts due to padding and overhead. If a system could efficiently switch between plain-text storage (when not actively accessed) and ORAM format (when frequent, oblivious access is needed), cloud storage costs could be reduced. However, slow initialization makes this impractical.

The core problem BULKOR tackles is the lack of an efficient, secure, and double-oblivious method for bulk loading Path ORAM within TEEs, which is crucial for making ORAM a practical and widely adopted privacy-preserving primitive.

Key Findings

▶ Watch: Motivation: Why ORAM initialization is a bottleneck (3:00)

BULKOR makes significant contributions to the field of oblivious computation within TEEs by providing a robust and highly efficient solution for ORAM bulk loading. The key findings and contributions can be summarized as follows:

1. Formal Definition of Bulk Loading: The authors formally define the bulk loading problem for ORAM, addressing the specific challenges of initializing an ORAM structure with a large set of blocks while maintaining security and performance within a TEE. This formalization provides a clear framework for future research in this area.
2. Improved Theoretical Time Complexity: BULKOR achieves a theoretical time complexity of O(N log N) for bulk loading N blocks. This represents a substantial improvement, saving an additional O(N log N) factor compared to prior state-of-the-art approaches for ORAM initialization inside TEEs. This theoretical efficiency translates directly into practical performance gains.
3. Exceptional Practical Performance: The practical evaluation of BULKOR on Intel SGX demonstrates dramatic speedups over existing ORAM implementations.

• In a single-threaded setting, BULKOR achieves up to 34x speedup over Zero Trees and 21x speedup over Oblix.
• In a 16-threaded setting, where BULKOR can leverage parallelism, the speedup is even more pronounced, reaching up to 160x over Zero Trees, largely because Zero Trees cannot be efficiently parallelized for initialization.

These figures highlight BULKOR's ability to overcome the initialization bottleneck in real-world TEE deployments.

1. Enabling More Efficient Oblivious Algorithms: BULKOR's accelerated initialization directly impacts the feasibility and performance of oblivious algorithms. The talk demonstrates this with a case study of an oblivious BFS (Breadth-First Search) algorithm. With BULKOR, the ORAM-based oblivious BFS algorithm can outperform custom, non-ORAM oblivious algorithms (like DOA) for denser graphs, shifting the efficiency trade-off point and making ORAM-based solutions more broadly applicable and performant.
2. Robust System Implementation: The work includes a thorough system implementation of BULKOR, which was used for practical performance evaluation. The re-implementation of Zero Trees in Rust for fair comparison further underscores the rigor of their evaluation methodology.
3. Double Obliviousness Guarantee: Throughout its design, BULKOR rigorously maintains the double obliviousness requirement, ensuring that both server-side storage accesses and TEE-internal ORAM controller structure accesses are hidden from a malicious host.

In essence, BULKOR transforms ORAM initialization from a major performance impediment into an efficient process, thereby broadening the applicability of ORAM in securing cloud computations and making privacy-preserving algorithms more practical for real-world scenarios.

Technical Deep Dive

▶ Watch: Insecurity of naive bulk loading approaches (6:00)

The core challenge addressed by BULKOR is the bulk loading of an ORAM structure, specifically a Path ORAM, within a Trusted Execution Environment (TEE), while maintaining double obliviousness. The goal is to take a set of N logical blocks, each with an address and data, and build a complete ORAM structure (including the stash, position map, and ORAM tree) by assigning physical addresses to all blocks (real and dummy blocks) and organizing them obliviously into the tree.

A straightforward, but flawed, approach might involve directly assigning a physical address to each block uniformly at random. However, this method cannot guarantee that each physical address will be unique, leading to collisions. Another intuitive approach is to randomly permute the input block array and then derive physical addresses based on their new positions. While this ensures unique physical addresses, it is problematic for ORAM. Path ORAM relies on leaf labels to determine the path a block belongs to. If physical addresses are determined first, the range of possible leaf labels for a block is restricted (e.g., a block at physical address 4 might only be assignable to leaf 0 or leaf 1). The speakers proved that this method of determining leaf labels based on pre-assigned physical addresses results in an insecure, non-uniformly random leaf label distribution, which violates ORAM's security guarantees.

BULKOR's key insight to overcome this security flaw is to reverse the dependency: instead of determining physical addresses first, it assigns leaf labels randomly to each block first, and then determines the physical address based on these assigned leaf labels. This ensures a consistent and secure leaf label distribution, as required by Path ORAM.

The BULKOR algorithm proceeds through several key steps:

1. Random Leaf Label Assignment: For each input block, a random leaf label is assigned. The design separates metadata (logical address, leaf label) from the actual data for performance optimization during metadata processing.
2. Initial Placement at Bottom Layer: Based on their assigned leaf labels, all blocks are conceptually placed at the bottom layer (leaves) of the ORAM tree. Each leaf corresponds to a bucket, and each bucket has a limited capacity (e.g., two slots per bucket).
3. Bucket ID Adjustment (The Core Mechanism): This is the most critical and complex step. It addresses the scenario where multiple blocks are assigned to the same leaf bucket, exceeding its capacity.

• If a bucket is over capacity, the "extra" blocks cannot stay at that leaf. They must be moved upwards along their assigned path towards the root until an empty slot is found in an ancestor bucket. This process is called bucket ID adjustment.
• The challenge is performing this adjustment obliviously. An attacker observing which buckets are checked for capacity or which blocks are moved would learn access patterns.

1. Oblivious Counter Management for Capacity Checking: To determine if a bucket has an empty slot, the system needs to maintain counters for each bucket, indicating its occupancy.

• A naive oblivious approach would be to scan all N bucket counters for every block placement and obliviously update the relevant one. This is prohibitively expensive, leading to an O(N^2) or O(N log N) factor for counter updates alone, making the overall process too slow.
• BULKOR introduces an optimized oblivious counter management strategy: instead of having a unique counter for every bucket, all buckets within the same layer of the ORAM tree share a common counter. This significantly reduces the number of counters that need to be scanned. For an ORAM tree with log N layers, there are only log N shared counters. When updating a counter, only these log N counters need to be scanned obliviously.
• If a counter indicates a bucket is full, the algorithm knows it must adjust the block's bucket ID upwards to the parent layer. This involves updating the counter of the upper layer.

1. Divergence Point Logic for Clearing Counters: When a block's path is adjusted upwards, it might move to a bucket that represents a different path segment than its original leaf. Consequently, some counters (representing buckets on the original path below the new position) should be cleared or become irrelevant.

• BULKOR determines which counters to clear by observing the binary representation of the original and new bottom bucket IDs. The difference between their binary representations indicates the layer from which the two paths diverge. All counters below this divergence point are then cleared. This ensures that only relevant counters are maintained and updated, and this determination is also performed obliviously with a single scan.

1. Final Physical Address Determination and Sorting: Once the final bucket ID (and thus physical address) for each block is determined through the oblivious bucket ID adjustment, the metadata is patched back together with its corresponding data. Finally, all blocks (metadata + data) are sorted in tandem according to their final physical addresses. This sorting step is also performed obliviously to prevent information leakage.

Through these meticulously designed steps, BULKOR constructs the entire ORAM tree, including the position map, while strictly adhering to the double obliviousness requirement. The use of shared counters and the divergence point logic are critical innovations that reduce the complexity of the bucket ID adjustment process to an efficient O(N log N), making bulk loading practical.

Demo / Proof of Concept

▶ Watch: BULKOR's core approach: assigning leaf labels first (7:00)

The talk presented a robust evaluation of BULKOR's practical performance, demonstrating its efficacy as a proof of concept for efficient ORAM bulk loading. The system was implemented and evaluated on Intel SGX, a prominent Trusted Execution Environment, using a single disk as the simulated non-volatile storage. This setup allowed for realistic assessment of BULKOR's performance in environments where TEEs are typically deployed.

To ensure fairness and provide meaningful comparisons, the researchers tested BULKOR against two state-of-the-art oblivious ORAM implementations: Zero Trees and Oblix. Notably, they re-implemented Zero Trees in Rust to guarantee a consistent and optimized baseline for comparison. The evaluation considered various settings, including different ratios of data cached in untrusted memory versus trusted memory, and adjusted for different ORAM tree sizes to ensure fair comparisons. It's important to clarify that the entire ORAM tree was not placed on disk during evaluation; rather, the top layers of the tree were cached in memory, and the in-memory ratio was adjusted to simulate different operational scenarios.

The results were compelling, showcasing BULKOR's significant performance advantages:

• Single-Threaded Performance: In a single-threaded execution environment, BULKOR achieved up to a 34x speedup over Zero Trees and a 21x speedup over Oblix. This demonstrates a substantial improvement even without leveraging parallel processing.
• Multi-Threaded Performance: When configured for a 16-threaded setting, BULKOR's performance gains were even more dramatic, reaching up to 160x speedup over Zero Trees. This stark difference highlights BULKOR's ability to be efficiently parallelized, a critical advantage over methods like Zero Trees which are less amenable to parallelization during initialization.

Beyond raw bulk loading performance, the talk also included case studies demonstrating how BULKOR enables more efficient oblivious algorithms. A particular focus was placed on an oblivious Breadth-First Search (BFS) algorithm. Two baselines were used:

1. DOA (Direct Oblivious Algorithm): A custom oblivious algorithm that does not use ORAM.
2. O-BFS (Oblivious BFS with ORAM): An existing oblivious BFS algorithm that uses ORAM.

The researchers designed a new algorithm with a separate initialization phase specifically suited for BULKOR's acceleration. The evaluation showed that for sparse graphs, DOA initially performed better than the ORAM-based algorithm when BULKOR was not enabled (i.e., with slow ORAM initialization). However, once BULKOR was integrated, the ORAM-based algorithm could perform significantly better, especially for denser graphs. This shift in the performance curve illustrates that BULKOR makes ORAM a viable and superior choice for a broader range of graph structures and other data-intensive oblivious algorithms, effectively expanding the practical utility of ORAM. The paper itself contains further detailed studies and analyses of these case studies.

Defensive Implications

▶ Watch: Efficient oblivious counter strategy for bucket occupancy (10:10)

The advancements introduced by BULKOR have profound defensive implications for organizations and developers leveraging Trusted Execution Environments (TEEs) for sensitive data processing. By significantly accelerating the bulk loading of Path ORAM, BULKOR addresses a critical bottleneck that previously limited the practicality and widespread adoption of ORAM-based privacy-preserving solutions.

Here are the key defensive implications:

1. Enhanced Practicality of ORAM in TEEs: The primary benefit is making ORAM a much more practical and viable defense against access pattern side channels in TEEs. Prior to BULKOR, the slow initialization overhead could deter developers from using ORAM, even if it provided superior security guarantees. With BULKOR's up to 160x speedup, the cost of setting up an ORAM is drastically reduced, lowering the barrier to entry for robust side-channel protection.
2. Improved System Resilience and Availability: For applications that require frequent ORAM rebuilding, such as those needing crash recovery or dynamic reconfigurations, BULKOR drastically cuts down the recovery time. This translates directly into higher system availability and resilience, crucial for mission-critical applications handling sensitive data in the cloud.
3. Wider Adoption of Oblivious Algorithms: BULKOR enables the efficient deployment of a broader range of oblivious algorithms. As demonstrated with the oblivious BFS example, applications that previously found ORAM initialization to be a performance bottleneck can now leverage ORAM to handle denser datasets or more complex computations obliviously, without compromising end-to-end performance. This expands the scope of privacy-preserving computation.
4. Cost Optimization for Cloud Storage: The ability to rapidly initialize and de-initialize ORAM structures could lead to more flexible storage strategies. Organizations might be able to switch between plain-text storage (when data is not actively being accessed obliviously, potentially reducing storage costs due to ORAM's overhead) and ORAM-protected storage (when frequent, oblivious access is required). BULKOR makes the transition to ORAM format fast enough to make such dynamic switching practical, potentially leading to cost savings on cloud storage services that charge by capacity.
5. Stronger Security Posture Against Sophisticated Attackers: By ensuring double obliviousness during bulk loading, BULKOR reinforces the overall security posture. It ensures that even during the setup phase, a malicious host cannot infer sensitive information from memory access patterns, including those related to the ORAM's internal controller structures within the TEE. This closes a potential window of vulnerability that might have been exploited by sophisticated attackers.
6. Foundation for Future ORAM Research and Deployment: BULKOR establishes a new baseline for efficient ORAM initialization, providing a robust component that future ORAM designs and applications can build upon. This accelerates research and development in secure computing, fostering innovation in privacy-preserving systems.

In essence, BULKOR strengthens the defensive capabilities of TEE-based systems by making the deployment of ORAM more practical, efficient, and robust, thereby safeguarding sensitive data against critical side-channel threats in cloud environments.

Key Takeaways

• ORAM initialization is a critical bottleneck: Traditional ORAM implementations, particularly within Trusted Execution Environments (TEEs), suffer from extremely slow initialization (bulk loading), hindering their practical deployment.
• BULKOR dramatically accelerates ORAM bulk loading: The proposed algorithm achieves a theoretical O(N log N) time complexity for N blocks, saving an additional O(N log N) factor over prior state-of-the-art methods.
• Significant practical performance gains: BULKOR demonstrates up to 34x speedup in single-threaded scenarios and an impressive 160x speedup in 16-threaded settings over existing ORAMs like Zero Trees and Oblix on Intel SGX.
• Enables efficient oblivious algorithms: By resolving the initialization bottleneck, BULKOR makes ORAM-based oblivious algorithms (e.g., oblivious BFS) more performant and practical, especially for denser datasets, expanding their applicability.
• Maintains double obliviousness: BULKOR rigorously ensures that both server-side storage accesses and TEE-internal ORAM controller structure accesses are hidden, upholding the crucial double obliviousness security requirement.
• Key technical innovations: BULKOR's efficiency stems from assigning leaf labels first, an oblivious bucket ID adjustment mechanism, and optimized oblivious counter management using shared counters per layer and divergence point logic.

About the Speaker(s)

Xiang Li is listed as a speaker from Shanghai University, and presented the talk. The transcript indicates his direct involvement in the research and presentation of BULKOR.

Yunqian Luo and Mingyu Gao are also listed as speakers on the paper. While the transcript does not provide specific biographical details or affiliations for Yunqian Luo or Mingyu Gao, their inclusion as speakers indicates their significant contributions to the BULKOR research and development.