Holepunch: Fast, Secure File Deletion with Crash Consistency

Holepunch: Fast, Secure File Deletion with Crash Consistency

Speakers: Zachary Ratliff; Wittmann Goh; Abe Wieland; James Mickens; Ryan Williams

Conference: IEEE S&P

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

Overview

In the realm of digital security and privacy, the concept of "deletion" often carries a misleading connotation. Users and businesses alike frequently operate under the assumption that deleting a file renders it permanently irrecoverable, yet the reality in modern computing environments is far more complex. This talk by Zachary Ratliff and his co-authors introduces Holepunch, a novel system designed to achieve truly secure and fast file deletion with per-file granularity, while also ensuring crash consistency. The work addresses critical shortcomings in existing file deletion mechanisms, which often leave sensitive data vulnerable to recovery by adversaries even after an explicit delete command.

Holepunch distinguishes itself by making no assumptions about the underlying storage device, a crucial factor given the intricacies of modern solid-state drives (SSDs) and their wear-leveling algorithms. By leveraging a sophisticated cryptographic primitive known as puncturable pseudo random functions (PPRFs), Holepunch provides a robust solution that is both cryptographically secure and highly efficient. The system is engineered to have a low memory footprint for key management and minimizes I/O operations, presenting a significant advancement over prior state-of-the-art approaches. This research is particularly pertinent in an era dominated by stringent data privacy regulations like GDPR and CCPA, where the ability to guarantee data erasure upon request is not just a user expectation but a legal mandate for businesses.

Background

▶ Watch: Introduction to secure file deletion challenge (0:00)

The problem of secure data deletion is deceptively complex, stemming from how file systems and storage devices handle data. Traditional file deletion methods, such as the rm command in Linux's ext4 file system, merely mark data blocks as free. The actual data persists on disk until it is overwritten by new information, leaving it susceptible to recovery by forensic tools. Even more "paranoid" methods like the shred command, which overwrites file data with zeros, prove insufficient on modern storage. Solid-state drives (SSDs), for instance, employ wear leveling techniques to distribute writes evenly across their memory cells, extending device lifespan. During this process, data might be copied from one physical location to another, with the original location marked free. A shred operation would only overwrite the new location, leaving the original data intact and recoverable at a different physical address. This inherent behavior of storage controllers makes achieving true secure deletion challenging without specific assumptions about the underlying hardware.

A standard, device-agnostic solution for secure deletion is cryptographic erasure. This technique involves encrypting all data stored on disk using a key held in a trusted storage area, such as a Trusted Platform Module (TPM) or a smart card. To "delete" data, one simply wipes the encryption key from this trusted storage. The data itself remains on disk, but becomes cryptographically unintelligible and unrecoverable, assuming the adversary is computationally bounded and cannot break the encryption. While effective for full-disk encryption, scaling this approach to support secure deletion at a per-file granularity introduces significant challenges, primarily related to key management. Storing hundreds of thousands of individual encryption keys for each file within a limited-capacity trusted storage component is impractical.

Prior research, notably the "Eraser" system by Onar, Cura, and Robertson, attempted to address per-file cryptographic erasure using a key tree data structure. This approach stored a single master key in trusted storage and used the key tree to recursively wrap keys along the path from the root to the leaves, where leaves represented per-file encryption keys. Deleting a file involved rotating and re-encrypting relevant keys within this tree. However, the key tree's size grows with the number of files, leading to trade-offs: storing it on disk incurred a logarithmic I/O cost for file access, while storing upper layers in memory improved performance but imposed a substantial memory overhead for cryptographic keys. Holepunch builds upon these foundations, aiming to overcome the limitations of key tree structures by introducing a more efficient and scalable cryptographic primitive.

Key Findings

▶ Watch: Prior cryptographic erasure and key tree challenges (4:00)

Holepunch's primary contribution is a robust, per-file secure deletion system that overcomes the limitations of previous cryptographic erasure methods, particularly regarding scalability and memory overhead, while also ensuring crash consistency. The core innovations and findings include:

1. Leveraging Puncturable Pseudo Random Functions (PPRFs): Holepunch introduces the use of a single puncturable pseudo random function (PPRF) key, encrypted under a master key stored in trusted hardware like a TPM. This PPRF efficiently generates unique per-file encryption keys based on a file's i-node number, effectively solving the "hundreds of thousands of keys" problem of traditional cryptographic erasure at per-file granularity.
2. Efficient Secure Deletion: When a file needs to be deleted, the PPRF key is "punctured" at the specific i-node number corresponding to that file. This operation renders the system unable to regenerate the file's encryption key, making the file data irrecoverable without affecting the keys for other, unpunctured files.
3. Low Memory Footprint: Unlike key tree approaches which can demand significant RAM for storing key structures (e.g., Eraser storing upper layers in memory), Holepunch maintains a remarkably low memory overhead. Benchmarks show it uses less than a gigabyte of RAM even for file systems as large as 32 terabytes, an order of magnitude improvement for large-scale deployments.
4. Crash Consistency: A critical advancement is Holepunch's implementation of crash consistency. Through a journaling scheme, the system synchronizes its on-disk state with the TPM, preventing key corruption and ensuring data integrity even during unexpected system failures. This was not guaranteed by some prior state-of-the-art tools.
5. Performance Parity: Despite its advanced security features, Holepunch demonstrates performance comparable to standard full-disk encryption solutions like DM-Crypt on Linux and prior secure deletion systems like Eraser across common file system workloads. While specific deletion operations, especially of random files, involve additional journaling steps that can incur a slight performance penalty, the overall overhead is minimal.
6. Device Agnosticism: Holepunch achieves secure deletion without making any assumptions about the underlying storage device or its controller behavior, effectively circumventing issues like SSD wear leveling that undermine traditional shred-like tools.

