BliMe: Verifiably Secure Outsourced Computation with Hardware-Enforced Taint Tracking

BliMe: Verifiably Secure Outsourced Computation with Hardware-Enforced Taint Tracking

Speakers: Hossam ElAtali

Conference: NDSS Symposium

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

Overview

The proliferation of outsourced computing, driven by its undeniable cost benefits and scalability, has introduced a fundamental challenge: maintaining the confidentiality of sensitive client data when processed by remote, potentially untrusted, cloud service providers (CSPs). As proprietary business logic and personal information increasingly reside on shared servers managed by third-party application software, concerns about malicious CSPs, compromised software, and sophisticated run-time or side-channel attacks have escalated. BliMe emerges as a groundbreaking solution to this critical problem, proposing a novel architecture that guarantees data confidentiality even in the face of such pervasive threats.

Presented by Hossam ElAtali at the NDSS Symposium, BliMe introduces a paradigm shift by leveraging minimal hardware changes to enforce stringent data confidentiality. Unlike prior approaches like Fully-Homomorphic Encryption (FHE) which suffers from "massive performance overheads" or hardware-assisted Trusted Execution Environments (TEEs) which have "repeatedly been shown to be vulnerable to run-time attacks" and offer "limited resistance to side-channel attacks," BliMe provides robust, verifiable security. It achieves this through a unique combination of Instruction Set Architecture (ISA) extensions for RISC-V, a dedicated encryption engine, and a minimal Hardware Security Module (HSM), all designed to implement a strict taint-tracking policy.

The significance of BliMe lies in its ability to offer strong security guarantees to multiple independent clients, without requiring them to trust the server software or even the operating system. Its protection extends comprehensively across various attack vectors, from malware and run-time exploits to all classes of side-channel attacks. By providing an efficient and provably secure foundation for outsourced computation, BliMe addresses a long-standing need in cloud security, promising to unlock new possibilities for privacy-preserving data processing.

Background

▶ Watch: Introduction and motivation for BliMe (0:00)

The modern computing landscape is heavily reliant on outsourced computation, where clients offload processing of their data to remote servers, often managed by third-party cloud service providers. This model, while economically attractive and scalable, fundamentally challenges data confidentiality. Clients must entrust their sensitive information—ranging from personal data to proprietary algorithms—to environments they do not fully control, opening the door to various attack scenarios. These include direct compromise by a malicious CSP, vulnerabilities within the server's application software, or sophisticated run-time and side-channel attacks designed to exfiltrate sensitive data.

Existing solutions to this problem have significant limitations. Fully-Homomorphic Encryption (FHE), for instance, allows computations directly on encrypted data, theoretically offering the strongest confidentiality guarantees. However, its practical deployment is severely hampered by "massive performance overheads," often "orders of magnitude worse than processing plaintext data directly," rendering it impractical for many real-world applications.

Another popular approach involves hardware-assisted Trusted Execution Environments (TEEs), such as Intel SGX or ARM TrustZone, embedded in modern CPUs. TEEs aim to create isolated execution environments for client applications, protecting them from the server's operating system and other co-located clients. A core feature of TEEs is remote attestation, which allows clients to cryptographically verify the integrity of the server's hardware and the software running within the TEE. Despite these isolation claims, TEEs have faced persistent security challenges. They have been "repeatedly shown to be vulnerable to run-time attacks" that can bypass client isolation, allowing adversaries direct access to sensitive data if software bugs are present in the attested code. Crucially, most TEE implementations offer "only limited resistance to side-channel attacks," as highlighted by research works such as [14], [15], and [45], meaning sensitive data can still be exfiltrated.

Side-channel leakage represents a particularly insidious threat. It occurs when an adversary infers information about sensitive data by observing unintended outputs of the system, even when the software is functionally correct and bug-free. These observable outputs can include execution time, memory access patterns, microarchitectural state (e.g., shared caches, branch predictors, performance counters), voltage fluctuations, and electromagnetic radiation [43, 32, 16, 37, 35, 29]. For example, if a conditional branch's path or execution time depends on a sensitive value, an adversary monitoring execution time can infer information. Similarly, using a sensitive value as a memory array index can leak information through observable cache access patterns. Modern CPUs, with their complex performance optimizations like speculation and out-of-order execution, unfortunately "amplify these leakage vectors" [36, 31, 52, 61, 46, 18, 10, 34, 12, 50, 69], making it exceedingly difficult for software developers to detect and mitigate side-channel leakage effectively.

