Paranoia And Selling A Laptop
How do we erase a hard disk, for sure?
Richard Nixon was not a theorist—of course. He was the President of the United States from 1969 until 1974, when he resigned in disgrace. He was also an “un-indicted co-conspirator” and probably one of the most paranoid presidents ever.
Today I want to talk about paranoia. I have a problem that the more I think about, the more worried I get. I would like to share the problem with you in the hope that there is a technical solution.
One of my favorite quotes on paranoia is:
Even a paranoid can have enemies—Henry Kissinger
I often think that one of the best attributes for working in security and cryptography is to be a bit paranoid. You must think of all the ways that people are indeed out to get you.
Let’s turn to my problem.
My problem is simple to state, but I will use Alice and Bob to explain it—even though it is my problem. Alice has a laptop that she has used for years, and while it is old it still works fine. She has upgraded to a new shiny machine and would like to give her old laptop to Bob. Alice of course would like Bob not to get any information that is on her disk. Alice has no bad information—she never visited one of those web sites—but she does not want Bob to know anything about her. She is a bit paranoid. The problem is: how can Alice erase her hard disk in a way that Bob will get no information?
The Standard Solution
Alice does not want to remove her disk and throw it away. She wants a software solution. She is well aware that there are plenty of software programs that operate as follows: These programs write random bits to all of the disk. For safety, they will repeat this process and write random bits again and again to all of the disk. Note, just deleting all the files is useless, since this just deletes the meta-data and leaves the actual file data intact. Thus real delete programs must change all the bits of the disk, not just some of the disk. Even more, these programs need to write random bits and write them to each bit more than once. The reason for this repeated writing is simply paranoia. If a bit is not changed enough times then there may be ways for Bob to recover the bit.
Imagine a bit on the disk. We usually think of as boolean—it is or . But in real life the bit is a physical quantity which has a range of values. Think of it as a value in the range . A zero is a value near and is a value near . The problem is that as the bit is “erased” the physical process can be viewed as replacing by
where the ‘s are random values. Each of these values is near either or . Clearly, while is changed to a pretty random value, if is small there is still some information potentially left in the bit. A clever Bob may be able to use hardware methods to recover Alice’s bit .
Okay, Alice selects one of these programs, and turns it on. They all warn that the deletion process can take hours. This makes sense since the delete programs must touch all of the disk multiple times.
As the laptop hums away running the delete program, Alice has some paranoid thoughts: how does she know that the program is really deleting her files? How does Alice know that it is not cheating her? She realizes the delete program could be doing one of several things:
- It could be actually using a good pseudo random generator and actually writing to all of the disk.
- But it could be using a trivial sequence, like
- Or it could be missing some of the disk blocks. This would erase all of the disk except some small part.
- Even worse the program could be a total fraud. It pretends to erase the disk information, but does nothing.
Alice realizes she has no way to tell what the program is really doing. Should she trust that it really works?
This is the problem.
An Approach To Alice’s Problem
How does Alice get a delete program she can trust? I have some ideas on how this might be done, but all of them do not work yet. I envision that a solution would be a protocol like this: Alice runs a program on her new laptop that interacts with the old laptop and the delete program. This interaction forces the delete program to really delete the information on the disk.
The man idea I have—that does not work yet—is based on the following process. Let’s use to denote the delete program that is running on the old laptop. Also assume that the disk on the old laptop can store bits exactly. Then, one can imagine Alice’s new laptop running a program that operates as follows:
- The program sends random bits to to store on the disk.
- Then asks to return the random bits.
- If the returned bits agree with the sent bits, then accepts; otherwise, it declares the delete program a fraud.
This process can clearly be repeated as many times as needed.
The point of the protocol is that can try to not store the bits, but then how does it return the bits? Since the bits sent will be pseudo random, the delete program could try and “break” the random generator. However, we can assume that it cannot do that.
The open problem is how does Alice get a delete program that she really can trust? The above ideas fail to convince the real paranoid for at least two reasons. What if the program does not really work? Have we just replaced our trust with one program by another? Or is this program easier to verify? Another problem is that as I have described the protocol, the delete program could cheat. It could avoid writing to all of the disk by storing some of the bits in its random access memory. How do we handle that?
What should Alice do?