Software-Based Memory Erasure with relaxed isolation requirements: Extended Version

Sergiu Bursuc, Reynaldo Gil Pons, Sjouke Mauw, Rolando Trujillo-Rasua

Abstract

A Proof of Secure Erasure (PoSE) is a communication protocol where a verifier seeks evidence that a prover has erased its memory within the time frame of the protocol execution. Designers of PoSE protocols have long been aware that, if a prover can outsource the computation of the memory erasure proof to another device, then their protocols are trivially defeated. As a result, most software-based PoSE protocols in the literature assume that provers are isolated during the protocol execution, that is, provers cannot receive help from a network adversary. Our main contribution is to show that this assumption is not necessary. We introduce formal models for PoSE protocols playing against provers aided by external conspirators and develop three PoSE protocols that we prove secure in this context. We reduce the requirement of isolation to the more realistic requirement that the communication with the external conspirator is relatively slow. Software-based protocols with such relaxed isolation assumptions are especially pertinent for low-end devices, where it is too costly to deploy sophisticated protection methods.

Introduction

Internet of Things (IoT) devices are increasingly integrated into critical infrastructure, yet they remain notoriously susceptible to malware. Once a device is compromised, restoring it to a known clean state is difficult. Proof of Secure Erasure (PoSE) protocols offer a solution: they allow a controller (the verifier) to confirm that a device (the prover) has overwritten its entire memory with random data, effectively wiping any resident malware.

Historically, software-only PoSE protocols have relied on a fragile assumption: isolation. They assumed the device was physically unable to communicate with external systems during the proof. If a compromised device could outsource the proof's computation to a nearby, more powerful computer, it could fake the erasure while keeping the malware hidden. Enforcing such isolation in the real world—for example, by using Faraday cages or signal jamming—is impractical for most IoT deployments. This research proposes a way to move PoSE from controlled labs to the real world by relaxing these isolation requirements.

The Distant Attacker Model

The core innovation of this work is the shift from physical isolation to a temporal constraint. Instead of assuming the device cannot talk to anyone, the authors propose a model where the device cannot talk to anyone fast enough to cheat.

The Distant Attacker model: The verifier interacts with a local device while ensuring it does not receive help from a distant attacker by monitoring communication latency.

In this "Distant Attacker" model, the adversary is split into two components: a local, potentially compromised device ($A_1$) and a distant conspirator ($A_0$) with unlimited resources. By integrating distance-bounding techniques, the verifier measures the Round-Trip Time (RTT) of challenges. If the response arrives within a very tight time window, the verifier can be mathematically certain that the response was computed locally, as the speed of light limits how quickly a distant attacker could receive the challenge and return an answer.

PoSE-DB: Protocol Mechanism

The authors introduce PoSE-DB (Proof of Secure Erasure with Distance Bounding), which structures the erasure process into three distinct phases: Initialization, Interaction, and Verification.

The PoSE-DB protocol sequence, showing the timing-critical interactive phase where the verifier measures round-trip time to ensure local computation.
  1. Initialisation Phase: The verifier sends a seed or nonce to the prover, which uses it to begin the memory-filling process.
  2. Interactive Phase: This is the timing-critical component. The verifier sends a series of $r$ challenges ($x_i$). For each challenge, the verifier starts a high-precision clock ($t_i^b$) and stops it ($t_i^e$) upon receiving the response ($y_i$).
  3. Verification Phase: The verifier checks that all responses are correct and, crucially, that the time elapsed for every round ($t_i^e - t_i^b$) is less than a predefined threshold $\Delta$. If the device is too slow, the proof is rejected.

In-Place Graph Labeling

To ensure that all memory is erased, the protocol itself must not occupy significant space. The researchers developed a new family of depth-robust graphs designed for "in-place" labeling. This allows the device to compute the proof using only a tiny, constant amount of memory overhead. By minimizing the "clean gap"—the memory occupied by the protocol code and variables—the verifier can be confident that virtually 100% of the RAM has been overwritten.

Key Results and Practicality

The proposed protocols were evaluated through a prototype implementation in Python and C, yielding promising results for low-end hardware:

  • Efficiency: The graph-labeling program required only 3.4KB of storage.
  • Performance: Erasing 32KB of memory took approximately 0.25 seconds on a standard desktop environment.
  • Real-World Feasibility: Based on existing Bluetooth distance-bounding research, the authors estimate that a 128-round fast phase would take roughly 10 seconds in a typical deployment, providing a high level of security without specialized hardware.

Conclusion

By replacing the requirement for physical isolation with the more realistic constraint of communication latency, this work significantly lowers the barrier for deploying secure erasure protocols. PoSE-DB provides a robust, software-based defense mechanism for IoT devices, ensuring they can be reliably "cleaned" even in the presence of sophisticated, distant adversaries. Future work will focus on refining hardware timing consistency to prevent false negatives in diverse IoT environments.

Summary updated

Abstract

A Proof of Secure Erasure (PoSE) is a communication protocol where a verifier seeks evidence that a prover has erased its memory within the time frame of the protocol execution. Designers of PoSE protocols have long been aware that, if a prover can outsource the computation of the memory erasure proof to another device, then their protocols are trivially defeated. As a result, most software-based PoSE protocols in the literature assume that provers are isolated during the protocol execution, that is, provers cannot receive help from a network adversary. Our main contribution is to show that this assumption is not necessary. We introduce formal models for PoSE protocols playing against provers aided by external conspirators and develop three PoSE protocols that we prove secure in this context. We reduce the requirement of isolation to the more realistic requirement that the communication with the external conspirator is relatively slow. Software-based protocols with such relaxed isolation assumptions are especially pertinent for low-end devices, where it is too costly to deploy sophisticated protection methods.
BibTeX
@inproceedings{bursuc2024software,
  author = {Sergiu Bursuc and Reynaldo Gil Pons and Sjouke Mauw and Rolando Trujillo-Rasua},
  title = {{Software-Based Memory Erasure with relaxed isolation requirements: Extended Version}},
  booktitle = {CSF},
  year = {2024},
  url = {https://openreview.net/forum?id=jDonLDxCGO},
}

Loading related content...

Figure