BliMe targets a scenario where multiple clients send data to a remote server for outsourced computation, potentially involving untrusted third-party software. The primary Security Requirement (SR-Confidentiality) is that no party other than the originating client can infer anything about its sensitive input data beyond its length. This protection must hold against malware, malicious server software, and all side channels. The Performance Requirement (PR-Fast execution) demands that the design does not significantly degrade software performance. Finally, Backwards compatibility (CR-Backwards compatibility) is essential, ensuring that existing secure, side-channel-resistant software continues to function correctly.

Key Findings

▶ Watch: BliMe's novel approach and key contributions (2:00)

BliMe presents a suite of significant contributions to the field of secure outsourced computation, addressing the critical gaps left by prior approaches:

• Novel BliMe Architecture: The core contribution is the BliMe architecture itself, featuring a minimal set of Instruction Set Architecture (ISA) extensions for RISC-V. These extensions are meticulously designed to enforce a strict taint-tracking policy, which verifiably prevents the exfiltration of sensitive data.
• Integrated Hardware Security Module (HSM) and Encryption Engine: BliMe integrates a small, attestable, fixed-function Hardware Security Module (HSM) for remote attestation and key management, alongside a dedicated encryption engine. This combination ensures secure data import and export, crucially marking all decrypted data on the server side as tainted (or blinded) to prevent its leakage.
• Machine-Checked Security Proof: A foundational aspect of BliMe's security is a machine-checked security proof of its dataflow security. Applied to a simplified model ISA using the F* programming language, this proof formally verifies that the BliMe taint-tracking policy satisfies SR-Confidentiality, ensuring that visible and non-blinded states remain independent of blinded values.
• Practical RTL Implementation (BliMe-BOOM): To demonstrate practicality, BliMe-BOOM provides an RTL implementation of the ISA extensions, integrated into the speculative out-of-order RISC-V BOOM core. This implementation rigorously enforces taint propagation rules even during speculative execution, effectively preventing all known Spectre-type attacks.
• Comprehensive Performance Evaluation: Extensive performance evaluations of BliMe-BOOM reveal minimal run-time, power, and area overheads. Specifically, it shows less than 1.5% overhead in power consumption and under 9.0% in FPGA resource usage, with no significant reduction in maximum clock rate. Performance overhead for general computation is moderate, with 8% average overhead achievable with memory subsystem optimizations (e.g., a 1:8 tag-to-data ratio).
• Broad Attack Surface Mitigation: BliMe's design provides robust protection extending beyond traditional side channels to include malware and run-time attacks, without requiring trust in the server's OS or other software. It specifically prevents cache-timing, general timing, and transient execution attacks.
• Backwards Compatibility: The architecture maintains compatibility with existing side-channel-resistant cryptographic software, allowing well-tested secure code to run successfully within the BliMe environment.

These findings collectively demonstrate that BliMe offers an efficient, practical, and formally verified solution for guaranteeing data confidentiality in outsourced computing, significantly advancing the state of the art.

Technical Deep Dive

▶ Watch: Understanding side-channel leakage and its impact (4:00)

BliMe's technical approach centers on a robust hardware-enforced taint-tracking policy, designed to prevent sensitive data from ever flowing to an observable output.

System Overview and Adversary Model

The BliMe system enhances a standard CPU with two primary components: BliMe Extensions, which enforce the taint-tracking policy, and a BliMe Encryption Engine, responsible for secure data import and export. Complementing these is a separate, minimal, fixed-function Hardware Security Module (HSM) dedicated to remote attestation and key management, designed with a reduced attack surface.

The adversary model assumes a powerful attacker with "full control over all server software, including the OS." This adversary can make inferences based on side-channel information such as memory access patterns and instruction traces. Crucially, the server hardware, including the BliMe extensions, encryption engine, and HSM, is assumed to be implemented correctly. Attacks requiring physical access to the hardware (e.g., differential power analysis) are considered out of scope.

The BliMe Protocol

Secure outsourced computation with BliMe proceeds through a four-step atomic protocol:

1. Remote Attestation and Key Agreement: Before any data transfer, the client initiates a handshake with the HSM. The HSM attests to its genuineness (via an embedded hardware root-of-trust) and its proper integration with the server hardware and BliMe extensions. Upon successful attestation, the client and HSM establish a client-specific session key. The HSM then securely stores this key within the encryption engine, associating it with a unique blindedness tag that identifies the client. This entire process occurs over a secure, cryptographically implemented channel.

