Secure Deletion
In this project, we analyze solutions to the problem of secure deletion: how to make sensitive data unaccessible from a storage medium. In particular we provide methods to securely delete data from modern devices working at different levels (user-space, log-structured filesystems, flash memory, etc.).
We made the following proposals in regards of the secure deletion topic; further information and related publications are given below:
Secure Data Deletion from Persistent Media: A general approach to the design and analysis of secure deletion for persistent storage that uses encryption and key wrapping.
Systematization of Knowledge: Secure Data Deletion: A survey and comparision of secure deletion solutions.
Efficient Secure Deletion on Flash Memory: An efficient secure deletion solution for flash memory implemented for the flash file system UBIFS.
User-Level Secure Deletion on Log-Structured File Systems: Three solutions to address the problem of secure deletion on log-structured file systems such as YAFFS.
Members of the project:
- Joel Reardon, Hubert Ritzdorf, Claudio Marforio , Srdjan Capkun, David Basin
Secure Data Deletion from Persistend Media
We present a general approach to the design and analysis of secure deletion for persistent storage that relies on encryption and key wrapping. We define a key disclosure graph that models the adversarial knowledge of the history of key generation and wrapping. We introduce a generic update function and prove that it achieves secure deletion of data against a coercive attacker; instances of the update function implement the update behaviour of all arborescent data structures including B-Trees, extendible hash tables, linked lists, and others.
We implement a B-Tree instance of our solution. Our implementation is at the block-device layer, allowing any block-based file system to be used on top of it. Using different workloads, we find that the storage and communication overhead required for storing and retrieving B-Tree nodes is small and that this therefore constitutes a viable solution for many applications requiring secure deletion from persistent media.
Related publications:
Joel Reardon and Hubert Ritzdorf and David Basin and Srdjan Capkun
Secure Data Deletion from Persistent Media
Proceedings of the ACM Conference on Computer and Communications Security,
[DownloadPDF (PDF, 246 KB) | Downloadslides (PDF, 276 KB)]
Systematization of Knowledge: Secure Data Deletion
Secure data deletion is the task of deleting data irrecoverably from a physical medium. In the digital world, data is not securely deleted by default; instead, many approaches add secure deletion to existing physical medium interfaces. Interfaces to the physical medium exist at different layers, such as user-level applications, the file system, the device driver, etc. Depending on which interface is used, the properties of an approach can differ significantly.
We present the many dimensions of secure deletion, consolidating existing notions. We provide a common language to describe secure deletion that unifies the diverse efforts of many researchers and we survey and systematize the related work in detail. We present the approaches in terms of interfaces to physical media: what can be done to achieve secure deletion given a particular interface through which to achieve it? We present a taxonomy of adversaries with different capabilities - adversaries with different manners of access to the storage medium. We explain the relationships among adversaries such that an approach that defeats an adversary also defeats weaker ones; we perform a similar task for characteristics of secure deletion approaches, such as efficiency and granularity. We perform experiments to test a selection of approaches used in practice on a variety of file systems, examining corner cases such as block-unaligned truncations and sparse files. Finally, we analyze which approaches work and what are the best ways to develop a secure deletion solution.
Related publications:
Joel Reardon and David Basin and Srdjan Capkun
On Secure Data Deletion
IEEE Security & Privacy Magazine, May 2014
[DownloadPDF (PDF, 750 KB) | external pageofficial version]
Joel Reardon, David Basin, Srdjan Capkun
SoK: Secure Data Deletion
IEEE Symposium on Security and Privacy, San Francisco, California, 2013
[DownloadPDF (PDF, 163 KB) | Downloadslides (PDF, 222 KB)]
Efficient Secure Deletion on Flash Memory
Secure deletion on flash memory (ubiquitously used in portable devices) is not the straightforwards solution of overwriting data becuase flash memory prohibits in-place updates. Erasure of data happens at a much larger granularity (the erase block) and each erasure incurs some physical wear on the memory.
We present the Data Node Encrypted File System (DNEFS), which securely and efficiently deletes data on flash memory; it requires only a few additional erasures that are evenly distributed over the erase blocks. DNEFS encrypts each individual data node (i.e., the unit of read/write for the file system) with a different key, and then manages the storage, use, and purging of these keys in an efficient and transparent way for both users and applications. Data nodes are encrypted before being written to the storage medium and decrypted after being read, thus DNEFS's use of encryption is no different than any encoding applied by the storage medium (e.g. error correcting codes).
The keys are stored in a reserved area of the file system called the key storage area. Each flash erase block in the key storage area is periodically purged - a new version of the erase block is written where keys corresponding to deleted data nodes are replaced with fresh random data; the old version is deleted, which ensures that data nodes encrypted by these keys are now irrecoverable.
We design and implement an instance of our solution for the file system UBIFS and call our modification UBIFSec. UBIFSec provides a guaranteed upper bound on deletion latency, fine-grained deletion for truncated or overwritten files, runs efficiently and produces little wear on the flash memory. Our implementation is easy to integrate into UBIFS's existing Linux implementation, and requires no changes to the applications using UBIFS.
Related publications:
Joel Reardon, Srdjan Capkun, David Basin
Data Node Encrypted File System: Efficient Secure Deletion for Flash Memory
USENIX Security Symposium, Bellevue, Washington 2012 [DownloadPDF (PDF, 404 KB)]
UBIFSec Implementation:
Downloadkernel 3.2.1 patch (PATCH, 80 KB) (PATCH, 80 KB) | Downloadubifsec design doc (TXT, 18 KB)]
Secure Deletion on Log-Structured File Systems
We address the problem of secure data deletion on log-structured file systems. We focus on the YAFFS file system, widely used on Android smartphones. We show that these systems provide no temporal guarantees on data deletion and that deleted data still persists for nearly 44 hours with average phone use and indefinitely if the phone is not used after the deletion. Furthermore, we show that file over-writing and encryption, methods commonly used for secure deletion on block-structured file systems, do not ensure data deletion in log-structured file systems.
User-level solutions have very limited access to the flash storage medium. Such solutions can only create, modify, and delete the user's own local files. The principle behind our three solutions - purging, ballooning, and our hybrid solution - is that they reduce the file system's available free space to encourage more frequent garbage collection, thereby decreasing the deletion latency of deleted data.
Purging fills the storage medium to capacity, thus ensuring that no deleted data remains on the storage medium. Purging executes intermittently and halts after completion. It provides a guarantee of deletion but is inefficient for large storage media as the entire capacity must be filled.
Ballooning continually occupies some fraction of the storage medium's empty space with junk files to ensure the free space remains within a target range. This reduces the total number of erase blocks available for allocation, thereby reducing the expected data deletion latency; erase blocks with deleted data will be garbage collected earlier than before. It is well-suited for large storage media but it does not provide a guarantee of deletion.
Our hybrid solution combines both purging and ballooning to obtain the benefits of both approaches. At all times, ballooning is used to limit the amount of free space on the device. Periodically, purging is performed to obtain a guarantee of secure deletion. Moreover, as the space occupied by the ballooning files will not be erased, there are fewer erase blocks that need filling so purging is much quicker.
Related publication:
Joel Reardon, Claudio Marforio, Srdjan Capkun, David Basin
User-Level Secure Deletion on Log-structured File Systems
ASIACCS 2012, Seoul Korea
Secure Deletion in the News:
Schweizer Fernsehen Einstein show: external page9.6.2011