These findings collectively present a practical and scalable solution for secure file deletion, addressing both the technical challenges of modern storage and the growing demands for data privacy and compliance.

Technical Deep Dive

▶ Watch: Introducing Holepunch: fast, secure, crash-consistent deletion (5:40)

At the heart of Holepunch's secure deletion mechanism lies the puncturable pseudo random function (PPRF). A PPRF behaves like a standard pseudo random function (PRF), meaning its outputs are computationally indistinguishable from truly random values for any given input, provided the key is unknown. The crucial distinguishing feature is its puncturing operation. This operation allows an attacker (or the system itself, in this case) to "puncture" the PPRF key at a specific input point. The resulting punctured key can no longer evaluate the PRF at that punctured point, effectively "forgetting" how to generate the output for that specific input. Critically, the punctured key still allows evaluation of the PRF on all unpunctured points, producing the same outputs as the original key.

Holepunch leverages this property by storing a single PPRF key, encrypted under a master key held within a trusted hardware module like a TPM. To read or write a file, the PPRF key is first decrypted into memory. Given a file's unique i-node number, the PPRF is evaluated with this i-node number as input to generate a unique per-file encryption key. This key is then used to transparently encrypt file data before it is written to disk and decrypt it when read. When secure deletion is desired, the system performs the puncturing operation on the PPRF key, using the target file's i-node number as the puncturing point. This action permanently prevents the system from generating that specific file's encryption key. After puncturing, the master key is rotated, and the newly punctured PPRF key is re-encrypted and stored on disk under the new master key.

The specific PPRF construction employed by Holepunch is based on the Goldreich-Goldwasser-Micali (GGM) PRF. The GGM construction starts with a length-doubling pseudo random generator (PRG) and a uniformly random seed. By recursively applying the PRG to the left and right halves of its output, a binary tree is formed. The leaves of this tree correspond to the evaluation of the PRF on their respective indices, and the PRF's key is the initial random seed at the root of the tree. To extend this to a puncturable PRF, the puncturing operation works by identifying the leaf node corresponding to the input point to be punctured. It then gathers all the "neighboring" nodes along the path from this leaf up to the root. These collected nodes collectively form the punctured key. With this punctured key, all other leaves (unpunctured points) can still be evaluated, as their paths can be reconstructed using the collected neighboring nodes, but the path to the punctured leaf is broken. This GGM-based PPRF allows for fast evaluation, requiring only O(log N) evaluations of the underlying PRG, where N is the number of files.

A critical challenge with the GGM-based PPRF is that its key size grows by O(log N) bits with each file deletion, as more neighboring nodes are added to the punctured key. If left unchecked, this growth could eventually lead to an unmanageably large key. Holepunch addresses this with an ingenious layer of indirection. Instead of directly generating a file's encryption key from the PPRF and its i-node number, Holepunch stores blocks of file keys on disk. Each of these file key blocks is encrypted under a single key, which is generated by evaluating the PPRF on the block's unique tag value. This design enables an efficient refresh operation: when the PPRF key becomes too large due to numerous deletions, it can be rotated without needing to re-encrypt all the actual file data. Instead, the refresh only requires re-encrypting the much smaller file key table that maps block tags to their corresponding PPRF-derived keys. This layer also facilitates batch deletion, allowing multiple files within a single block to be securely deleted with just one puncture operation. The frequency of PPRF key rotations is a configurable parameter, offering a trade-off between memory overhead and the computational cost of refreshes.

For crash consistency, Holepunch implements a journaling scheme. This scheme ensures that the on-disk state of the file system, particularly the integrity of the PPRF key and file key table, remains synchronized with the TPM. This prevents corruption of cryptographic keys and loss of data integrity even in the event of unexpected system shutdowns or power failures. The detailed mechanics of this journaling are elaborated in the accompanying paper.

Demo / Proof of Concept

▶ Watch: The Puncturable Pseudo Random Function (PRF) explained (6:20)

The talk describes Holepunch's implementation as a block device driver, a common method for integrating file system-level security mechanisms directly into the I/O path. This allows Holepunch to transparently encrypt and decrypt all data as it is written to or read from disk, without requiring modifications to existing applications or the underlying file system structure. The implementation assumes the presence of a TPM (Trusted Platform Module) as the trusted storage component for the master key, though the design is adaptable to other trusted hardware like smart cards. While a live demonstration wasn't explicitly detailed in the transcript, the authors confirm the availability of their code for testing and evaluation, inviting others to "grab and test the code at the link below" (though a specific URL was not provided in the transcript).