1. Data Import: The client encrypts its sensitive data using the agreed-upon session key and sends the ciphertext to the server. The server software then invokes the encryption engine's data import function. Atomically, the engine decrypts the ciphertext using the sealed session key and taints (or blinds) the resulting plaintext. This is achieved by attaching the unique blindedness tag to the data in registers and memory. A tag value of zero signifies unblinded (non-sensitive) data, while other non-zero values identify the data as blinded and indicate its source client (an n-bit integer, supporting 2^n - 1 clients).

1. Safe Computation: With the data now blinded, the server software performs the requested computation. Throughout this phase, the BliMe CPU extensions rigorously enforce the taint-tracking policy. Any operation that violates this policy, such as attempting to exfiltrate blinded data or allow it to influence observable outputs, will trigger a fault. The policy ensures that all intermediate and final results derived from blinded data consistently remain blinded, preventing any unintentional leakage.

1. Data Export: Once the computation is complete, the server software calls the encryption engine's data export function. The engine atomically encrypts the blinded results using the session key corresponding to their blindedness tag. Simultaneously, it unblinds the ciphertext by zeroing its tag. The server then transmits the encrypted results back to the client. This encryption must be robust against adaptive chosen-plaintext attacks to prevent an adversary from deducing information by observing ciphertexts.

Taint-Tracking Policy

The core of BliMe's security guarantees lies in its sophisticated taint-tracking policy, which governs the flow of data within the system.

System State Definition: BliMe categorizes system state into two types:

• Blindable State: This includes all values in cache lines, registers (excluding the program counter, PC), main memory, and all internal busses and queues used for value transfer. Each element of blindable state is augmented with a blindedness tag.
• Visible State: This encompasses information that may be exposed outside the system and, therefore, must never contain sensitive data. It includes microarchitectural state without a blindedness tag, such as the program counter, memory addresses, branch predictor state, and performance counters. The program counter is explicitly part of visible state because it directly controls program execution flow, meaning blinded data is strictly forbidden from affecting control flow.

Observable Outputs: The policy defines the following as observable outputs: visible state, non-blinded blindable state, memory operation addresses, instruction execution time, and fault signals. Outputs requiring physical access (e.g., voltage, electromagnetic radiation) are explicitly excluded from this model.

Taint-Tracking Policy Rules (as per Table I in the original work):

The policy's fundamental rules are:

• An instruction with a blinded input (i.e., a non-zero blindedness tag) will produce a blinded output, inheriting the same tag.
• If an instruction receives blinded data from multiple sources with different blindedness tags, it indicates a security domain mixing violation and raises a fault.
• Crucially, if an instruction attempts to affect any observable output (other than non-blinded blindable state) in a manner that depends on a blinded input, a fault is raised. This directly prevents the exfiltration of sensitive data.

Specifically, BliMe's policy provides protection against:

• Cache-timing side-channel attacks: Blinded values are strictly prohibited from being used as addresses for load or store operations.
• Timing attacks: Control flow decisions or the duration of variable-time instructions (e.g., division) cannot depend on blinded values. An adversary monitoring execution time would thus learn nothing about sensitive data.
• Transient execution attacks: Blinded values cannot influence speculation decisions (e.g., branch prediction). While speculatively executed instructions can process blinded values and maintain their tags, the underlying prediction logic cannot rely on them. This effectively blocks all speculative side channels.

It is important to note that the blindedness tag itself is not considered sensitive; thus, instructions can safely query whether a value is blinded.

BliMe-compliant Software

For software to operate securely within the BliMe environment, it must adhere to principles akin to constant-time coding [5], which are standard for side-channel-resistant cryptographic implementations. Specifically, BliMe-compliant software must not:

1. Use blinded data in control-flow decisions.
2. Use blinded data as a target address for jumps or branches.
3. Use blinded data as an address, offset, or index for memory operations.
4. Use blinded data as an operand for instructions with variable execution time (e.g., division).
5. Mix blinded data belonging to separate security domains (i.e., data with different blindedness tags).
6. Write blinded data to any peripherals like displays, network devices, or disk drives.

These restrictions, while strict, do not fundamentally limit computational power. BliMe permits conditional branching and indirect addressing on non-sensitive data and can simulate any finite-tape Turing machine, ensuring that it remains a powerful yet secure computational platform.

Demo / Proof of Concept

▶ Watch: Problem description and BliMe's security requirements (4:40)

To concretely demonstrate BliMe's practicality and efficacy on a complex, speculative computation platform, the researchers implemented BliMe in RTL (Register-Transfer Level) on the BOOM RISC-V core and the Chipyard System-on-Chip (SoC) framework. This implementation, named BliMe-BOOM, is crucial because it enforces taint propagation rules even during speculative execution, thereby effectively mitigating Spectre-type attacks [31].

