Efficient Storage Integrity in Adversarial Settings

Quinn Burke, Ryan Sheatsley, Yohan Beugin, Eric Pauley, Owen Hines, Michael Swift, Patrick D. McDaniel

Overview

Securing untrusted cloud storage with Merkle trees typically involves a significant trade-off between system performance and security guarantees. This paper introduces Partially Asynchronous Integrity Checking (PAC), a hybrid approach that maintains synchronous read verification while processing write updates asynchronously in the background. PAC achieves up to a 5.5× speedup over state-of-the-art integrity trees, reaching 85% of the throughput of an AEAD-protected disk, while providing robust cryptographic protection against tampering and replay attacks.

The Challenge: Securing Untrusted Cloud Storage

In modern cloud environments, while compute resources can be secured using Trusted Execution Environments (TEEs) like AMD SEV-SNP, attached storage often remains outside the trust boundary. A malicious cloud provider or hypervisor could tamper with data or execute a replay attack, where the disk is rolled back to an older, potentially vulnerable state.

The threat model: A malicious cloud provider can record and replay disk blocks to roll back the system state.

To counter these threats, systems employ Merkle hash trees to ensure global transactional consistency and data freshness. However, the overhead of updating and verifying these trees on every I/O operation is prohibitive. Previous attempts to mitigate this through asynchronous batching of both reads and writes introduced a "window of vulnerability," where applications might act on malicious data before it is verified.

PAC: Partially Asynchronous Integrity Checking

PAC breaks the security-performance deadlock by splitting the integrity workload. Implemented as a Linux block device driver, it employs the following strategies:

  • Synchronous Reads: To eliminate the window of vulnerability, reads are never speculative. PAC immediately verifies a block's MAC against a pending update queue or the Merkle tree cache before returning data to the application.
  • Asynchronous Writes: Write operations are encrypted and MACed synchronously, but the Merkle tree update is deferred to a background thread via a shared queue in secure memory.
  • Update Overriding: PAC optimizes performance by overwriting pending updates in the queue if a block is written multiple times rapidly, leveraging the skewed nature of real-world workloads.
  • fsync Checkpointing: PAC ties state commitments to the fsync system call. This ensures that the Merkle root is securely sealed whenever an application requires durability, preventing long-term rollback vulnerabilities.

Evaluation and Performance

The authors evaluated PAC using synthetic storage workloads generated by fio (Flexible I/O Tester). They simulated real-world storage access patterns using Zipfian distributions across various disk capacities (up to 1 TB) and I/O sizes.

Aggregate read/write throughput comparison across different capacities and I/O sizes, showing the performance gap between AEAD and traditional integrity trees (DMT).

Key Results

  • Significant Throughput Gains: PAC delivers up to a 5.5× improvement in throughput and latency compared to Dynamic Merkle Trees (DMTs).
  • Near-Native Performance: With typical fsync frequencies, PAC achieves over 85% of the throughput of an AEAD baseline (encryption without Merkle tree integrity).
  • Scalability: Unlike previous designs that struggle with large datasets, PAC maintains its performance edge on disks up to 1 TB and with large I/O sizes (up to 256 KB).
  • Memory Efficiency: While PAC requires a small amount of extra memory for its update queue (about a 1.38× overhead per node compared to DMTs), it achieves peak performance with a drastically smaller hash cache.

Key Insights

  • Read Verification is Cheap: The authors discovered that synchronous read verification, when aided by a small hash cache (e.g., 0.1% of tree size), adds negligible latency (~2 µs). The primary bottleneck is the tree update process.
  • Exploiting Workload Skew: Real-world workloads are often highly skewed. PAC’s update queue allows it to "skip" intermediate updates for hot blocks, performing fewer total tree operations than strictly synchronous systems.
  • Natural Synchronization: Using fsync as a synchronization point aligns security commitments with application-level durability requirements, allowing PAC to hide update latency effectively in the background.

Limitations and Future Work

Current limitations include the complexities of crash recovery in a fail-stop model, particularly under adversarial conditions. Future research may explore "pipelined verification," where applications proceed with unverified data but are blocked from performing externally visible actions (like network requests) until verification is complete.

Summary updated

BibTeX
@inproceedings{burke2025efficient,
  author = {Quinn Burke and Ryan Sheatsley and Yohan Beugin and Eric Pauley and Owen Hines and Michael Swift and Patrick D. McDaniel},
  title = {{Efficient Storage Integrity in Adversarial Settings}},
  booktitle = {SP},
  year = {2025},
  doi = {10.1109/sp61157.2025.00196},
}

Loading related content...

Figure