TL;DR
This paper introduces NFPS (NAND Flash Partial Scrubbing), a novel method for securely deleting data from flash memory that not only removes the data but also conceals the history of deletion. This is crucial because traditional secure deletion methods leave artifacts that can be exploited by adversaries.
What Problem Does This Paper Address?
Modern computing systems, especially those using flash memory (like SSDs, smartphones, and USB drives), face a significant challenge in securely removing data. When data is "deleted" through conventional means, its remnants often persist in the storage medium. This can happen because file systems typically only update metadata, leaving the actual data intact. Existing secure deletion techniques, such as overwriting or encryption, are often insufficient. Overwriting can be difficult and expensive on flash memory due to its erase-before-write nature and limited program-erase cycles. Encryption can be effective, but the very act of deletion can leave "artifacts" – traces in the storage layout that an adversary can analyze to infer information about the deleted data, potentially even recovering it or learning that a deletion occurred. The goal is to achieve "undetectable secure deletion" (SDG), meaning data is truly gone, and there's no evidence it was ever there.
Methods
The core innovation is NAND Flash Partial Scrubbing (NFPS), which operates at the Flash Translation Layer (FTL) – the firmware that bridges the gap between the logical block interface and the physical NAND flash. NFPS tackles the problem from a new angle by focusing on concealing deletion history rather than just overwriting data.
Key techniques include:
- Partial Scrubbing: Instead of completely overwriting a page with zeros (full scrubbing), which itself can be an artifact, NFPS modifies only a portion of the bits in a deleted page. This ensures the data is unrecoverable but doesn't create a "zero page" that signals deletion. This is achieved through:
- Partial Page Reprogramming (PPR): By reducing the page program time below the standard duration, only a subset of "1" bits are programmed to "0". The exact parameters (time and number of operations) are determined algorithmically to minimize time while ensuring bits flip.
- Partial Block Erasure (PBE): Similarly, by reducing the block erase time, only a portion of "0" bits are reset to "1", preventing a fully "1" block from indicating deletion.
- Eliminating Leakage from Mappings: FTLs maintain mappings between logical and physical addresses. When data is deleted, these mappings are removed, which is itself an artifact. NFPS addresses this by encrypting these mappings with a secret key derived from the user's login password. This makes the mappings appear as random data to an adversary without the key.
- Eliminating Leakage from ECCs: Error Correction Codes (ECCs) are used to detect and correct errors. Partial scrubbing can corrupt ECCs, signaling a deletion. NFPS masks the ECC parity with the secret key, making it impossible for an adversary to distinguish between a corrupted ECC (due to deletion) and a legitimate one.
NFPS is integrated into FTLs by modifying the write operation. When a page/block is invalidated (marked for deletion), NFPS performs partial scrubbing on it before it's potentially reclaimed by garbage collection.
Datasets
Not discussed in the paper. The evaluation uses actual NAND flash chips from various manufacturers.
Key Insights and Ideas
- Deletion History is a Leakage Vector: The most significant insight is that simply overwriting data isn't enough; the process of deletion leaves traces. Traditional secure deletion methods fail because they don't hide the fact that a deletion occurred.
- FTL is the Sweet Spot: The FTL is an ideal place to implement secure deletion because it's a common layer across many flash devices, and modifying it can affect all higher-level file systems without requiring changes to them.
- Partial Scrubbing is Key: The idea of "partial" modification, rather than complete erasure or overwriting, is crucial for avoiding obvious deletion artifacts like zero pages or fully erased blocks.
- Encryption and Masking for Metadata: The problem isn't just about data content; metadata (mappings, ECCs) also leaks information. Encrypting mappings and masking ECCs are clever ways to hide these traces.
- MLC Flash Complexity: Multi-Level Cell (MLC) flash, which stores more bits per cell, presents greater challenges due to "paired-page effects" where modifying one page can impact another, requiring more complex handling.
Key Results
- Undetectable Secure Deletion Achieved: NFPS successfully removes data and conceals deletion history, satisfying the security definition (p → 0, where p is the probability of detecting a deletion).
- Performance Impact: NFPS introduces a performance overhead, particularly for write operations.
- For SLC chips, the degradation was modest (around 1.6x to 2.8x slower writes depending on the FTL type).
- For MLC chips, the degradation was more significant (around 2.2x to 5.2x slower writes), especially for block mapping and FAST hybrid mapping FTLs, due to the need for data copying and more complex operations.
- Reliability: Partial scrubbing did not cause errors in SLC chips. For MLC chips, it could cause errors in adjacent pages, requiring additional handling (copying valid data and then partially erasing). Partial block erasure did not introduce errors in either SLC or MLC chips.
Limitations and Future Work
- Performance Overhead: The primary limitation is the performance degradation, especially for write-intensive workloads on MLC flash.
- Complexity in MLC: Handling paired-page effects in MLC flash adds complexity to the implementation.
- Future Work: The authors suggest defending against more powerful attackers who can perform on-line attacks (accessing the device while it's running). They also note that the current work focuses on block-based devices and doesn't address file-system-level deletion directly. The paper also mentions that the security of the encryption and masking relies on the secrecy of the key, which is derived from the user's password.
Summary updated