Two variations of BliMe-BOOM were developed:

• BliMe-BOOM-1: Employs single-bit blindedness tags with byte-level granularity.
• BliMe-BOOM-8: Utilizes eight-bit blindedness tags with 8-byte (word-level) granularity.

The design leverages Chisel, a hardware construction language embedded in Scala. A key aspect of the implementation is the definition of a Blinded data type, which is a composition of a blindedness tag and a variable-length bit vector. This ensures that blinded values cannot be separated from their tags, preventing unintended leakage.

Architectural Changes

Significant architectural modifications were made across various components of the BOOM core:

1. Registers and ALU Operations: The register files were modified to store the new Blinded type, accommodating both data and its associated tag. ALU operations that read from a blinded register typically produce a blinded output. Exceptions exist for operations with constant results, such as XORing a register with itself, which always yields zero and thus an unblinded output.

1. Main Memory & Caches: A dedicated memory region was introduced to store blindedness tags, made inaccessible directly to software. Both the L1 data cache (L1D) and L2 caches were expanded to include tags alongside each data granule. The L1 instruction cache (L1I), however, does not store tags; any blinded values read into it are zeroed, and their 'valid instruction' metadata bits are unset, effectively preventing the execution of blinded code. L2 cache misses are translated into two separate main memory operations: one for data and one for tags. The researchers noted a limitation in Chipyard's TileLink implementation that restricted data reads to 8-word granularity, resulting in an effective minimum tag size of 64 bits for their current BliMe-BOOM, affecting memory optimization potential.

1. Pipeline Stages: Functional units within BOOM's pipeline were modified to propagate blindedness tags or raise a fault if an operation is deemed unsafe with blinded operands (e.g., memory address generation). Specifically, the memory address generation unit faults if blinded operands are used. Furthermore, if the page table walker encounters a blinded Page Table Entry (PTE), it zeroes the PTE before storing it in the Translation Lookaside Buffer (TLB), thereby preventing loads from blinded physical addresses.

1. Encryption Engine: The BliMe encryption engine is implemented as a ROCC accelerator [3, p. 3], utilizing a pipelined ChaCha20 stream cipher with a 19-cycle latency. It exposes atomic blind-and-decrypt and encrypt-and-unblind operations through reserved instruction opcodes, enabling its use with unmodified C compilers via RISC-V intrinsics.

1. Speculation: A critical aspect of BliMe-BOOM is its handling of speculative execution. Speculatively executed instructions are subjected to the exact same taint checks as non-speculative instructions. The branch prediction logic is designed never to depend on blinded data. This is achieved by blocking blinded data flows into the prediction logic, zeroing out blinded instructions in the instruction cache, and preventing any feedback from faulting branch decisions that might have been based on blinded data. This comprehensive approach is stated to block all speculative side channels, distinguishing it from prior work like Speculative Taint Tracking (STT) [68], as BliMe does not untaint data after speculative execution.

Handling Violations

Any violation of the strict taint-tracking policy—such as attempting to write blinded values to the program counter, using them in variable-time instructions, employing them as memory addresses, or writing them to unblindable memory locations (e.g., peripherals)—results in an illegal instruction fault. This fault mechanism provides immediate feedback and prevents any potential leakage.

For rapid testing and validation of these architectural changes, the researchers also implemented them in Spike [48], a C++ RISC-V ISA simulator.

Defensive Implications

▶ Watch: BliMe's system overview and design approach (6:00)

BliMe offers profound defensive implications for organizations and individuals concerned with data confidentiality in outsourced computing environments. Its hardware-enforced taint tracking fundamentally shifts the burden of security from fallible software to a provably secure hardware foundation, offering robust protection against a wide array of sophisticated attacks.

For Cloud Service Providers (CSPs):

• Enhanced Trust and Service Offering: CSPs can offer verifiably secure computation services, attracting clients with high-confidentiality requirements. BliMe provides a strong, attestable guarantee that client data remains confidential, even from the CSP's own software and administrators.
• Reduced Liability: By leveraging BliMe-enabled hardware, CSPs can mitigate risks associated with data breaches stemming from software vulnerabilities or side-channel attacks within their infrastructure.

For Clients and Data Owners:

