Proof of secure erasure

In computer security, proof of secure erasure (PoSE) or proof of erasure[1] is a remote attestation[2] protocol, by which an embedded device proves to a verifying party, that it has just erased (overwritten) all its writable memory. The purpose is to make sure that no malware remains in the device. After that typically a new software is installed into the device.

Overview

The verifying party may be called the verifier, the device being erased the prover. The verifier must know the device's writable memory size from a trusted source and the device must not be allowed to communicate with other parties during execution of the protocol, which proceeds as follows. The verifier constructs a computational problem, which cannot be solved (in reasonable time or at all) using less than the specified amount of memory, and sends it to the device. The device responds with the solution and the verifier checks its correctness.[3]

Protocol constructions

Naive approach

In the simplest implementation the verifier sends a random message as large as the device's memory to the device, which is expected to store it. After the device has received the complete message, it is required to send it back. Security of this approach is obvious, but it includes transfer of a huge amount of data (twice the size of the device's memory).[3]:15

This can be halved if the device responds with just a hash of the message. To prevent the device from computing it on the fly without actually storing the message, the hash function is parametrized by a random value sent to the device after the message.[2][3]:16

Communication-efficient constructions

Avoiding the huge data transfer requires a suitable (as stated in Overview) computational problem, whose description is short. Dziembowski et al.[1] achieve this by constructing what they call an (m − δ, ε)-uncomputable hash function, which can be computed in quadratic time using memory of size m, but with memory of size m − δ it can be computed with at most a negligible probability ε.[3]:16

Communication- and time-efficient constructions

Karvelas and Kiayias claim to have designed the first PoSE with quasilinear time and sublinear communication complexity.[4]

Relation to proof of space

Proof of space is a protocol similar to proof of secure erasure in that both require the prover to dedicate a specific amount of memory to convince the verifier. Nevertheless, there are important differences in their design considerations.

Because the purpose of proof of space is similar to proof of work, the verifier's time complexity must be very small. While such property may be useful for proof of secure erasure as well, it is not fundamental to its usefulness.

Proof of secure erasure on the other hand requires the prover to be unable to convince the verifier using less than the specified amount of memory. Even this may be useful for the other protocol, however proof of space is not harmed if the prover may succeed even with significantly less space.[4]

References
  1. Stefan Dziembowski; Tomasz Kazana; Daniel Wichs (2011). One-Time Computable Self-erasing Functions. Theory of Cryptography. TCC 2011. Lecture Notes in Computer Science. Lecture Notes in Computer Science. 6597. pp. 125–143. doi:10.1007/978-3-642-19571-6_9. ISBN 978-3-642-19570-9.
  2. Daniele Perito; Gene Tsudik (2010). Secure Code Update for Embedded Devices via Proofs of Secure Erasure. Computer Security – ESORICS 2010. Lecture Notes in Computer Science. Lecture Notes in Computer Science. 6345. pp. 643–662. CiteSeerX 10.1.1.593.7818. doi:10.1007/978-3-642-15497-3_39. ISBN 978-3-642-15496-6.
  3. Nikolaos P. Karvelas (2013-01-07). "Proofs of secure Erasure (MSc Thesis)" (PDF). Technische Universität Darmstadt. Retrieved 25 April 2017.
  4. Nikolaos P. Karvelas; Aggelos Kiayias (2014). Efficient Proofs of Secure Erasure. Security and Cryptography for Networks. SCN 2014. Lecture Notes in Computer Science. Lecture Notes in Computer Science. 8642. pp. 520–537. doi:10.1007/978-3-319-10879-7_30. ISBN 978-3-319-10878-0.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.