Key aspects of the proof of concept and performance evaluation include:

• Memory Overhead: Holepunch demonstrates significantly lower memory consumption for storing and managing encryption keys compared to prior key tree-based systems like Eraser. For instance, even with infrequent refresh intervals, Holepunch uses less than a gigabyte of RAM, even when managing a file system as large as 32 terabytes. This represents a substantial improvement in scalability for large data deployments.
• Performance Benchmarks: The system was benchmarked against two significant baselines: Eraser, the prior state-of-the-art secure deletion tool, and DM-Crypt, the standard full-disk encryption solution on Linux (which does not support secure deletion).
• For common file system workloads (e.g., file creation, reads, writes), Holepunch performs similarly to both Eraser and DM-Crypt, indicating that its cryptographic overhead is well-managed and does not introduce significant performance bottlenecks.
• The only exception noted was a test involving the deletion of random files. In this specific scenario, Holepunch required "several additional journaling steps" to maintain crash consistency and prevent file loss during system crashes. This overhead led to a slight performance decrease compared to the baselines for that particular operation, but it is a deliberate trade-off for enhanced data integrity and reliability.

The robust implementation as a block device driver, coupled with compelling performance and memory efficiency benchmarks, validates Holepunch as a practical and effective solution for secure file deletion in real-world environments.

Defensive Implications

▶ Watch: Holepunch's mechanism for per-file key generation and deletion (7:00)

Holepunch offers profound defensive implications for individuals, enterprises, and cloud providers dealing with sensitive data. Its ability to provide fast, secure, and crash-consistent per-file deletion directly addresses several critical security and compliance challenges:

1. Regulatory Compliance: For businesses, Holepunch directly facilitates compliance with stringent data privacy regulations such as the General Data Protection Regulation (GDPR) and the California Consumer Privacy Act (CCPA). These regulations often include a "right to erasure" or "right to be forgotten," mandating that personal data be securely deleted upon user request. Traditional deletion methods are insufficient to meet this legal obligation, leaving organizations vulnerable to penalties and reputational damage. Holepunch provides a cryptographic guarantee of non-recoverability, enabling true compliance.
2. Mitigating Data Recovery Attacks: Holepunch effectively thwarts adversaries who gain complete access to a system, whether through network intrusion or physical seizure of storage devices. By cryptographically erasing data at the per-file level, the system ensures that even if an attacker bypasses file system permissions and accesses raw disk blocks, the deleted data remains unintelligible and unrecoverable. This is a significant improvement over methods like shred, which are easily defeated by modern storage behaviors.
3. Addressing SSD and Modern Storage Challenges: The system's device-agnostic approach is crucial for modern storage. SSDs' internal complexities, such as wear leveling, often create copies of data in different physical locations, making it impossible for OS-level overwrites to guarantee deletion. Holepunch bypasses these physical layer complexities by using cryptographic keys, ensuring that once a key is punctured, the data can no longer be decrypted, regardless of where it resides on the physical media.
4. Enhanced Data Lifecycle Management: For organizations handling various types of sensitive data (e.g., intellectual property, customer records, financial information), Holepunch enables more granular and secure data lifecycle management. Files can be confidently marked for deletion, knowing they will be truly erased and not linger on storage devices. This is particularly valuable in environments where data retention policies are strictly enforced.
5. Moving Beyond Inadequate Solutions: Holepunch highlights the inadequacy of relying solely on operating system commands like rm or even shred for secure deletion. It provides a robust, cryptographically sound alternative that security practitioners should consider as a foundational component for any system handling sensitive information, especially when data integrity and non-recoverability are paramount. Its implementation as a block device driver makes it a deployable solution that can integrate beneath existing file systems.

Key Takeaways

• Holepunch is a novel block device driver that provides fast, secure, per-file deletion with crash consistency, overcoming limitations of traditional methods and prior cryptographic erasure systems.
• It leverages puncturable pseudo random functions (PPRFs) to efficiently generate and manage per-file encryption keys, requiring only a single master key in trusted hardware like a TPM.
• The system achieves a significantly lower memory overhead for key management (sub-gigabyte for 32TB filesystems) compared to key tree-based approaches like Eraser.
• Holepunch performs comparably to standard full-disk encryption (DM-Crypt) and prior secure deletion tools across most file system workloads, demonstrating its efficiency and practicality.
• Its design is device-agnostic, effectively circumventing challenges posed by modern storage behaviors such as SSD wear leveling, which defeat simple data overwriting techniques.
• Holepunch is crucial for regulatory compliance (e.g., GDPR, CCPA) by enabling true "right to erasure" and ensuring data non-recoverability even against powerful adversaries with physical access.

About the Speaker(s)

The primary presenter for this work was Zachary Ratliff. He collaborated with a team of co-authors, including Wittmann Goh, Abe Wieland, James Mickens, and Ryan Williams. The transcript indicates Zachary Ratliff introduced himself as the main speaker. Beyond their names, specific titles or affiliations for the speakers were not provided within the scope of the presentation transcript.