Software-Based Memory Erasure with Relaxed Isolation Requirements

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 the memory on a given device 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 two 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.

The Challenge of Remote Memory Erasure

Internet of Things (IoT) devices are notoriously vulnerable to malware. A pragmatic way to recover an infected device is "secure erasure"—wiping its memory to return it to a known clean state. To do this remotely, researchers use Proof of Secure Erasure (PoSE) protocols. In these protocols, a verifier asks a prover (the device) to prove its memory is filled with fresh, random data.

However, existing software-based PoSE protocols suffer from a critical "Achilles' heel": the isolation assumption. If an infected device can communicate with an external conspirator, it can "outsource" the proof. The conspirator stores the required random data and computes the answers, while the device keeps the malware hidden in its own memory. Traditionally, researchers assumed that physical isolation—using jamming or Faraday cages—was mandatory to prevent this, making real-world deployment impractical.

Comparison between the traditional absolute isolation model (left) and the proposed distant attacker model (right).

Shifting the Paradigm: The Distant Attacker Model

This research, presented by teams from the University of Luxembourg and Rovira i Virgili University, proposes shifting from "absolute isolation" to a more realistic "distant attacker" model. The core idea is to replace expensive physical shielding with the laws of physics, specifically the speed of light, through two main pillars:

  1. Distance Bounding (DB): The verifier measures the Round-Trip Time (RTT) of challenge-response pairs. If the response arrives within a very tight time window ($\Delta$), the answer must have been computed locally, as there wasn't enough time to send the challenge to a distant attacker and receive a reply.
  2. In-Place Depth-Robust Graphs: To make the proof efficient, the prover computes labels for a Directed Acyclic Graph (DAG). The authors designed a new family of "in-place" graphs that can be labeled using almost no extra memory beyond what is being erased—a necessity when the goal is to fill the entire memory. Depth-robustness ensures that if a prover tries to cheat by not storing labels, recomputing them on-the-fly takes longer than the allowed time window $\Delta$.

Proposed Protocols and Performance

The paper introduces two protocols, referred to as Protocol V and Protocol VI in comparative analysis:

  • Unconditional PoSE-DB (Protocol V): Simple but requires high bandwidth, sending a random string as large as the memory ($O(n)$).
  • Graph-based PoSE-DB (Protocol VI): Low bandwidth, sending a small seed ($O(1)$) and relying on the hardness of recomputing graph labels.
Comparison of PoSE protocols showing that the proposed methods (V and VI) are the only ones to achieve security without isolation or specialized hardware while maintaining efficient communication.

As shown in the comparison table, the proposed protocols are the first to succeed without requiring isolation or specialized hardware. In a prototype implementation using Python and C, erasing 32KB of memory took only 0.25 seconds. For a high-security 128-round protocol, the estimated execution time is roughly 10 seconds over Bluetooth.

Conclusion and Future Work

By leveraging physics as a security layer, this work makes software-based erasure viable for low-end IoT devices that lack "Secure Elements" or TPMs. While a tiny fraction of memory theoretically remains available to an attacker (the "small part" gap), these protocols represent a significant step toward practical, remote malware recovery. Future research will focus on closing this memory gap and addressing potential timing jitter in various IoT communication protocols.

Summary updated

Abstract

A Proof of Secure Erasure (PoSE) is a communication protocol where a verifier seeks evidence that a prover has erased the memory on a given device 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 two 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}},
  booktitle = {CSF},
  year = {2024},
  url = {https://openreview.net/forum?id=jDonLDxCGO},
}
Figure