• Guaranteed Data Confidentiality: Clients gain strong, formally verified assurance that their sensitive data, once imported and marked as blinded, cannot be exfiltrated by malicious server software, malware, or side-channel attacks. This addresses a critical trust gap in current cloud models.
• Protection Against All Side Channels: BliMe's design specifically targets and mitigates all known classes of side-channel attacks, including cache-timing, general timing, and transient execution (Spectre-type) vulnerabilities. This significantly reduces the attack surface that software developers typically struggle to defend against.
• Reduced Reliance on Software Trust: The protocol ensures security without requiring clients to trust the server's operating system or third-party application software, a significant improvement over TEEs which often require trust in a larger Trusted Computing Base (TCB).

For Software Developers:

• Simplified Secure Coding: While BliMe-compliant software must adhere to constant-time principles, the hardware inherently protects blinded data from side channels. This means developers can focus on the correctness of their algorithms without needing to meticulously audit every line of code for potential microarchitectural leakage when operating on sensitive data.
• Compatibility with Existing Secure Code: BliMe is designed to be compatible with existing side-channel-resistant cryptographic libraries (e.g., TweetNaCl), allowing developers to leverage well-tested and audited codebases.

Actions for Defenders:

1. Hardware Adoption: Organizations should advocate for and adopt hardware platforms incorporating BliMe or similar hardware-enforced taint-tracking extensions. This is the foundational step to leverage BliMe's security guarantees.
2. Protocol Adherence: Clients must meticulously follow the BliMe protocol, particularly the remote attestation and key agreement steps, to establish a secure session key and verify the presence of BliMe hardware.
3. Software Compliance: While BliMe protects data once blinded, the initial application logic that handles and transforms data before blinding, or after unblinding, must still be carefully developed to be BliMe-compliant (e.g., avoiding sensitive data in control flow if it's not yet blinded). Future compiler support, as noted in the talk, will greatly simplify this.
4. Orthogonal Defenses: It's crucial to acknowledge that BliMe, as presented, does not defend against attacks requiring physical access to the server (e.g., Rowhammer [30], power analysis [32], electromagnetic attacks [16, 37], or advanced voltage/frequency scaling attacks like Plundervolt [40]). Defenders must implement orthogonal physical security measures and consider other hardware-level protections for these specific threats.
5. Fault Handling: Developers of server-side applications must be aware of how BliMe handles policy violations (illegal instruction faults) and design their error reporting mechanisms to avoid leaking information through fault signals, especially if the fault's occurrence depends on a blinded value. The proposed future work of suppressing faults and setting a blinded bit in protected storage would address this.

In essence, BliMe provides a robust, efficient, and formally verified hardware mechanism to ensure data confidentiality in outsourced environments. It empowers defenders with a powerful tool to protect sensitive data against a broad spectrum of software and microarchitectural attacks, significantly raising the bar for cloud security.

Key Takeaways

• Verifiably Secure Confidentiality: BliMe introduces a novel architecture with RISC-V ISA extensions and hardware-enforced taint tracking, providing strong, formally verified confidentiality for outsourced computation against malicious software and side-channel attacks.
• Addresses Limitations of FHE and TEEs: It overcomes the performance impracticality of FHE and the side-channel/software vulnerability limitations of TEEs by offering efficient hardware-level protection.
• Minimal Hardware Overheads: The BliMe-BOOM RTL implementation demonstrates exceptional efficiency with less than 1.5% power consumption overhead, under 9.0% FPGA resource usage, and no reduction in maximum clock frequency.
• Practical Performance with Optimization: While initial overheads were 23-25%, memory subsystem optimizations (e.g., a 1:8 tag-to-data ratio) can reduce performance overhead to a practical 8% on average.
• Comprehensive Side-Channel and Transient Execution Mitigation: BliMe's strict taint-tracking policy prevents blinded data from influencing control flow, memory addresses, variable-time instructions, and speculative execution, effectively blocking all known classes of side-channel and Spectre-type attacks.
• Compatible and Future-Proof: BliMe maintains compatibility with existing side-channel-resistant code and lays the groundwork for future compiler support to further simplify the development of secure, BliMe-compliant applications.

About the Speaker(s)

Hossam ElAtali is a researcher who presented BliMe: Verifiably Secure Outsourced Computation with Hardware-Enforced Taint Tracking at the NDSS Symposium. Based on the detailed technical content of the talk, his work focuses on advancing hardware security and privacy, particularly in the challenging domain of outsourced computation. His expertise lies in designing novel architectures, such as BliMe, that leverage minimal hardware modifications to provide strong, formally verifiable security guarantees against sophisticated threats like side-channel and transient execution attacks, thereby addressing critical limitations of existing trusted execution environments.